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

arXiv: https://arxiv.org/abs/1602.00422 · HTML: https://mlsanity.com/paper/1602.00422/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [Contextual Biasing to Improve Domain-specific Custom Vocabulary Audio Transcription without Explicit Fine-Tuning of Whisper Model](https://mlsanity.com/paper/2410.18363/) (2024)

## Abstract (arXiv)

In this paper, 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σ + O(k log n) bits of space and supports fast pattern matching queries and updates, where σ is the size of an alphabet. 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(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(fracmα f(k,n)) worst-case time and in O(fracmα + 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. As an application of our packed c-trie, we show that the sparse suffix tree for a string of length n over prefix codes with k sampled positions, such as evenly-spaced and word delimited sparse suffix trees, can be constructed online in O((fracnα + k) f(k,n)) worst-case time and O(fracnα + k f(k,n)) expected time with n log σ + O(k log n) bits of space. When k = O(fracnα), by using the state-of-the-art dynamic predecessor/successor data structures, we obtain sub-linear time construction algorithms using only O(fracnα) bits of space in both cases. We also discuss an application of our packed c-tries to online LZD factorization.