Research articles
ScienceAsia (): 65-73 |doi:
10.2306/scienceasia1513-1874...065
A new heuristic for full trie minimization
Meng Zhanga, Dequan Chena, Yi Zhangb, Guohang Songa,*
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
Download PDF
67 Downloads 1594 Views
| a |
College of Computer Science and Technology, Jilin University, Changchun 130012 China |
| b |
College of Electronics and Computer Science, Jilin Jianzhu University, Changchun 130118 China |
* Corresponding author, E-mail: songguohang1988@sina.com
Received 25 Feb 2018, Accepted 6 Mar 2019
|
