Patent ID: 7546281

Claim:
A method to reduce the size of a ternary data structure database, the method comprising the acts of: providing the database in a memory such that the database includes a listing of N rules, where N>=2, such that each rule (R) of the N rules represents a row of data in the database and has an associated integer index having a value of 0, 1, 2 . . . N and includes bit characters 0, 1 and * (wild card or don't care) representing values of bits included in each rule in the database; tagging each rule with a valid bit having an initial value of 1; processing the N rules using a redundancy test algorithm that identifies which rules of the database are included in other rules of the database and therefore should be deleted from the data base as being redundant, such that the redundancy test algorithm includes the following steps: step 1 setting an integer index i of rule Ri to initially be 0; step 2 setting an integer indexi j of rule Rj to initially be 0; step 3 if the valid bit of rule Rj=0, then go to step 6; step 4 if the integer index j=i, then go to step 6; step 5 if no bit of rule Ri having a value of 0 is positioned in rule Ri in a same bit position as a bit in rule Rj having a value of 1, AND if no bit of rule Ri having a value of 1 is positioned in rule Ri in a same bit position as a bit in rule Rj having a value of 0, AND if every bit of rule Ri having the a value of * is positioned in a same bit position as a bit in rule Rj having the value of *, then rule Ri is identified as being redundant relative to rule Rj such that the valid bit with which rule Ri is tagged is reset to 0, and go to step 7; step 6 if the integer index j<N−1, then increment j by 1 such that j:=j+1, and go to step 3; step 7 if the integer index i<N−1, then increment i by 1 such that i:=i+1, and go to step 2; step 8 END; deleting redundant rules Ri from the database for which an associated tagged valid bit has been reset to 0; processing remaining N rules of the database which have not been deleted as being redundant and which have a value of 1 for an associated tagged valid bit using a rule reduction algorithm to identify which of the remaining N rules are identical to other remaining N rules in all bit positions except exactly one bit position; and deleting from the database remaining N rules which have been identified as being identical to other remaining N rules in all bit positions except exactly one bit position.