Can match-length-dependent sliding windows improve LZ77 compression rates?

WLZ ties window size to match length

Classical LZ77 encodes a repeated substring as a backward distance plus a match length, and every match draws on the same history of W symbols. That is wasteful for short matches: a two-byte repeat rarely needs a pointer into the far past, yet it pays the same fixed-width distance field as a long repeat. WLZ instead assigns a window W(ℓ) to each match length ℓ, so short matches use smaller windows and shorter distance fields while long matches keep access to distant repetitions. The decoder infers the distance range from the decoded length, so no separate class identifier is needed.

The paper keeps two quantities strictly apart throughout: window sizes measured in input symbols, and distance-field widths measured in bits. A length-ℓ match has window W(ℓ) and width w(ℓ) := log2 W(ℓ); the maximum window W has width B := log2 W. This distinction matters because the compression saving from a narrower window is a saving in bits per match, while the window itself is a search-space limit in symbols.

A transfer bound charges restricted windows and missed matches

Restricting windows breaks a property the classical LZ77 analysis relies on: a suffix of a legal copy can keep a distance outside its shorter length's window, so the suffix closure behind the standard comparisons fails. The paper's parsing-transfer inequality repairs this by charging both the window restrictions and any matches the parser misses or declines. With that charge in place, established phrase-count bounds still apply to WLZ.

The consequence is that exact greedy WLZ preserves the convergence rates of ordinary LZ77 under substring-complexity bounds, and its finite-class minimax orders when windows are comparable to the input length. A sharper block charge proves stationary-ergodic universality of exact greedy WLZ when full-window matching begins at length o(B). These are preservation results: WLZ does not lose the guarantees LZ77 already had, provided the parser is exact and the missed-match term is accounted for.

A calibrated schedule never raises minimum token cost

The central comparison fixes a single-window comparator that uses one window 2^B, the same literal cost, and match cost a(ℓ)+B. Given any comparator parse, its matches split into those the length-dependent windows admit and those they exclude. Admitting the first group saves B−w(ℓ) bits per match; replacing each excluded match with its literals costs bℓ−a(ℓ)−B bits. Lemma 4.3 shows the minimum token cost of an admissible parse is at most the comparator cost minus the admitted savings plus the exclusion cost.

Two practical readings follow. First, shorter distance fields alone do not guarantee improvement: for a heuristic encoder with excess token cost E_W and header difference ΔΓ, strict improvement requires the admitted savings to exceed the exclusion cost plus E_W plus ΔΓ. Second, window widths can be chosen by a marginal rule — expanding a window by one bit helps exactly when the newly admitted matches' savings exceed the extra bit charged to every previously admitted match. Nondecreasing widths across length classes can then be selected by a prefix-minimum dynamic program in O(J(B_max+1)) time after histogram construction, optimizing a fixed trace rather than joint window selection and reparsing.

The window saving is real but polynomially small

On specified iid sources, a calibrated window schedule saves Ω(BW^−β) in rate with β>2. That is a genuine asymptotic improvement over the single-window baseline, but it decays polynomially in the window size, so it is not where the large gains live. The paper states this directly: the remaining gains come from the token code rather than the windows.

A separate obstruction sharpens the point. For an iid uniform source with a fixed integer threshold t independent of B, where every length at least t gets the full window and exactly B distance bits, the redundancy is at least h + c·h·log B/B − O(B^−1). This rules out redundancy O(B^−p) for p>1, and even O(B^−1), in that model. Changing the short-match windows alone therefore cannot deliver the better exponent; the length-cost assumption behind the bound holds for common universal integer codes but does not follow from prefix-decodability alone.

Cheap length symbols and run recoding drive the larger gains

On a uniform iid source, a growing phrase cap with a cheap length symbol improves redundancy from the Ω(log B/B) of the original 1977 fixed-field format — whatever phrase cap that format uses — to O(log log B/B). The comparison isolates the cost of the historical length field, and the paper notes that a single-window encoder with the same token code gains as much.

A second recoding targets runs. Writing a single-symbol run (r,1) as (1,r), with a logarithmic-cost count r that may exceed the match cap, codes inputs with O(n^α) runs, 0≤α<1, in O(n^α log n) bits, versus Ω(n) for the 1977 format with phrase cap Θ(log W) and W=o(n). The extension rule decides which conclusion applies: positional varints or universal integer codes can meet the logarithmic hypothesis, whereas one extension byte per additional 255 symbols, as in the LZ4 match-length format, costs Θ(r) bits. If g(r)/r→γ and Γ_n=o(n), the single-run parse has limiting rate γ on a constant input, and a strict constant improvement still follows whenever γ < c/L.

Huffman coding the fields cuts the periodic-input rate

On globally p-periodic inputs, Huffman coding the fields of a capped parse with nearest-distance ties reduces the large-file rate from Θ(B/W) under fixed-width coding to at most 3/W, including tables and framing. The mechanism is the standard conditioning identity: for a fixed parse with M matches, decoded length class J, and distance symbol Z, the ideal empirical saving from conditioning is M·Î(Z;J), because the decoded length identifies J without a class selector. Unconstrained binary Huffman coding shifts that saving by rounding terms each in [0,M) when singleton alphabets may use zero bits, and extra distance bits, table headers, and format restrictions must also be charged.

The paper is careful about what its measurements show. With the WZIP codec's bounded dynamic-programming parser, replacing per-length-group offset tables by one table lowers the compression ratio on the Silesia corpus by 0.58%, whereas admitting every length at every distance, with offsets still coded per group, leaves it unchanged. Each ablation reparses the input, so the paper says this indicates rather than isolates the effect of conditioning.

Complete WLZ codes also yield an entropy-rate estimator

Selecting among complete WLZ codes produces an entropy-rate estimator that is consistent almost surely and in mean, with finite-data error bounds for fixed nonuniform iid sources. The minimum-bit variant of this estimator, which evaluates C*_{B,n} for every B≤K_n≤log n, takes O(n log^3 n) time.

The analysis carries explicit scope conditions. Exact greedy parsing is required for the universality and convergence statements; practical encoders that cap candidates, retain only the latest hash entry, skip insertions, or apply lazy matching are useful speed choices but their output is not assumed to equal the reference parse, and the analysis either requires exact greedy parsing or charges missed and declined matches. The run-code gain depends on the specified ordinary cap, and the periodic Huffman comparison changes the available phrase expansions. The paper also flags open directions: matching upper and lower bounds for the fixed-source saving from calibrated windows with the length-code model held fixed, quantitative recurrence-tail and search-loss bounds for dependent sources, and efficient joint selection of window sizes and hash-chain inspection budgets under memory and time constraints.

Where the next bit of compression actually comes from

The paper's own priority ordering is the useful takeaway. If the goal is a better compression rate, the window schedule is not the lever to pull first: its asymptotic strict gain on the analyzed sources is polynomially small, and the fixed-threshold obstruction rules out redundancy O(B^−p) for p>1 from short-match windows alone. The token code is the lever — a cheap length symbol with a growing phrase cap moves uniform-iid redundancy from Ω(log B/B) to O(log log B/B), and run recoding moves few-run inputs from Ω(n) to O(n^α log n).

The window schedule still earns its place for a different reason: it restricts short-match histories, which reduces indexing resources, and it never increases minimum token cost relative to a single-window baseline when calibrated. So the decision splits by objective. Choose length-dependent windows for memory and search cost while keeping LZ77's convergence orders intact; choose the token code when the target is the compression ratio itself. The condition to check before expecting a window gain is the improvement inequality — admitted savings must exceed the exclusion cost plus heuristic excess plus header difference — and the condition to check before expecting a run-code gain is the extension rule, since a byte-per-255-symbols format costs Θ(r) bits and forfeits the logarithmic hypothesis.

Sources used in this answer