skip to content

Why does a sliding-window compressor with a 32 KB window miss a repeat that last occurred 100 KB earlier?

level: middleimportance: should knowfreq 48%

answer

  1. reach, not intelligence
  2. only the last N bytes
  3. 32 KB means 32768
  4. distance field sized to the window
  5. decoder holds the window too

basics

~20 s

A sliding window holds only the most recent N bytes — 32768 of them at 32 KB. A repeat 100 KB back has already slid out and no distance can address it, so the compressor re-emits those bytes as literals. The output stays correct, just larger.

solid answer

~40 s

Window size is a **reach** limit: only repeats whose earlier copy lies within the last N bytes can be referenced. At 32 KB that is 32768 bytes, and a duplicate 102400 bytes back is simply out of range — the bytes are gone from the window and a distance field sized for 32 KB cannot express the offset anyway. The compressor is not failing; it re-encodes the block as literals (plus whatever nearer matches it finds), so the result decompresses correctly and is merely bigger. The window size is also a **contract on the decoder**, which must retain the same N bytes of output to resolve any distance, so enlarging it spends memory on both ends and lengthens every distance symbol.

go deeper

for a junior

Hold on to the one fact: a back-reference can only reach back a limited distance, so duplicates that are far apart are re-encoded from scratch.

for a middle

Be able to convert a window size into a distance range and explain both limits behind it — the bytes that must be retained and the width of the distance symbol.

for a senior

Diagnose a poor ratio on visibly redundant data by measuring how far apart the duplicates actually are, and reach for layout or chunking changes before settings.

for a principal

Treat window size as a long-lived commitment: it fixes the memory every future reader must have, so pick it against the most constrained consumer, not the compressor's host.

## What "window" limits In a sliding-window scheme the window is the span of already-processed bytes that a back-reference is allowed to point into. A 32 KB window means 32768 bytes: at any moment, the encoder can express "copy from up to 32768 bytes back" and nothing further. As the encoder advances, older bytes leave the window. A duplicate of a block last seen 102400 bytes ago is therefore invisible to the match stage, even though it is a byte-for-byte repeat, because 102400 > 32768. Two separate constraints combine into this one limit, and it is worth keeping them apart: - **Memory.** The encoder must retain the bytes to compare against, and the decoder must retain them to copy from. Reach cannot exceed what is kept. - **Symbol range.** A distance is coded as a number in `1..N`. Sizing the window at 32768 means distances need up to 15 bits before any entropy coding; a distance of 102400 has no representation in that alphabet. | Window | Distances addressable | Raw distance width | Buffer each end must hold | |---|---|---|---| | 4 KB | 4096 | 12 bits | 4 KB | | 32 KB | 32768 | 15 bits | 32 KB | | 1 MB | 1048576 | 20 bits | 1 MB | | 8 MB | 8388608 | 23 bits | 8 MB | ## What the compressor does instead Nothing breaks. A lossless coder never discards data, so the unreachable duplicate is simply encoded the expensive way: as literals, interspersed with any shorter matches that *are* in range — boilerplate, field names, punctuation and other fragments that recur constantly and are therefore always nearby. The visible symptom is a ratio that is worse than the data's actual redundancy would suggest. Someone measuring it will say "this file is full of duplicates and it barely compressed", and the window is the usual explanation. ## Layout decides what is reachable Because reach is measured in bytes of *distance*, the arrangement of the data is as important as its content: - Interleaving two producers into one stream pushes each producer's own duplicates further apart, and past some interleaving factor every self-similarity falls out of the window. - Splitting a large body of similar records into many independently compressed chunks resets the window at every boundary, so cross-chunk similarity is never exploited at all. - Grouping similar records together brings their duplicates within reach and can shrink the output dramatically without changing a single byte of content. That last point is the practical lever: the same bytes, reordered so their repeats are near each other, compress better under the same scheme and the same settings. ## Why not just use a huge window A bigger window does reach more repeats, but it is not free, and three costs land in different places: 1. **Decoder memory.** Whoever reads the data must hold N bytes of recent output. This is the one that bites hardest, because the reader may be far more constrained than the writer, and the requirement is permanent for as long as the data exists. 2. **Distance cost.** A wider distance range means more symbols and, on average, more bits per match token — every match pays a little more so that rare far-away matches can exist. 3. **Search cost.** More candidate positions to consider per match, so encoding slows down unless the search is bounded, in which case some of the extra reach goes unused. And the gains taper: once the window is large enough to hold the natural period of repetition in the data — a record, a page, a batch — doubling it again finds little. Conversely, if the period is far larger than any practical window, the match stage cannot see the redundancy at all and a different approach is needed to expose it. ## How to reason about it in review The useful mental model is a ruler, not a dictionary. Ask: *how far apart are the duplicates in this stream, in bytes?* If the answer is larger than the window, no amount of tuning inside the match stage will find them; the fix is either a bigger window, paid for in memory on both ends, or a layout change that moves the duplicates closer together. If the answer is well inside the window and the data still compresses poorly, the redundancy is not sequence repetition at all, and the match stage is the wrong tool to be looking at.

  • Does the decoder need as much memory as the window?
    Effectively yes: it must retain the last N bytes of output so that any legal distance can be resolved. Window size is therefore part of the contract between writer and reader, not a private encoder setting, and it stays binding for as long as the compressed data is kept.
  • Would a larger window always compress better?
    No. It costs memory at both ends and widens the distance range, so every match token pays slightly more bits. Once the window already spans the data's natural repetition period, the extra reach finds little, and the added per-match cost can offset the few long-distance matches gained.
  • Why does compressing one large stream often beat compressing the same records individually?
    Each independent compression starts with an empty window, so every record pays full price for content it shares with its neighbours. Concatenating them lets later records reference earlier ones — provided they stay within window reach of each other.

saying these in an interview costs you the question

  • Says the compressor is buggy because it missed an exact duplicate
  • Thinks the matcher scans the whole input regardless of window size
  • Assumes a bigger window costs the encoder only, not the reader
  • Confuses the window of past bytes with the lookahead buffer
  • Claims doubling the window roughly halves the output