Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-05-04
2004-08-31
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C707S793000
Reexamination Certificate
active
06785699
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to search engines, and particularly to prefix comparators that identify common subprefixes of two prefixes.
BACKGROUND OF THE INVENTION
In application Ser. No. 09/679,313 we describe flexible search engine for a sorted binary search tree for perfect matching. The search tree is used for searching large databases, such as integrated circuit cell libraries. In application Ser. No. 09/679,209, we describe a prefix search tree that identifies the longest common subprefix of two prefixes. The prefix search tree is useful in a sorted binary search tree, such as that described in application Ser. No. 09/679,313 to perform search functions.
As described in application Ser. No. 09/679,209, the prefixes have values based on two rules: First, a bit string A is smaller in value than a bit string AB (AB>A), where bit string B contains at least one finite bit. Thus, if A is “1101” and B is “110”, AB is “1101110” which is greater than “1101”. Second, where two bit strings have the same length, a bit string A1B, comprising bit string A followed by binary “1” and a bit string B, is greater in value than the same bit string A followed by binary “0” and bit string C, regardless of the values of B and C. Thus, ALB>AOC. Thus if A is “1101”, B is “000”, and C is “110”, A1B is “11011000” and AOC is “11010110” and 11011000>11010110.
The prefix search tree of application Ser. No. 09/679,209 employs a mask that defines one or more common subprefixes between a binary search prefix and the binary prefixes in the vertices of the tree. A mask is derived for each prefix in the tree based on an ordered comparison of the prefix at the vertex and the search prefix. The masks are used for searching the prefix tree to find the prefix in the tree with longest matching subprefix to the search prefix.
Generation of the masks in application Ser. No. 09/679,209 requires considerable memory and processing allocation. The present invention is in an improved prefix comparator that significantly improves the performance of the mask generation.
SUMMARY OF THE INVENTION
In accordance with the invention, a longest common subprefix of two binary prefixes p
1
and p
2
is identified. The prefixes are defined as bit strings ip
1
and n
1
, and ip
2
and n
2
, respectively, where ip
1
and ip
2
are of equal length and represent the prefixes p
1
and p
2
, and n
1
and n
2
represent the actual lengths of p
1
and p
2
. Word portions ip
1
and ip
2
are processed to form a bit string having first bit values corresponding to the matching bits of ip
1
and ip
2
. Word portions n
1
and n
2
are decoded to define the length of the shortest of the prefixes p
1
and p
2
. The results of the processing of ip
1
and ip
2
and decoding of n
1
and n
2
derive a mask having a consecutive string of most significant bits having the first bit value identifying the matching subprefixes of ip
1
and ip
2
.
A preferred aspect of the present invention is the provision of a circuit that performs the functions of the invention. Preferably, the circuit is implemented as a triangle semiconductor device.
Alternatively the present invention may be implemented as a computer readable program that is embedded in a computer usable medium to cause a computer to identify common subprefixes of two binary words and to carry out the processes of the invention.
REFERENCES:
patent: 6047283 (2000-04-01), Braun
patent: 6505270 (2003-01-01), Voelkel et al.
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 6633548 (2003-10-01), Bachmutsky et al.
Andreev Alexander E.
Scepanovic Ranko
LSI Logic Corporation
Ngo Chuong Dinh
Westman Champlin & Kelly
LandOfFree
Prefix comparator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prefix comparator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix comparator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3358884