Abstract
Trie is a data structure with many applications. High space usage is the major drawback of the trie. The order-containing trie optimizes the space usage of the trie by rearranging symbols of strings. We present a new heuristic for building order-containing tries with small space. The heuristic is based on the following observation. For a given string set P, by moving the symbols on a position to the first position of strings in P, the trie of the resulting pattern set may have fewer nodes than that of the trie of P. We present an algorithm to find positions that yield the smallest such trie. The algorithm runs in O( P ) time and uses O(|P| log|P|) bits space, where P is the number of total symbols in P, and |P| is the number of patterns in P. By using this method recursively in trie constructions, we can build a trie with fewer nodes than the trie of P. We conduct several experiments that show the new heuristic builds smaller tires than previous work.
Introduction
The trie (or prefix tree) is a fundamental data structure in bioinformatics, IP routing, and dictionary management. However, its primary weakness is space inefficiency due to a high memory footprint. While path-compressed variants like Patricia trees exist, another powerful approach is the Order-Containing Trie (O-Trie).
In a standard trie, characters are checked in a fixed sequence (e.g., 1st, then 2nd, then 3rd). An O-Trie relaxes this constraint, allowing different paths to check characters in different orders. For example, checking the 3rd character before the 1st might lead to more shared prefixes and fewer total nodes.
Finding the optimal character order to minimize nodes is an NP-complete problem. Previous heuristics were either computationally expensive or lacked guarantees on size reduction. This paper introduces a new, linear-time heuristic that guarantees a data structure never larger—and often significantly smaller—than a standard trie.
Methodology: The ML Heuristic and Cholevel Algorithm
The authors propose a recursive construction method based on a new heuristic function called ML (Minimal Level).
The Core Observation
The fundamental insight is that moving a character from position $i$ to the first position in a set of strings can drastically change the number of nodes in the resulting trie. By identifying the position that yields the smallest trie, we can optimize the structure level by level.
The Cholevel Algorithm
To avoid the $O(\|P\|^2)$ brute-force approach of building a trie for every possible position, the authors developed the "Cholevel" algorithm. This algorithm efficiently calculates the node count for any starting position without fully constructing the trie. It leverages:
- Least Common Ancestor (LCA) properties to determine "encounter distances" between nodes.
- Range Minimum Query (RMQ) data structures to calculate the number of nodes in $O(1)$ time after a linear-time preprocessing step.
This logic is applied recursively. At each node, the algorithm chooses the "best" remaining character position to test next, effectively building the O-Trie level-by-level in $O(\|P\|)$ time.
Experimental Results
The researchers evaluated their heuristic using synthetic and real-world datasets, including DNA sequences (Homo sapiens chromosome 21) and English text (Mona Lisa Overdrive).
- Binary Data ($|\Sigma|=2$): Achieved up to a 21% reduction in node count.
- DNA Data: Achieved an 11-12% reduction compared to a standard trie.
- English Text: Showed a more modest 3-4% reduction due to the larger alphabet size.
The effectiveness of the heuristic is inversely proportional to the alphabet size, with an average improvement ratio of approximately $1/(2|\Sigma|)$. This makes the technique particularly powerful for low-entropy data like DNA or binary streams.
Conclusion and Future Work
The new heuristic consistently outperforms both standard tries and previous greedy methods while maintaining linear-time complexity. While space savings diminish as alphabet sizes grow very large (e.g., UTF-8), the method provides a robust guarantee of non-expansion. Future work may explore how non-linear character ordering affects search speed and whether O-Tries can be optimized to "skip" certain input symbols entirely during lookups.
Summary updated