Linked dynamic tries with applications to LZ-compression in sublinear time and space

DOI10.1007/s00453-013-9836-6zbMath1325.68075OpenAlexW2135649699MaRDI QIDQ2350903

Jesper Jansson, Wing-Kin Sung, Kunihiko Sadakane

Publication date: 25 June 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9836-6

zbMATH Keywords

data structuresLZ-compressiondynamic trielongest common prefix query

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

Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ c-trie++: a dynamic trie tailored for fast prefix searches ⋮ Dynamic Path-decomposed Tries ⋮ Engineering Practical Lempel-Ziv Tries ⋮ m-Bonsai: A Practical Compact Dynamic Trie ⋮ LZ78 Compression in Low Main Memory Space ⋮ Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Constructing LZ78 tries and position heaps in linear time for large alphabets ⋮ Succinct dynamic cardinal trees

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Space-efficient construction of Lempel-Ziv compressed text indexes
• Improved behaviour of tries by adaptive branching
• New trie data structures which support very fast search operations
• The design of dynamic data structures
• A simple optimal representation for balanced parentheses
• Indexing text using the Ziv--Lempel trie
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• A space and time efficient algorithm for constructing compressed suffix arrays
• A linear-time algorithm for a special case of disjoint set union
• Lempel-Ziv index for \(q\)-grams
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• Succinct Representation of Balanced Parentheses and Static Trees
• The string B-tree
• An Improved Succinct Representation for Dynamic k-ary Trees
• Indexing compressed text
• Squeezing succinct data structures into entropy bounds
• Compression of individual sequences via variable-rate coding
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Probabilistic behavior of asymmetric level compressed tries