Design of a Compact Data Structure for the Patricia Trie

摘要

In many applications, information retrieval is a very important research field. In several key strategies, the bi- nary 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 struc- tures 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 nor- mal binary trie into a compact bit stream.