A separation between RLSLPs and LZ77

Philip Bille, Travis Gagie, Inge Li Gørtz*, Nicola Prezza

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalJournal of Discrete Algorithms
Volume50
Pages (from-to)36-39
ISSN1570-8667
DOIs
Publication statusPublished - 2018

Keywords

  • Grammar-based compression
  • Run-length compression
  • SLP
  • RLSLP
  • LZ77
  • Thue-Morse sequence

Cite this