A Structure-Shared Trie Compression Method

Trie, a well-known searching algorithm, is a basic and important part of various computer applications such as information retrieval, natural language processing, database system, compiler, and computer network. Although a merit of trie structure is its searching speed, the nave version of trie structure size may not be acceptable when the key set is very large. To reduce its size, several methods were proposed. This paper proposes an alternative approach using a new trie structure called, structure-shared trie (SS-trie). The main idea is to reduce unused space using shared common structure and bit compression. Three techniques are used: (1) path compression, (2) structure sharing, and (3) node compression. A number of experiments are conducted to investigate trie size, sharing rate, and average depth of the proposed method in comparison with binary search, nave trie, PAT, and LC-trie. The result shows that our method outperforms other methods.