Journal article
A separation between RLSLPs and LZ77
In their ground-breaking paper on grammar-based compression, Charikar et al. (2005) gave a separation between straight-line programs (SLPs) and Lempel Ziv ’77 (LZ77): they described an infinite family of strings such that the size of the smallest SLP generating a string of length n in that family, is an Ω(logn/loglogn)-factor larger than the size of the LZ77 parse of that string.
However, the strings in that family have run-length SLPs (RLSLPs) — i.e., SLPs in which we can indicate many consecutive copies of a symbol by only one copy with an exponent — as small as their LZ77 parses. In this paper we modify Charikar et al.’s proof to obtain the same Ω(logn/loglogn)-factor separation between RLSLPs and LZ77.
Language: | English |
---|---|
Year: | 2018 |
Pages: | 36-39 |
ISSN: | 15708675 and 15708667 |
Types: | Journal article |
DOI: | 10.1016/j.jda.2018.09.002 |
ORCIDs: | Bille, Philip , Gørtz, Inge Li , Prezza, Nicola and 0000-0003-3689-327X |