Please use this identifier to cite or link to this item:
Title: Random access to grammar-compressed strings and trees
Authors: Bille, P.
Landau, G. M.
Raman, Rajeev
Sadakane, K.
Satti, S. R.
Weimann, O.
First Published: 5-May-2015
Publisher: Society for Industrial and Applied Mathematics
Citation: SIAM Journal on Computing, 44(3), 513–539. (27)
Abstract: Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel-Ziv family, Run-Length Encoding, Byte-Pair Encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let S be a string of length N compressed into a context-free grammar S of size n. We present two representations of S achieving O(log N) random access time, and either O(n·αk(n)) construction time and space on the pointer machine model, or O(n) construction time and space on the RAM. Here, αk(n) is the inverse of the k th row of Ackermann’s function. Our representations also efficiently support decompression of any substring in S: we can decompress any substring of length m in the same complexity as a single random access query and additional O(m) time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern P with at most k errors in time O(n(min{|P|k, k^4 + |P|} + log N) + occ), where occ is the number of occurrences of P in S. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy paths in grammars.
DOI Link: 10.1137/130936889
ISSN: 0097-5397
eISSN: 1095-7111
Version: Publisher version
Status: Peer-reviewed
Type: Journal Article
Rights: Archived with reference to SHERPA/RoMEO and publisher website. © 2015, Society for Industrial and Applied Mathematics Version of record:
Description: AMS subject classifications. 68P05, 68P30
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
130936889.pdfPublisher version631.74 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.