Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
Lists
Only you see this
Abstract
We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in \(n \log \sigma + O(k \log n)\) bits of space and supports fast pattern matching queries and updates, where \(\sigma \) is the alphabet size. Assume that \(\alpha = \log _\sigma n\) letters are packed in a single machine word on the standard word RAM model, and let f(k, n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1, n] in \(O(k \log n)\) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in \(O(\frac{m}{\alpha } f(k,n))\) worst-case time and in \(O(\frac{m}{\alpha } + f(k,n))\) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.
BibTeX
@article{takagi2017packed,
author = {Takuya Takagi and Shunsuke Inenaga and Kunihiko Sadakane and Hiroki Arimura},
title = {{Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing}},
journal = {IEICE Trans. Fundam. Electron. Commun. Comput. Sci.},
year = {2017},
url = {https://openreview.net/forum?id=6xmRVtSh5T},
}Loading related content...