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

Takuya TAKAGI; Shunsuke INENAGA; Kunihiko SADAKANE; Hiroki ARIMURA

doi:10.1587/transfun.E100.A.1785

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

Takuya TAKAGI, Shunsuke INENAGA, Kunihiko SADAKANE, Hiroki ARIMURA

Full Text Views

0

Share
Cite this

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

online text indexing, packed string matching, sparse suffix trees, dynamic predecessor dictionaries

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://globals.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 -