Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Approximation Ratios of \(\mathsf {RePair}\), \(\mathsf {LongestMatch}\) and \(\mathsf {Greedy}\) on Unary Strings
verfasst von : Danny Hucke
Erschienen in: String Processing and Information Retrieval
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A grammar-based compressor computes for a given input w a context-free grammar that produces only w. So-called global grammar-based compressors (\(\mathsf {RePair}\), \(\mathsf {LongestMatch}\) and \(\mathsf {Greedy}\)) achieve impressive practical compression results, but the recursive character of those algorithms makes it hard to achieve strong theoretical results. To this end, this paper studies the approximation ratio of those algorithms for unary input strings, which is strongly related to the field of addition chains. We show that in this setting, \(\mathsf {RePair}\) and \(\mathsf {LongestMatch}\) produce equal size grammars that are by a factor of at most \(\log _2(3)\) larger than a smallest grammar. We also provide a matching lower bound. The main result of this paper is a new lower bound for \(\mathsf {Greedy}\) of 1.348..., which improves the best known lower bound for arbitrary (not necessarily unary) input strings.