Patent ID: 8532988

Claim:
A non-transitory computer readable medium encoded with a computer program for executing a method for searching for an input symbol string among a set of symbol strings, comprising: creating a trie data structure of symbol strings, wherein the symbol strings are grouped into branches in such a manner that the symbol strings beginning with the same symbols belong to the same branch, and the symbol strings in the same branch divide into new branches at the symbols, from which onwards the symbols strings differ from each other, receiving an input formed of an input symbol string, proceeding from the starting point of the trie data structure along a branch to a calculation point indicated by the next symbol, calculating distances at the calculation point between a sample symbol string formed by the symbols of the calculation point of the branch in question and the calculation points preceding it and the input symbol string by comparing these in alternative ways, calculating at the calculation point also the smallest possible length difference corresponding to each distance that indicates how much the length of the remaining part of the input symbol string not examined in the distance calculation differs from the lengths remaining in the symbols strings passing through the calculation point, and calculating on the basis of each distance and corresponding length difference a reference value, selecting repeatedly the next branch to follow to the calculation point indicated by the next symbol, at which said calculation is repeated for the new calculation point, said selection of the next branch being performed in such a manner that next the routine proceeds from the calculation point, from which the lowest reference value has been obtained as result, after the calculation has terminated, selecting one or more symbol strings having the shortest distance to the input symbol string on the basis of the performed calculations, and using the selected symbol string(s) to produce a response.