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

Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura

Abstract

This paper introduces the Packed Compact Trie (packed c-trie), a high-performance evolution of the classic Patricia tree optimized for the modern word RAM model of computation. By leveraging bit-level parallelism to process multiple characters simultaneously, the packed c-trie achieves a 5% to 20% speedup in query times over standard implementations while maintaining a near-optimal space footprint. This structure is particularly well-suited for large-scale online string processing and data compression tasks.

Introduction

In string algorithms, the trie is a foundational data structure for storing and searching sets of strings. The compact trie (or Patricia tree) improves upon the basic trie by merging non-branching paths into single edges, significantly reducing space requirements. However, traditional implementations process strings character-by-character, which is inefficient on modern 64-bit architectures where multiple characters (especially from small alphabets like DNA) can fit into a single machine word.

While "packed string matching" techniques exist for linear sequences, they typically fail at branching nodes within a trie. The authors address this limitation by introducing a structure that maintains the speed of word-packed processing even in the presence of frequent branching.

Methodology

The packed c-trie utilizes several innovations to bridge the gap between word packing and tree navigation:

Micro-trie Decomposition

The core innovation is the partitioning of the large compact trie into "micro c-tries" of height $\alpha$, where $\alpha$ is the number of characters that fit into one machine word. This layered approach allows the algorithm to handle chunks of the string as single units.

Decomposition of a compact trie into micro c-tries of height $\alpha$.

Word RAM Operations and Hashing

Within these micro-tries, the algorithm treats sequences of characters as large integers. Using bitwise XOR and "Most Significant Bit" (MSB) operations, the system can find the Lowest Common Ancestor (LCA) of two strings—identifying exactly where they diverge—in $O(1)$ constant time. To manage transitions between these micro-tries, the authors employ advanced data structures like y-fast tries or Beame-Fich structures. Additionally, a hashing-based variant (PCThash) allows the algorithm to skip matching sections in expected constant time per word, rather than per character.

Experimental Evaluation

The authors evaluated their implementation against a standard Patricia tree (CT) and two versions of their packed trie (PCTxor and PCThash) using eight diverse real-world datasets from the Pizza&Chili Corpus, including DNA sequences, natural language text (DBLP, English), MIDI music data (Pitches), and source code.

Key Results

The experimental results demonstrate that the PCThash implementation consistently outperforms the classic Patricia tree in query speed.

Performance comparison of the packed compact trie (PCT) against the standard compact trie (CT) across various datasets.

As shown in the table above, the PCThash variant achieved a 5% to 20% speedup in query times across most datasets. Furthermore, construction times were generally faster or comparable to standard tries, particularly on the DBLP, pitches, and urls datasets. Theoretically, the structure supports updates and queries in $O(\frac{m}{\alpha} \log \log n)$ expected time, a significant improvement over the standard $O(m)$ character-by-character approach.

Discussion and Conclusion

The packed c-trie represents a significant advancement in string data structures by successfully applying sub-linear processing techniques to branching structures. While the use of boundary nodes and hash tables increases the node count (up to 46% in the DNA dataset), the performance gains in query and construction speed justify the overhead for many online applications.

The authors successfully applied this structure to accelerate Online Sparse Suffix Tree construction and LZ-Double factorization. Future work will focus on reducing the memory overhead associated with node creation and exploring performance on larger alphabets.

Summary updated

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...

Figure