Fingerprints in compressed strings

DOI10.1016/j.jcss.2017.01.002zbMath1370.68060DBLPjournals/jcss/BilleGCSVV17arXiv1305.2777OpenAlexW2577924862WikidataQ60554414 ScholiaQ60554414MaRDI QIDQ2396828

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)

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

zbMATH Keywords

longest common extensionsgrammar-compressed stringKarp-Rabin fingerprints

Mathematics Subject Classification ID

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

Related Items (6)

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

Cites Work

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

This page was built for publication: Fingerprints in compressed strings