A Separation Between Run-Length SLPs and LZ77

Autor:	Bille, Philip, Gagie, Travis, Gørtz, Inge Li, Prezza, Nicola
Rok vydání:	2017
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	In this paper we give an infinite family of strings for which the length of the Lempel-Ziv'77 parse is a factor $\Omega(\log n/\log\log n)$ smaller than the smallest run-length grammar.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1711.07270 Zobrazit plný text záznamu View this record from Arxiv