Finger Search in Grammar-Compressed Strings

Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

192 Downloads (Pure)

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 many popular compression schemes. Given a grammar, the random access problem is to compactly represent the grammar while supporting random access, that is, given a position in the original uncompressed string report the character at that position. In this paper we study the random access problem with the finger search property, that is, the time for a random access query should depend on the distance between a specified index f, called the finger, and the query index i. We consider both a static variant, where we first place a finger and subsequently access indices near the finger efficiently, and a dynamic variant where also moving the finger such that the time depends on the distance moved is supported.

Let n be the size the grammar, and let N be the size of the string. For the static variant we give a linear space representation that supports placing the finger in O(log(N)) time and subsequently accessing in O(log(D)) time, where D is the distance between the finger and the accessed index. For the dynamic variant we give a linear space representation that supports placing the finger in O(log(N)) time and accessing and moving the finger in O(log(D) + log(log(N))) time. Compared to the best linear space solution to random access, we improve a O(log(N)) query bound to O(log(D)) for the static variant and to O(log(D) + log(log(N))) for the dynamic variant, while maintaining linear space. As an application of our results we obtain an improved solution to the longest common extension problem in grammar compressed strings. To obtain our results, we introduce several new techniques of independent interest, including a novel van Emde Boas style decomposition of grammars.
Original languageEnglish
Title of host publicationProceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Number of pages16
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2016
Article number36
ISBN (Print) 978-3-95977-027-9
DOIs
Publication statusPublished - 2016
Event36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) - Chennai, India
Duration: 13 Dec 201615 Dec 2016
Conference number: 36
http://www.fsttcs.org/

Conference

Conference36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Number36
CountryIndia
CityChennai
Period13/12/201615/12/2016
Internet address
SeriesLeibniz International Proceedings in Informatics
Volume65
ISSN1868-8969

Cite this

Bille, P., Christiansen, A. R., Cording, P. H., & Gørtz, I. L. (2016). Finger Search in Grammar-Compressed Strings. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) [36] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, Vol.. 65 https://doi.org/10.4230/LIPIcs.FSTTCS.2016.36