Please use this identifier to cite or link to this item:
Title: Random Access to Grammar-Compressed Strings
Authors: Bille, Philip
Landau, Gad M.
Raman, Rajeev
Sadakane, Kunihiko
Satti, Srinivasa Rao
Weimann, Oren
First Published: 2011
Presented at: The Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, California
Start Date: 23-Jan-2011
End Date: 25-Jan-2011
Publisher: Society for Industrial and Applied Mathematics (SIAM)
Citation: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 373-389
Abstract: 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(logN) random access time, and either O(n · α[subscript k](n)) construction time and space on the pointer machine model, or 0(n) construction time and space on the RAM. Here, α[subscript k](n) is the inverse of the k[superscript 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[superscript 4] + |P|}+logN)+occ), where occ is the number of occurrences of P in S. Finally, we are able to generalize our results to navigation and other operations on grammar-compressed 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.
ISBN: 0898719933
Version: Publisher Version
Type: Conference Paper
Rights: Copyright © 2011, SIAM. Archived with permission of the publisher.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
SODA11_030_billep.pdfPublished (publisher PDF)1.22 MBAdobe PDFView/Open

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