Fingerprints in compressed strings

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

doi:10.1016/j.jcss.2017.01.002

Fingerprints in compressed strings

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

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

University of Bristol

Research output: Contribution to journal › Journal article › Research › peer-review

332 Downloads (Pure)

Abstract

In this paper we show how to construct a data structure for a string S of size N compressed into a context-free grammar of size n that supports efficient Karp–Rabin fingerprint queries to any substring of S. 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(log⁡N) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(log⁡log⁡N) query time. We extend the result to solve the longest common extension problem in query time O(log⁡Nlog⁡ℓ) and O(log⁡ℓlog⁡log⁡ℓ+log⁡log⁡N) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.

Original language	English
Journal	Journal of Computer and System Sciences
Volume	86
Pages (from-to)	171-180
ISSN	0022-0000
DOIs	https://doi.org/10.1016/j.jcss.2017.01.002
Publication status	Published - 1 Jun 2017

Keywords

Grammar compressed string
Karp–Rabin fingerprints
Longest common extensions

Access to Document

10.1016/j.jcss.2017.01.002

1305Submitted manuscript, 182 KB

OpenUrl availability

Full text

Cite this

@article{11864fc74f11414289862ccc3918daad,

title = "Fingerprints in compressed strings",

abstract = "In this paper we show how to construct a data structure for a string S of size N compressed into a context-free grammar of size n that supports efficient Karp–Rabin fingerprint queries to any substring of S. 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(log⁡N) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(log⁡log⁡N) query time. We extend the result to solve the longest common extension problem in query time O(log⁡Nlog⁡ℓ) and O(log⁡ℓlog⁡log⁡ℓ+log⁡log⁡N) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.",

keywords = "Grammar compressed string, Karp–Rabin fingerprints, Longest common extensions",

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

year = "2017",

month = jun,

day = "1",

doi = "10.1016/j.jcss.2017.01.002",

language = "English",

volume = "86",

pages = "171--180",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press",

}

TY - JOUR

T1 - Fingerprints in compressed strings

AU - Bille, Philip

AU - Gørtz, Inge Li

AU - Cording, Patrick Hagge

AU - Sach, Benjamin

AU - Vildhøj, Hjalte Wedel

AU - Vind, Søren

PY - 2017/6/1

Y1 - 2017/6/1

N2 - In this paper we show how to construct a data structure for a string S of size N compressed into a context-free grammar of size n that supports efficient Karp–Rabin fingerprint queries to any substring of S. 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(log⁡N) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(log⁡log⁡N) query time. We extend the result to solve the longest common extension problem in query time O(log⁡Nlog⁡ℓ) and O(log⁡ℓlog⁡log⁡ℓ+log⁡log⁡N) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.

AB - In this paper we show how to construct a data structure for a string S of size N compressed into a context-free grammar of size n that supports efficient Karp–Rabin fingerprint queries to any substring of S. 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(log⁡N) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(log⁡log⁡N) query time. We extend the result to solve the longest common extension problem in query time O(log⁡Nlog⁡ℓ) and O(log⁡ℓlog⁡log⁡ℓ+log⁡log⁡N) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.

KW - Grammar compressed string

KW - Karp–Rabin fingerprints

KW - Longest common extensions

U2 - 10.1016/j.jcss.2017.01.002

DO - 10.1016/j.jcss.2017.01.002

M3 - Journal article

AN - SCOPUS:85009813096

SN - 0022-0000

VL - 86

SP - 171

EP - 180

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -