Patent attributes
The disclosed invention presents a method and apparatus to a one dimensional prefix search problem. The problem consists looking up the best match to a word out of a table of one-dimensional prefixes. The invention addresses the problems with prior art of high power consumption, large silicon chip area for implementation and slow search speed. The prefix entries are divided in several subgroups. A function is described that can be efficiently implemented to determine which of these subgroups the presented word will find a best match in. Thus, it is necessary to search only this small subgroup of prefixes. This saves on power consumption as well as area. An efficient hardware embodiment of this idea which can search at a very high speed is also presented. The applications for this invention could include internet routing, telephone call routing and string matching.
