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

DOI10.1007/978-3-540-77050-3_35MaRDI QIDQ5458854zbMATH OpenOpenAlexFDO

Authors Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung

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

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

Recommendations

• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• An experimental study of compression methods for dynamic tries
• Dynamic index and LZ factorization in compressed space
• scientific article; zbMATH DE number 975330
• Fast Compressed Tries through Path Decompositions
• Fast compressed tries through path decompositions
• Fully dynamic data structure for LCE queries in compressed space
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Sublinear algorithms for approximating string compressibility

Cites work

• Algorithms and Computation
• Algorithms and Computation
• Combinatorial Pattern Matching
• Compression of individual sequences via variable-rate coding
• scientific article; zbMATH DE number 4045113 (Why is no real title available?)
• Improved behaviour of tries by adaptive branching
• Indexing text using the Ziv--Lempel trie
• Linear Algorithm for Data Compression via String Matching
• Log-logarithmic worst-case range queries are possible in space theta(N)
• New trie data structures which support very fast search operations
• Optimal bounds for the predecessor problem
• Probabilistic behavior of asymmetric level compressed tries
• Squeezing succinct data structures into entropy bounds
• Succinct representation of balanced parentheses and static trees

Cited in

(11)

• An experimental study of compression methods for dynamic tries
• Top tree compression of tries
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Fast compressed tries through path decompositions
• scientific article; zbMATH DE number 2185642 (Why is no real title available?)
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• Fast Compressed Tries through Path Decompositions
• scientific article; zbMATH DE number 975330 (Why is no real title available?)
• Space-efficient construction of Lempel-Ziv compressed text indexes
• Top Tree Compression of Tries.
• Compressed string dictionaries via data-aware subtrie compaction

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

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