Efficiency masked matching
Methods and apparatus for reducing the search space processed by mask matching methods. The search space is reduced by grouping the candidate bit patterns into groups and subgroups that have internal bit agreement between the members. By only applying the mask matching methods to a select number of groups selected by their bit agreement with the target bit pattern, the computation time and memory requirement of the mask matching method is reduced.
1. A method of increasing the efficiency of a process for finding a match between a target bit pattern and at least one of a plurality of candidate bit patterns, the method comprising:
a) dividing said candidate bit patterns into specific groups such that for every group, members of that group have bit agreement with every other member in said group;
b) applying said process only to groups whose members have bit agreement with said target bit pattern; and
wherein said dividing is accomplished by:
a1) defining a working bit position;
a2) grouping said candidate bit patterns based on bit values at said bit position such that for every group all members in that group have the same bit value at said bit position;
a3) defining a new working bit position;
a4) applying step a1)–a3) to every group such that members of resulting subgroups have bit agreement at all bit positions up to the new working bit position; and
a5) applying steps a2)–a4) to all resulting subgroups such that final resulting subgroups have bit agreement at all bit positions,
wherein each new working bit position is subsequent to its preceding working bit position.
2. A method of increasing the efficiency of a process for finding a match between a target bit pattern and at least one of a plurality of candidate bit patterns, the method comprising:
a) dividing said candidate bit pattern into search space groups, each group having an aggregate number of members lesser that the total aggregate number of candidate bit patterns;
b) applying said process only to groups whose members are in bit agreement with the target bit pattern on at least a first bit position; and
wherein said dividing is accomplished by:
a1) defining a working bit position;
a2) grouping said candidate bit patterns based on bit values at said bit position such that for every group all members in that group have the same bit value at said bit position;
a3) defining a new working bit position;
a4) applying steps a1)–a3) to every group such that members of resulting subgroups have bit agreement at all bit positions up to the new working bit position; and
a5) applying steps a2)–a4) to all resulting subgroups such that final resulting subgroups have bit agreement at all bit positions,
wherein each new working bit position is subsequent to its preceding working bit position.
3. A method of increasing the efficiency of a process for finding a match between a target bit pattern and at least one of a plurality of candidate bit patterns, the method comprising:
a) grouping said candidate bit patterns based on a value of a specific bit in a specific bit position in said candidate bit patterns;
b) discarding candidate bit patterns which have a specific bit in a specific bit position whose value does not match the value of the corresponding bit in the target bit pattern;
c) repeating steps a)–b) to the remaining candidate bit patterns with different bit positions until the number of remaining candidate bit patterns is at a minimum; and
d) applying said process to the remaining candidate bit patterns.
4. A system for matching a target bit pattern with at least one of a plurality of candidate bit patterns, the system comprising:
dividing means for dividing said candidate bit patterns into specific groups such that for every group, members of that group have bit agreement with every other member in said group;
mask matching means for matching said target bit pattern with at least one of said candidate bit patterns, said mask matching means including being applied only to groups whose members are in bit agreement with the target bit pattern on at least a first bit position; and
wherein said dividing means executes the following method;
a1) defining a new working bit position;
a2) grouping said candidate bit patterns based on bit values at said bit position such that for every group all members in that group have the same bit value at said bit position;
a3) defining a new working bit position;
a4) applying steps a1)–a3) to every group such that members of resulting subgroups gave bit agreement at all bit positions up to the new working bit position; and
a5) applying steps a2)–a4) to all resulting subgroups such that final resulting subgroups have bit agreement at all bit positions,
wherein each new working bit position is subsequent to its preceding working bit position.
5. Computer readable media having encoded thereon computer readable and computer executable code for executing a method for increasing the efficiency of a process for finding a match between a target bit pattern and at least one of a plurality of given candidate bit patterns, said method comprising;
a) grouping said candidate bit patterns based on a value of a specific bit in a specific bit position in said candidate bit patterns;
b) discarding candidate bit patterns which have a specific bit in the specific bit position whose value does not match the value of the corresponding bit in the target bit pattern;
c) repeating steps a)–b) to the remaining candidate bit patterns with different bit positions until the number of remaining candidate bit patterns is at a minimum; and
d) applying said process to the remaining candidate bit patterns.