Design of a Compact Data Structure for the Patricia Trie

Masami SHISHIBORI  Makoto OKADA  Tooru SUMITOMO  Jun-ichi AOE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.4   pp.364-371
Publication Date: 1998/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Databases
Keyword: 
information retrieval,  trie method,  patricia trie,  data structures,  pre-order bit stream,  

Full Text: PDF(761.2KB)>>
Buy this Article




Summary: 
In many applications, information retrieval is a very important research field. In several key strategies, the binary trie is famous as a fast access method able to retrieve keys in order. Especially, a Patricia trie gives the shallowest trie by eliminating all nodes which have only one arc, and it requires the smallest storage among the other trie structures. If trie structures are implemented, however, the greater the number of the registered keys, the larger storage is required. In order to solve this problem, Jonge et al. proposed a method to change the normal binary trie into a compact bit stream. This paper proposes the improved trie representation for the Patricia trie, as well as the methods for searching and inserting the key on it. The theoretical and experimental results, using 50,000 Japanese nouns and 50,000 English words, show that this method generates 25-39 percent shorter bit streams than the traditional method. This method, thus, enables us to provide more compact storage and faster access than the traditional method.