Method for generating a trie having a reduced number of trie blocks

摘要

A method of generating a trie having a reduced number of trie blocks. An algorithm identifies data to be to be added to a trie. The algorithm separates the data into portions having sizes based, at least in part, on sizes related to trie blocks in the trie. The algorithm indicates in a trie entry of a first trie block, wherein a first portion of the prefix identifies the trie entry, that a second portion of the prefix is stored in a pruned-trie entry. The algorithm indicates in the trie entry of the first trie block a location of the pruned-trie entry, and stores the second portion of the prefix in the pruned-trie entry. The algorithm indicates in the pruned-trie entry the position the second portion occupies relative to other portions of the data.