Why does a sliding-window matcher emit short repeats as literals rather than as back-references?

## A token has a price The match stage of a sliding-window compressor chooses, at every position, between two purchases: emit the next byte as a **literal**, or emit a **match token** that replaces several bytes with a distance and a length. The second is only worth making when the token costs fewer bits than the bytes it displaces, and the token's cost is largely fixed — it does not shrink because the match happens to be short. That fixed cost has two parts: - **The distance.** Its range is the window size, so a 32 KB window means a value in `1..32768`, up to 15 bits before any entropy coding. - **The length.** A few bits, plus whatever flag or alphabet trick distinguishes a match token from a literal in the stream. Call it roughly 21 bits for a scheme with a 32 KB window. That is the hurdle every match must clear. ## Doing the arithmetic Literals cost 8 bits each before entropy coding, so the comparison is a straight multiplication. | Match length | Literals it replaces | Raw literal bits | Token bits | Verdict | |---|---|---|---|---| | 2 | 2 | 16 | ~21 | loses — emit literals | | 3 | 3 | 24 | ~21 | marginal gain | | 4 | 4 | 32 | ~21 | clear gain | | 8 | 8 | 64 | ~21 | large gain | | 32 | 32 | 256 | ~21 | overwhelming | So the break-even sits at three bytes, which is why minimum match lengths of three or four are the common design point. The figure moves with the window: a larger window widens the distance range, raising the token's price and pushing the break-even length up, while a small window lowers both. ## The entropy stage moves the line The raw arithmetic above is not the whole story, because the token stream is normally handed to a second stage that codes frequent symbols in fewer bits. That cuts both sides of the comparison, and not equally: 1. Literals in real data are far from uniform, so a typical literal costs noticeably fewer than 8 bits once coded. 2. Small distances and short lengths are common, so cheap matches get cheaper too. 3. But the *number* of symbols in a token — a distance and a length, versus one symbol per literal — does not change. The net effect is that the break-even is not a constant; a scheme picks a threshold that is right on average for the data it expects. It also explains a second-order benefit of a higher threshold: excluding the marginal two- and three-byte matches keeps the length symbols concentrated on a few values, which the entropy stage codes more cheaply than a flat spread. ## What goes wrong if the threshold is too low Allowing very short matches is not merely useless, it is actively harmful: - Output can **grow**, because each unprofitable token spends more bits than the literals it displaced. - The match rate rises while the ratio falls — a metric that looks like success and is not. - The length distribution flattens, so every length symbol costs more, taxing the profitable long matches as well. - The encoder spends search time confirming matches it should not take. Setting it too high has the mirror cost: genuinely profitable three- and four-byte matches — common in structured, punctuation-heavy payloads — are thrown away and paid for in literals. ## The point that generalises This is the clearest small instance of a rule that runs through the whole family: **compression is bookkeeping in bits, not in bytes replaced**. A back-reference does not "save" the bytes it covers; it trades them for the cost of naming them. Any argument of the form "we found more repeats, so it must be smaller" is unsound unless the repeats were long enough to pay for their own tokens. The same reasoning reappears when choosing between two candidate matches, when deciding whether to break a long match to reach a better one, and when judging whether an extra stage in a pipeline earns its framing overhead.