Patent ID: 7933885

Claim:
A machine comprising a search engine for searching a database comprising a first sequence of distinguishing bit indexes and a sequence of keys together representing a first digital search tile, the search engine comprising: a plurality of first stage decoders configured to generate a first sequence of key indexes based on the first sequence of distinguishing bit indexes and a search key, each key index of first sequence of key indexes indentifying a preliminary candidate key in the sequence of keys; a distinguishing bit selection module coupled to the plurality of first stage decoders and configured to generate a second sequence of distinguishing bit indexes based on the first sequences of distinguishing bit indexes and the first sequence of key indexes, the second sequence of distinguishing bit indexes and the sequence of preliminary candidate keys together representing a second digital search trie; a second stage decoder coupled to the distinguishing bit selection module and configured to generate a second sequence of key indexes based on the search key and the second sequence of distinguishing bit indexes, each key index in the second sequence of key indexes indentifying a secondary candidate key in the sequence of keys having a matching prefix with the search key, wherein each first stage decoder of the plurality of first stage decoders comprises a matrix of interconnected cells configured to generate a subsequence of key indexes in the first sequence of key indexes, and the second stage decoder comprises a matrix of interconnected cells configured to generate the second sequence of key indexes; a priority encoder coupled to the second stage decoder and configured to select the last key index in the second sequence of key indexes; a key memory coupled to the priority encoder and configured to store the sequence of keys, the key memory further configured to select a candidate key in the sequence of keys based on the selected key index; a longest candidate prefix module coupled to the key memory and configured to identify a most significant distinguishing bit index between the search key and the selected candidate key; and a longest prefix match module coupled to the longest candidate prefix module and configured to identify a longest matching prefix key in the at least one secondary candidate key based on the most significant distinguishing bit index, the longest matching prefix key being the secondary candidate key of the at least one secondary candidate key having a longest matching prefix with the search key.