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: | |
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: |