| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 45 Number 3
Volume 45 Number 2
Volume 45 Number 1
Volume 44 Number 6
Volume 44 Number 5
Volume 44 Number 4
Earlier issues
Volume 44 Number 6 Volume 45 Number 1 Volume 45 Number 2

previous article next article 1

Research articles

ScienceAsia 45(2019): 65-73 |doi: 10.2306/scienceasia1513-1874.2019.45.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

44 Downloads 226 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