Lempel-Ziv Parsing with Match-Length-Dependent Windows: Universality and Limits

@misc{yingquan2026lempelziv,
  title = {{Lempel-Ziv Parsing with Match-Length-Dependent Windows: Universality and Limits}},
  author = {Yingquan and Wu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06530},
  eprint = {2610.06530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06530},
}

TY  - UNPB
TI  - Lempel-Ziv Parsing with Match-Length-Dependent Windows: Universality and Limits
AU  - Yingquan
AU  - Wu
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.06530
UR  - https://arxiv.org/abs/2610.06530
AB  - LZ77 coders spend the same number of bits on the distance of every match, although short matches rarely pay off at long distances. With match-length-dependent windows, used in several practical codecs, a match of length ℓ may refer back at most W(ℓ) symbols: short matches get short distance fields, while long matches keep the full window W. This breaks the suffix closure that classical LZ77 analyses rely on: the tail of an admissible match need not be admissible. We bound the cost of this loss, and of matches missed by a practical hash search, by the phrase count of a single-window reference parse. Consequently, when the full window starts at length O(log W), greedy parsing keeps the convergence rates and the optimal finite-input rates of LZ77 under substring-complexity constraints, and when it starts at length o(log W), greedy parsing is universal for stationary ergodic sources. We then delimit what the windows gain. A calibrated schedule never increases the minimum code length and saves a polynomially small rate on some iid sources. The leading redundancy term is set by the length code instead: on uniform iid data, with logarithmic-cost lengths and a fixed full-window threshold, it is at least of order (loglog W)/log W whatever windows the short matches use, and a short codeword for a growing longest match reduces it to O((logloglog W)/log W). We also quantify the gains of coding single-symbol runs by count and of Huffman coding the token fields, and obtain a consistent entropy-rate estimator by selecting the window.
ER  -