A trie compaction algorithm for a large set of keys

A trie structure is frequently used for various applications, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie (and transitions between them) becomes large, so that the space cost may not be acceptable for a huge key set. In order to resolve this disadvantage, this paper presents a new scheme, called a “two-trie”, that enables us to perform efficient retrievals, insertions and deletions for the key sets. The essential idea is to construct two tries for both front and rear compressions of keys, which is similar to a DAWG (directed acyclic word-graph). The approach differs from a DAWG in that the two-trie approach presented can uniquely determine information corresponding to keys while a DAWG cannot. For an efficient implementation of the two-trie, two types of data structures are introduced. Theoretical and experimental observations show that the method presented is more practical than existing ones considering the use of dynamic key sets, information storage of keys and compression of transitions