Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space

DOI10.1007/978-3-540-77050-3_35zbMath1135.68374OpenAlexW1947022961MaRDI QIDQ5458854

Kunihiko Sadakane, Wing-Kin Sung, Jesper Jansson

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_35

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (1)

Space-efficient construction of Lempel-Ziv compressed text indexes

Cites Work

• Unnamed Item
• Improved behaviour of tries by adaptive branching
• New trie data structures which support very fast search operations
• Indexing text using the Ziv--Lempel trie
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Succinct Representation of Balanced Parentheses and Static Trees
• Optimal bounds for the predecessor problem
• Squeezing succinct data structures into entropy bounds
• Linear Algorithm for Data Compression via String Matching
• Compression of individual sequences via variable-rate coding
• Algorithms and Computation
• Combinatorial Pattern Matching
• Probabilistic behavior of asymmetric level compressed tries
• Algorithms and Computation

This page was built for publication: Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space