Chunking with Overlap

The problem

Before indexing, documents are cut into chunks: passages short enough to match a question precisely. If chunks are cut at fixed positions, a sentence that straddles a boundary is split in two halves, and neither chunk makes sense alone. An overlap fixes it: each chunk starts a bit before the end of the previous one, so a cut sentence appears whole in the next chunk.

The rule

For a list of tokens, a chunk size size and an overlap overlap:

• chunks have size tokens, and each starts size - overlap tokens after the previous one: the starts are $0, s, 2s, \dots$ with $s = \text{size} - \text{overlap}$;
• stop as soon as a chunk reaches the end of the text. The last chunk may be shorter than size; never emit a chunk that only repeats the end of the previous one;
• return a list of (start, chunk_tokens) pairs. An empty input gives an empty list;
• raise ValueError unless 0 <= overlap < size.

Example. Tokens 0, 1, ..., 9 (10 tokens), size = 4, overlap = 1, so the stride is 3:

• start 0: [0, 1, 2, 3];
• start 3: [3, 4, 5, 6];
• start 6: [6, 7, 8, 9]: it reaches the end, so stop.

Tokens 3 and 6 are in two chunks each. With 8 tokens the last chunk is shorter: [0, 1, 2, 3], [3, 4, 5, 6], [6, 7]. With 7 tokens, size 4 and overlap 2 (stride 2): [0..3], [2..5], [4, 5, 6]; a chunk starting at 6 would only repeat token 6.

What to implement

chunk(tokens, size, overlap): the list of (start, chunk_tokens) pairs.

Requirements

• Every token must be in at least one chunk, and consecutive chunks must share exactly overlap tokens (except possibly the last, shorter one).

Hint

Walk with a start that grows by the stride; after adding a chunk, stop if start + size >= len(tokens).