Comparison of LZ77-type parsings

Abstract

We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of them are defined as greedily constructed parsings encoding each phrase by reference to a string occurring earlier in the input. They differ by the phrase encodings: encoded by pairs (length + position of an earlier occurrence) or by triples (length + position of an earlier occurrence + the letter following the earlier occurring part); and they differ by allowing or not allowing overlaps between the phrase and its earlier occurrence. For a given string of length n over an alphabet of size σ, denote the numbers of phrases in the parsings allowing (resp., not allowing) overlaps by z (resp., zˆ) for “pairs”, and by z3 (resp., zˆ3) for “triples”. We prove the following bounds and provide series of examples showing that these bounds are tight: • z≤zˆ≤z⋅O(log⁡[Formula presented]) and z3≤zˆ3≤z3⋅O(log⁡[Formula presented]); • [Formula presented]zˆ<zˆ3≤zˆ and [Formula presented]z<z3≤z. © 2018 Elsevier B.V.