Fingerprints in compressed strings

DOI10.1007/978-3-642-40104-6_13zbMATH Open1370.68060DBLPjournals/jcss/BilleGCSVV17arXiv1305.2777OpenAlexW2577924862WikidataQ60554414 ScholiaQ60554414MaRDI QIDQ2396828FDOQ2396828

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

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences, Lecture Notes in Computer Science (Search for Journal in Brave)

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(logNloglce)$ and $O(loglcelogloglce+loglogN)$ for SLPs and Linear SLPs, respectively. Here, $lce$ denotes the length of the LCE.

Full work available at URL: https://arxiv.org/abs/1305.2777

Recommendations

• Fingerprints in compressed strings
• Longest common extensions via fingerprinting
• Finger Search in Grammar-Compressed Strings
• Finger search in grammar-compressed strings
• A Faster Query Algorithm for the Text Fingerprinting Problem

zbMATH Keywords

longest common extensionsgrammar-compressed stringKarp-Rabin fingerprints

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Cites Work

• String matching in Lempel-Ziv compressed strings
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Compression of individual sequences via variable-rate coding
• Title not available (Why is that?)
• The level ancestor problem simplified
• Efficient randomized pattern-matching algorithms
• Title not available (Why is that?)
• A universal algorithm for sequential data compression
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Surpassing the information theoretic bound with fusion trees
• Finding level-ancestors in trees
• Title not available (Why is that?)
• Substring compression problems
• Fast Algorithms for Finding Nearest Common Ancestors
• Dynamic ordered sets with exponential search trees
• Title not available (Why is that?)
• Design and implementation of an efficient priority queue
• Faster Suffix Tree Construction with Missing Suffix Links
• Longest Common Extensions with Recompression.
• The string edit distance matching problem with moves
• The Smallest Grammar Problem
• Exact and Approximate Pattern Matching in the Streaming Model
• Self-Indexed Grammar-Based Compression
• Time-Space Trade-Offs for Longest Common Extensions
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• A Faster Grammar-Based Self-index
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Title not available (Why is that?)
• Compactly encoding unstructured inputs with differential compression
• Efficient algorithms for substring near neighbor problem
• Finger Search in Grammar-Compressed Strings

Cited In (8)

• Finger search in grammar-compressed strings
• Balancing straight-line programs for strings and trees
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Access, Rank, and Select in Grammar-compressed Strings
• Small-space LCE data structure with constant-time queries
• Balancing run-length straight-line programs
• Space-efficient conversions from SLPs
• Wheeler maps

This page was built for publication: Fingerprints in compressed strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396828)