Level Compressed Tries for Longest Prefix Matching with Minimum Number of Nodes for a Given Maximum Height

In this paper we present a variant of the path and level com- pressed trie that can store non pre x-free sets of strings.We also study how to limit the height of it, while main- taining optimal size. The ability to limit the height is particularly important since it also limits the number of memory accesses needed for a search operation. The min- imum height is proportional to the length of the longest chain of pre xes in the set to be represented. If this can be bounded, the data structure can be e ciently implemented in a pipelined hardware architecture, where the length of the pipeline puts a hard limit on the height of the trie. We also discuss a simple language for describing path and level compressed tries, and use it to describe an algorithm to control the height of a trie while maintaining optimal size. The algorithm uses dynamic programming and runs in O

Keywords:

trie , path compression , level compression , optimal size