Context Window Extractor
Extract relevant context windows from a document for a given query.
Given a document (list of sentences) and a query, find sentences that contain at least one query word and return them with their indices.
Input format:
- Line 1: Query string (space-separated words, lowercase)
- Line 2: Number of sentences N
- Lines 3 to N+2: One sentence per line (lowercase)
Output: A list of tuples (index, sentence) for sentences containing at least one query word. Matching is case-insensitive (both already lowercase).
Example:
machine learning 4 deep learning is a subset of machine learning natural language processing uses rules machine translation converts text between languages learning algorithms improve with data
[(0, 'deep learning is a subset of machine learning'), (2, 'machine translation converts text between languages'), (3, 'learning algorithms improve with data')]
Query words: {"machine", "learning"}
- Sentence 0: "deep learning is a subset of machine learning" — contains both "learning" and "machine" => MATCH
- Sentence 1: "natural language processing uses rules" — no match
- Sentence 2: "machine translation converts text between languages" — contains "machine" => MATCH
- Sentence 3: "learning algorithms improve with data" — contains "learning" => MATCH
Constraints:
- Match whole words only (split on whitespace)
- Both query and sentences are lowercase
- Return matches in order of appearance
- A sentence matches if it contains ANY query word
Background Knowledge
The "Context Window Extractor" problem falls under the category of Natural Language Processing (NLP), specifically within the topic of Question Answering. This involves analyzing and understanding human language to extract relevant information. A key concept here is tokenization, which is the process of breaking down text into individual words or tokens. In this problem, both the query and the document are already tokenized into lowercase words, simplifying the comparison process.
Understanding how to compare the query words with the sentences in the document is crucial. This comparison is based on string matching, where we look for occurrences of query words within each sentence. Since the matching is case-insensitive and both the query and sentences are in lowercase, we can directly compare the words without worrying about case differences. The concept of context window is also important, as it refers to the portion of the text (in this case, sentences) that is relevant to the query.
In NLP, information retrieval techniques are often used to find relevant documents or parts of documents based on a query. The "Context Window Extractor" problem is a simplified version of such techniques, focusing on extracting relevant sentences from a document. This requires understanding how to efficiently search through text data and how to determine the relevance of a sentence based on the presence of query words.
Algorithm/Approach
The general approach to solving this type of problem involves iterating through each sentence in the document and checking if any of the query words are present in the sentence. This can be achieved through a simple linear search algorithm, where each sentence is scanned for the occurrence of query words. The algorithm should keep track of the index of each sentence that contains at least one query word and return this information along with the sentence itself.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.