Chunk Text into Overlapping Windows
Problem Statement
Split a long token stream into fixed-size chunks with a fixed overlap, the standard preprocessing for populating a vector memory.
Background
Given n tokens, a chunk size size, and an overlap, chunks start at *0, size-overlap, 2(size-overlap), ...**. Each chunk spans [start, min(start+size, n)). Generation stops once a chunk reaches the end. The step size - overlap must be positive.
Your Task
Implement:
def chunk_ranges(n, size, overlap):
Return a list of (start, end) tuples (end exclusive) covering the stream, with the given overlap. Stop after the chunk that reaches n.
Input Format
- n (int) total tokens, size (int), overlap (int) with 0 <= overlap < size.
Output Format
- A list of (start, end) int tuples.
Sample
print(chunk_ranges(10, 4, 1))
Output:
[(0, 4), (3, 7), (6, 10)]
Example:
print(chunk_ranges(10, 4, 1))
[(0, 4), (3, 7), (6, 10)]
- Compute the stride between chunk starts using the formula step=size−overlap, which yields 4−1=3; this determines how far the window shifts after each chunk.
- Initialize the first chunk at index 0; its end is calculated as min(0+4,10)=4, producing the range (0,4) since it has not yet reached the total length n=10.
- Advance the start position by the stride to 0+3=3; the new end is min(3+4,10)=7, creating the overlapping range (3,7) where the overlap of 1 token is shared with the previous chunk.
- Advance the start position again by the stride to 3+3=6; the new end is min(6+4,10)=10, creating the range (6,10).
- Since the end index 10 equals the total token count n, the generation stops, and the final output is
[(0, 4), (3, 7), (6, 10)].
Constraints:
0 <= overlap < size,size >= 1,n >= 0.- Step is
size - overlap; each chunk is[start, min(start+size, n)). - Stop once a chunk's end reaches
n; ifn == 0return[].
1. Background Knowledge
This problem models the sliding window technique, a fundamental pattern in signal processing, NLP, and time-series analysis. When a document or token stream is too long to fit into a model's context window, it is split into smaller, manageable segments called chunks. To prevent important information from being lost at the boundaries between chunks, consecutive chunks share a portion of their content. This shared portion is the overlap.
In the context of vector memory for AI agents, each chunk is typically embedded into a vector and stored in a vector database. When the agent needs to recall information, it searches for the most relevant vectors. Overlapping chunks ensure that if a critical piece of information spans the boundary of two chunks, it is fully contained within at least one chunk, improving retrieval accuracy.
The mathematical structure here is an arithmetic progression of starting indices. If the chunk size is size and the overlap is overlap, the distance between the start of one chunk and the start of the next is the stride, defined as:
stride=size−overlapSince overlap<size, the stride is always positive, ensuring the windows move forward through the token stream without infinite loops.
2. Algorithm Approach
The problem is a straightforward iterative generation task. You do not need complex data structures or recursion. The approach is:
- Calculate the stride (size−overlap).
- Initialize a start index at 0.
- In a loop, calculate the end index for the current chunk. The end is the minimum of start + size and the total length n, ensuring you don't exceed the stream's boundary.
- Append the (start, end) tuple to the result list.
- Update start by adding the stride.
- Terminate the loop once the start index reaches or exceeds n.
This is a linear scan with constant work per iteration, making it highly efficient.
3. Step-by-Step Strategy
- Compute Stride: Calculate step = size - overlap. This is the increment for the start index.
- Initialize: Create an empty list ranges and set start = 0.
- Loop Condition: Continue while start < n. This ensures we only generate chunks that begin within the valid token range.
- Determine End: Set end = min(start + size, n). This handles the final chunk, which may be shorter than size if it reaches the end of the stream.
- Record Range: Append (start, end) to ranges.
- Advance: Update start += step.
- Return: Return the ranges list.
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.