Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
From MaRDI portal
Publication:2819506
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
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
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
