License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.45
URN: urn:nbn:de:0030-drops-146263
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14626/
Ganardi, Moses
Compression by Contracting Straight-Line Programs
Abstract
In grammar-based compression a string is represented by a context-free grammar, also called a straight-line program (SLP), that generates only that string. We refine a recent balancing result stating that one can transform an SLP of size g in linear time into an equivalent SLP of size ?(g) so that the height of the unique derivation tree is ?(log N) where N is the length of the represented string (FOCS 2019). We introduce a new class of balanced SLPs, called contracting SLPs, where for every rule A → β₁ … β_k the string length of every variable β_i on the right-hand side is smaller by a constant factor than the string length of A. In particular, the derivation tree of a contracting SLP has the property that every subtree has logarithmic height in its leaf size. We show that a given SLP of size g can be transformed in linear time into an equivalent contracting SLP of size ?(g) with rules of constant length. This result is complemented by a lower bound, proving that converting SLPs into so called α-balanced SLPs or AVL-grammars can incur an increase by a factor of Ω(log N).
We present an application to the navigation problem in compressed unranked trees, represented by forest straight-line programs (FSLPs). A linear space data structure by Reh and Sieber (2020) supports navigation steps such as going to the parent, left/right sibling, or to the first/last child in constant time. We extend their solution by the operation of moving to the i-th child in time ?(log d) where d is the degree of the current node.
Contracting SLPs are also applied to the finger search problem over SLP-compressed strings where one wants to access positions near to a pre-specified finger position, ideally in ?(log d) time where d is the distance between the accessed position and the finger. We give a linear space solution for the dynamic variant where one can set the finger in ?(log N) time, and then access symbols or move the finger in time ?(log d + log^(t) N) for any constant t where log^(t) N is the t-fold logarithm of N. This improves a previous solution by Bille, Christiansen, Cording, and Gørtz (2018) with access/move time ?(log d + log log N).
BibTeX - Entry
@InProceedings{ganardi:LIPIcs.ESA.2021.45,
author = {Ganardi, Moses},
title = {{Compression by Contracting Straight-Line Programs}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {45:1--45:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14626},
URN = {urn:nbn:de:0030-drops-146263},
doi = {10.4230/LIPIcs.ESA.2021.45},
annote = {Keywords: grammar-based compression, balancing, finger search}
}
|
Keywords: |
|
grammar-based compression, balancing, finger search |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
