Keyword Answer Extractor

easyFREEQuestion AnsweringNLP 3: Advanced

Given a context paragraph and a question, find the sentence in the context that has the most keyword overlap with the question. Return that sentence as the answer.

Input format:

Line 1: The context (sentences separated by periods)
Line 2: The question

Keywords are all words (lowercased) except common stop words: {"the", "a", "an", "is", "are", "was", "were", "in", "on", "at", "to", "for", "of", "and", "or", "it", "this", "that", "what", "which", "who", "where", "when", "how", "do", "does", "did"}.

If there's a tie, return the first matching sentence.

Example

Input

Cats are popular pets. Dogs are loyal animals. Fish live in water.
What animals are loyal

Output

Dogs are loyal animals

Reasoning

Step 1: Extract question keywords (minus stop words) "what animals are loyal" → keywords: {"animals", "loyal"}

Step 2: Count keyword overlap per sentence "Cats are popular pets" → overlap: 0 "Dogs are loyal animals" → overlap: {"loyal", "animals"} = 2 "Fish live in water" → overlap: 0

Step 3: Return best match "Dogs are loyal animals" has highest overlap (2)

Constraints

Sentences separated by periods
Case-insensitive matching
Stop words excluded from keyword matching
Output: The best matching sentence (stripped of leading/trailing whitespace)

Learn this in

Question Answering & Information RetrievalNLP Study Plan

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Levenshtein Distanceeasy Word-Level Translatoreasy

Concept primer

Background Knowledge

The "Keyword Answer Extractor" problem falls under the category of Question Answering, a subfield of Natural Language Processing (NLP). Question Answering involves finding relevant information from a given context to answer a specific question. This problem requires understanding the concept of keyword extraction, where the goal is to identify the most important words (keywords) in a sentence or paragraph. In this case, keywords are defined as words that are not common stop words, which are words that do not carry much meaning in a sentence, such as "the", "a", etc.

To solve this problem, it's essential to have a basic understanding of text preprocessing techniques, including tokenization (splitting text into individual words) and stop word removal. Additionally, familiarity with string matching and set operations will be helpful in comparing the keywords between the question and the context sentences. The problem also touches on the concept of information retrieval, where the goal is to find the most relevant information (in this case, a sentence) from a larger corpus (the context paragraph).

Understanding the concept of overlap or similarity between two sets of words is also crucial. This can be measured using various techniques, such as set intersection or Jaccard similarity. The Jaccard similarity, for example, is calculated as the size of the intersection divided by the size of the union of two sets: $J(A, B) = \frac{|A \cap B|}{|A \cup B|}$ . This concept will be useful in determining the sentence with the most keyword overlap with the question.

Algorithm/Approach

The general approach to solving this problem involves the following algorithm pattern:

Preprocess the context and question text by tokenizing and removing stop words
Extract keywords from the question and each sentence in the context
Compare the keywords between the question and each sentence to find the sentence with the most overlap
Return the sentence with the most overlap as the answer

This approach can be implemented using a combination of string manipulation, set operations, and conditional statements.

Step-by-Step Strategy

To implement the solution, follow these steps:

Preprocess the context and question text: Tokenize the text into individual words and remove stop words.
Extract keywords from the question and each sentence: Identify the keywords in the question and each sentence in the context.
Compare the keywords between the question and each sentence: Use set operations (e.g., intersection, union) to find the overlap between the keywords in the question and each sentence.
Find the sentence with the most overlap: Compare the overlap between the question and each sentence to find the sentence with the most keywords in common.
Return the sentence with the most overlap: Output the sentence with the most keyword overlap as the answer.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrect stop word removal: Make sure to remove stop words correctly to avoid false positives.
Inconsistent tokenization: Ensure that tokenization is consistent across the context and question text.
Incorrect overlap calculation: Double-check the calculation of overlap between the question and each sentence.

Time & Space Complexity

The expected time complexity of the solution is O(nm), where n is the number of sentences in the context and m is the average number of words in a sentence. The space complexity is O(nm) as well, as we need to store the preprocessed text and keyword sets for each sentence. However, the actual complexity may vary depending on the implementation details and the specific algorithms used for tokenization, stop word removal, and overlap calculation.

solution.py

Python 3.13

Test results