Chunk Text into Overlapping Windows

mediumPROContext & Agent MemoryAI AgentsAI Agents 1

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

Input

print(chunk_ranges(10, 4, 1))

Output

[(0, 4), (3, 7), (6, 10)]

Reasoning

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; if n == 0 return [].

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

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:

\text{stride} = size - overlap

Since $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.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results