A key search algorithm using the compact Patricia trie

In several key strategies, the Patricia trie has the shallowest trie by eliminating all nodes which have only one arc, and these nodes are called single descendant nodes. For this reason, this trie can retrieve the key faster than any other trie strategies. This trie, however, must store information concerning the eliminated nodes, and thus if this trie structure is implemented, the required storage is large. This paper shows the retrieval algorithm using the compact Patricia trie, which is represented by the bit stream.