Abstract
In grammarbased compression a string is represented by a contextfree grammar, also called a straightline 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 righthand 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 AVLgrammars 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 straightline 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 ith 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 SLPcompressed strings where one wants to access positions near to a prespecified 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 tfold 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 StraightLine Programs}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {45:145:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14626},
URN = {urn:nbn:de:0030drops146263},
doi = {10.4230/LIPIcs.ESA.2021.45},
annote = {Keywords: grammarbased compression, balancing, finger search}
}
Keywords: 

grammarbased compression, balancing, finger search 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 