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 (and transitions between them) of a trie becomes large so that space cost may not be acceptable for a huge key set. In order to resolve this disadvantage, this paper presents a new scheme, called ''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. The theoretical and experimental observations show that the method presented is more practical than existing ones considering the use of dynamic key sets, storing information of keys, and compression of transitions.