Fingerprints in compressed strings
From MaRDI portal
DOI10.1016/j.jcss.2017.01.002zbMath1370.68060arXiv1305.2777WikidataQ60554414 ScholiaQ60554414MaRDI QIDQ2396828
Philip Bille, Inge Li Gørtz, Søren Vind, Benjamin Sach, Patrick Hagge Cording, Hjalte Wedel Vildhøj
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Exact and Approximate Pattern Matching in the Streaming Model