A method of compressing trie structures

A trie structure can immediately determine whether a desired key is in a given key set or not, and can find its longest match easily. Thanks to these attractive properties, a trie structure is frequently used for various fields, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie becomes large, so space requirements are not good for a huge key set. To resolve this disadvantage a new structure which reduces the total number of states in a traditional trie, called a double‐trie, is introduced in this paper. Insertion and deletion operations, as well as key retrieval for this double‐trie, are presented. The efficiency of this method is shown by the results of simulations for various key sets.