Fingerprints in Compressed Strings

Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj, Søren Juhl Vind

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

300 Downloads (Pure)

Abstract

The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a data structure for a string S of size N compressed by a context-free grammar of size n that answers fingerprint queries. That is, given indices i and j, the answer to a query is the fingerprint of the substring S[i,j]. We present the first O(n) space data structures that answer fingerprint queries without decompressing any characters. For Straight Line Programs (SLP) we get O(logN) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(loglogN) query time. Hence, our data structures has the same time and space complexity as for random access in SLPs. We utilize the fingerprint data structures to solve the longest common extension problem in query time O(logNlogℓ) and O(logℓloglogℓ + loglogN) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures : 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings
PublisherSpringer
Publication date2013
Pages146-157
ISBN (Print)978-3-642-40103-9
ISBN (Electronic)978-3-642-40104-6
DOIs
Publication statusPublished - 2013
EventAlgorithms And Data Structures Symposium (WADS 2013) - London, Ontario, Canada
Duration: 12 Aug 201314 Aug 2013
http://www.wads.org/

Conference

ConferenceAlgorithms And Data Structures Symposium (WADS 2013)
CountryCanada
CityLondon, Ontario
Period12/08/201314/08/2013
Internet address
SeriesLecture Notes in Computer Science
Volume8037
ISSN0302-9743

Cite this

Bille, P., Cording, P. H., Gørtz, I. L., Sach, B., Vildhøj, H. W., & Vind, S. J. (2013). Fingerprints in Compressed Strings. In Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings (pp. 146-157 ). Springer. Lecture Notes in Computer Science, Vol.. 8037 https://doi.org/10.1007/978-3-642-40104-6_13