Fingerprints in Compressed Strings

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

doi:10.1007/978-3-642-40104-6_13

Fingerprints in Compressed Strings

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

Department of Applied Mathematics and Computer Science

University of Warwick

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

440 Downloads (Orbit)

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 language	English
Title of host publication	Algorithms and Data Structures : 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings
Publisher	Springer
Publication date	2013
Pages	146-157
ISBN (Print)	978-3-642-40103-9
ISBN (Electronic)	978-3-642-40104-6
DOIs	https://doi.org/10.1007/978-3-642-40104-6_13
Publication status	Published - 2013
Event	Algorithms And Data Structures Symposium (WADS 2013) - London, Ontario, Canada Duration: 12 Aug 2013 → 14 Aug 2013 http://www.wads.org/

Conference

Conference	Algorithms And Data Structures Symposium (WADS 2013)
Country/Territory	Canada
City	London, Ontario
Period	12/08/2013 → 14/08/2013
Internet address	http://www.wads.org/

Series	Lecture Notes in Computer Science
Volume	8037
ISSN	0302-9743

Access to Document

10.1007/978-3-642-40104-6_13

1305

http://arxiv.org/abs/1305.2777

OpenUrl availability

Full text

Cite this

@inproceedings{a457eb05058c4c50877a9606ae420e9a,

title = "Fingerprints in Compressed Strings",

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.",

author = "Philip Bille and Cording, {Patrick Hagge} and G{\o}rtz, {Inge Li} and Benjamin Sach and Vildh{\o}j, {Hjalte Wedel} and Vind, {S{\o}ren Juhl}",

year = "2013",

doi = "10.1007/978-3-642-40104-6_13",

language = "English",

isbn = "978-3-642-40103-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "146--157 ",

booktitle = "Algorithms and Data Structures",

note = "Algorithms And Data Structures Symposium (WADS 2013) ; Conference date: 12-08-2013 Through 14-08-2013",

url = "http://www.wads.org/",

}

Bille, P, Cording, PH, Gørtz, IL, Sach, B, Vildhøj, HW & Vind, SJ 2013, Fingerprints in Compressed Strings. in Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer, Lecture Notes in Computer Science, vol. 8037, pp. 146-157 , Algorithms And Data Structures Symposium (WADS 2013), London, Ontario, Canada, 12/08/2013. https://doi.org/10.1007/978-3-642-40104-6_13

Fingerprints in Compressed Strings. / Bille, Philip; Cording, Patrick Hagge; Gørtz, Inge Li et al.
Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer, 2013. p. 146-157 (Lecture Notes in Computer Science, Vol. 8037).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Fingerprints in Compressed Strings

AU - Bille, Philip

AU - Cording, Patrick Hagge

AU - Gørtz, Inge Li

AU - Sach, Benjamin

AU - Vildhøj, Hjalte Wedel

AU - Vind, Søren Juhl

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40104-6_13

DO - 10.1007/978-3-642-40104-6_13

M3 - Article in proceedings

SN - 978-3-642-40103-9

T3 - Lecture Notes in Computer Science

SP - 146

EP - 157

BT - Algorithms and Data Structures

PB - Springer

T2 - Algorithms And Data Structures Symposium (WADS 2013)

Y2 - 12 August 2013 through 14 August 2013

ER -