Fingerprints in compressed strings
From MaRDI portal
Publication:2396828
DOI10.1016/j.jcss.2017.01.002zbMath1370.68060arXiv1305.2777WikidataQ60554414 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
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q42: Grammars and rewriting systems
68P05: Data structures
68W32: Algorithms on strings
Related Items
Small-space LCE data structure with constant-time queries, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Balancing run-length straight-line programs, Balancing straight-line programs for strings and trees, Finger search in grammar-compressed strings, Access, Rank, and Select in Grammar-compressed Strings
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