IEICE TRANSACTIONS on Fundamentals
Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
Summary :
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 nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσ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(klog 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( rac{m}{alpha} f(k,n))$ worst-case time and in $O( rac{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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1785-1793
- Publication Date
- 2017/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1785
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Takuya TAKAGI
Hokkaido University
Shunsuke INENAGA
Kyushu University
Kunihiko SADAKANE
University of Tokyo
Hiroki ARIMURA
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takuya TAKAGI, Shunsuke INENAGA, Kunihiko SADAKANE, Hiroki ARIMURA, "Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 9, pp. 1785-1793, September 2017, doi: 10.1587/transfun.E100.A.1785.
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 nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσ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(klog 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( rac{m}{alpha} f(k,n))$ worst-case time and in $O( rac{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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1785/_p
Copy
@ARTICLE{e100-a_9_1785,
author={Takuya TAKAGI, Shunsuke INENAGA, Kunihiko SADAKANE, Hiroki ARIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing},
year={2017},
volume={E100-A},
number={9},
pages={1785-1793},
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 nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσ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(klog 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( rac{m}{alpha} f(k,n))$ worst-case time and in $O( rac{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.},
keywords={},
doi={10.1587/transfun.E100.A.1785},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1785
EP - 1793
AU - Takuya TAKAGI
AU - Shunsuke INENAGA
AU - Kunihiko SADAKANE
AU - Hiroki ARIMURA
PY - 2017
DO - 10.1587/transfun.E100.A.1785
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - 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 nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσ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(klog 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( rac{m}{alpha} f(k,n))$ worst-case time and in $O( rac{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.
ER -
English
