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 Omega(log n/ log log n)-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 Omega(log n/ log log n)-factor separation between RLSLPs and LZ77. (C) 2018 Elsevier B.V. All rights reserved.
|Data di pubblicazione:||2018|
|Titolo:||A separation between RLSLPs and LZ77|
|Rivista:||JOURNAL OF DISCRETE ALGORITHMS|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.jda.2018.09.002|
|Appare nelle tipologie:||2.1 Articolo su rivista |
File in questo prodotto: