Confusion set-base method and apparatus for pruning a predetermined arrangement of indexed identifiers

A method of matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the method comprising the steps of:

• a) providing a recognized identifier on the basis of the input identifier;
• b) determining an index code for the recognized identifier;
• c) determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier;
• d) accessing the reference identifiers associated with the reference index codes determined in step c), the accessed reference identifiers forming a candidate subset of reference identifiers;
• e) searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier;
• and
• g) selecting a matching reference identifier as corresponding to the input identifier wherein the step c) comprises:
• i) arranging the reference index codes into a predetermined data structure, wherein the predetermined data structure comprises a plurality of nodes, each node representing at least a portion of at least one of the plurality of reference index codes;
• ii) traversing the predetermined data structure, wherein moving from any one of the nodes to another node along a first predetermined direction represents a first value, and wherein moving from any one of the nodes to another node along a second predetermined direction represents a second value;
• iii) calculating a travel path value for each node based on at least one of the first predetermined value and the second predetermined value, each reference index code being associated with a corresponding travel path value;
• iv) comparing a value of each bit position of each travel path value with a value of each corresponding bit position of the index code for the reference identifier;
• v) determining for each travel path value an amount of bit positions having a different value than those in corresponding bit positions of the index code for the recognized identifier;
• and
• vi) including in a candidate set of reference index codes those reference index codes associated with travel path values for which the associated amount of bit positions having a different value than the corresponding bit positions of the index code for the recognized identifier is no more than the predetermined distance.

An apparatus for matching an input identifier to one of a set of reference identifiers, each of the reference identifiers being associated with one of a plurality of reference index codes, the apparatus comprising:

• a) first means for providing a recognized identifier on the basis of the input identifier;
• b) first means for determining an index code for the recognized identifier, the input identifier being provided by a user;
• c) second means for determining which of the plurality of reference index codes are within a predetermined distance of the index code for the recognized identifier;
• d) means for accessing the reference identifiers associated with the reference index codes determined by the second means for determining, the accessed reference identifiers forming a candidate subset of reference identifiers;
• e) means for searching the candidate set of reference identifiers for a reference identifier that matches the recognized identifier;
• and
• f) means for selecting a matching reference identifier as corresponding to the input identifier, wherein each reference identifier is a set of alphanumeric characters.

An apparatus, comprising:

• a processing device;
• a recognizing device coupled to the processing device, the recognizing device including an input for receiving an input identifier, the input identifier being provided by a user;
• a reference identifier database coupled to the processing device, the reference identifier database including at least one reference identifier, each reference identifier being associated with one of a plurality of reference index codes;
• an index pruning module coupled to the processing device;
• a confusion matrix memory coupled to the processing device;
• and
• a confusion set generating module coupled to the processing device.