Patent ID: 6873993

Claim:
An apparatus for identifying one or more portions of data in a database for comparison with a query input by a user, the query and the portions of data each comprising a sequence of sub-word units, said apparatus comprising: a memory for storing data defining a plurality of sub-word unit classes, each class comprising sub-word units that are confusable with other sub-word units in the same class; a memory for storing an index having a plurality of entries, each entry having an associated identifier for identifying the entry and each entry comprising: a key associated with the entry and which is related to the identifier for the entry in a predetermined manner; and a number of pointers which point to portions of data in the database which correspond to the key associated with the entry, wherein each key comprises a sequence of sub-word unit classifications which is derived from a corresponding sequence of sub-word units appearing in the database by classifying each of the sub-word units in the sequence into one of the plurality of sub-word unit classes; means for classifying each of the sub-word units in the input query into one of the plurality of sub-word unit classes and for defining one or more sub-sequences of query sub-word unit classifications; means for determining a corresponding identifier for an entry in the index for each of the one or more sub-sequences of query sub-word unit classifications; means for comparing the key associated with each of the determined identifiers determined by said determining means with the corresponding sub-sequence of query sub-word unit classifications; and means for retrieving one or more pointers from the index in accordance with the output of said comparing means, which one or more pointers identify the one or more portions of data in the database for comparison with the input query.