Context Window Finder

easyFREEQuestion AnsweringNLP 3: Advanced

Given a document (list of words) and a query word, find the context window of size k around each occurrence of the query word. Return all unique context windows.

Implement find_windows(words, query, k):

words: the document as a list of words
query: the query word
k: window size (number of words on each side)

Output: Return a list of context window strings (each window's words joined by single spaces), in order of first appearance. Matching is case-insensitive. If the query word never appears, return ["No matches found"].

Example

Input

the cat sat on the mat near the door
the
1

Output

the cat
on the mat
near the door

Reasoning

words is the document split into $n = 9$ words, numbered from 0: the(0) cat(1) sat(2) on(3) the(4) mat(5) near(6) the(7) door(8). query is the and k is 1, so a window holds at most $2k + 1 = 3$ words.
The query matches at positions 0, 4 and 7. Around a match at position $i$ , the window covers positions $i - k$ through $i + k$ , clipped to the valid range $0$ to $n - 1 = 8$ .
Position 0: the range $-1$ to $1$ clips to $0$ to $1$ , giving the cat. Only 2 words, since nothing lies left of the first word.
Position 4 gives positions 3 to 5, and position 7 gives positions 6 to 8, which ends exactly at the last word.
All three windows differ, so all three lines are output in order of appearance: the cat on the mat near the door.
Notice that repeats are possible: in "a b a c a" with $k = 0$ every window is just a, so only one is kept.

Constraints

Case-insensitive matching for query word
Window extends k words on each side
Clip at document boundaries
Output unique windows in order of first appearance

Learn this in

Text RepresentationNLP Study Plan Word EmbeddingsNLP Study Plan

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Keyword Answer Extractoreasy Levenshtein Distanceeasy Word-Level Translatoreasy

Concept primer

Background Knowledge

The "Context Window Finder" problem is rooted in Natural Language Processing (NLP), specifically within the realm of Question Answering. This domain involves understanding and manipulating human language to extract meaningful information. A key concept here is the context window, which refers to a sequence of words surrounding a specific term or phrase of interest. The size of this window (denoted by $k$ ) determines how many words on each side of the target word are included. Understanding context windows is crucial for tasks like text analysis, information retrieval, and language modeling, as it helps in capturing the semantic relationships between words.

In NLP, tokenization (the process of breaking down text into individual words or tokens) and case-insensitive matching are fundamental techniques. For this problem, the ability to find all occurrences of a query word in a document, regardless of case, is essential. This involves converting both the document and the query word to a standard case (either lower or upper) before performing the search. The concept of windowing or sliding window techniques is also relevant, where a fixed-size window moves over the data (in this case, the document) to extract subsets of data (context windows) around points of interest (the query word).

The problem requires returning all unique context windows in the order of their appearance. This implies that if the same context window appears multiple times due to multiple occurrences of the query word, it should only be reported once, but its first occurrence's position in the document determines its output order. This involves understanding set operations (to ensure uniqueness) and maintaining a record of the order in which these windows are first encountered.

Algorithm/Approach

The general approach to solving this type of problem involves a combination of string processing, pattern matching, and set operations. The algorithm pattern can be outlined as follows:

Preprocess the document and query word for case-insensitive matching.
Iterate through the document to find all occurrences of the query word.
For each occurrence, extract the context window of size $k$ .
Store unique context windows, ensuring that each is only added once but maintaining the order of first appearance.

Step-by-Step Strategy

Preprocessing: Convert the document and query word to lower case to enable case-insensitive matching.
Find Query Word Occurrences: Iterate through the document to find all indices where the query word occurs.
Extract Context Windows: For each occurrence of the query word, calculate the start and end indices of the context window based on the window size $k$ .
Handle Edge Cases: Adjust the start and end indices if the context window extends beyond the document boundaries.
Store Unique Windows: Use a set or similar data structure to store unique context windows. Since sets automatically eliminate duplicates, this ensures uniqueness. However, to maintain the order of first appearance, consider using an ordered data structure like a list or an ordered dictionary, checking for membership before adding.
Output Windows: Iterate through the stored unique context windows and print each one.

Common Pitfalls

Index Out of Bounds: Failing to adjust context window boundaries when they exceed the document's limits.
Case Sensitivity: Not converting both the document and query word to the same case before searching.
Duplicate Windows: Not implementing a mechanism to ensure uniqueness of context windows while preserving order of appearance.

Time & Space Complexity

Time Complexity: The time complexity is expected to be $O(n \cdot k)$ , where $n$ is the number of words in the document and $k$ is the window size. This is because in the worst case, for each word in the document, we might need to examine $k$ words to its left and right.
Space Complexity: The space complexity is $O(n \cdot k)$ as well, because we need to store all unique context windows. In the worst-case scenario, if every context window is unique, we would store $n$ windows, each of size $2k + 1$ .

solution.py

Python 3.13

Test results