Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

DOI10.1007/978-3-319-44543-4_17zbMath1478.68066arXiv1602.00422OpenAlexW2268618959MaRDI QIDQ2819506

Shunsuke Inenaga, Hiroki Arimura, Takuya Takagi, Kunihiko Sadakane

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.00422

Mathematics Subject Classification ID

Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Dynamic Path-decomposed Tries, Compressed string dictionaries via data-aware subtrie compaction, Unnamed Item, Practical Implementation of Space-Efficient Dynamic Keyword Dictionaries, Top tree compression of tries

Uses Software

• PATRICIA

Cites Work

• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• New trie data structures which support very fast search operations
• Surpassing the information theoretic bound with fusion trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• On-line construction of suffix trees
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Optimal Packed String Matching
• Alphabet-Dependent String Searching with Wexponential Search Trees
• LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
• Sparse and Truncated Suffix Trees on Variable-Length Codes
• The string B-tree
• Dynamic ordered sets with exponential search trees
• Dictionary matching and indexing with errors and don't cares
• Compression of individual sequences via variable-rate coding
• On-Line Linear-Time Construction of Word Suffix Trees
• Dynamic LCA Queries on Trees