For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Design of a Compact Data Structure for the Patricia Trie
Masami SHISHIBORI Makoto OKADA Tooru SUMITOMO Jun-ichi AOE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
information retrieval, trie method, patricia trie, data structures, pre-order bit stream,
Full Text: PDF(761.2KB)>>
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.