Method, apparatus, and system for modifying substitution costs

An apparatus comprising:

• a computer readable storage medium storing a computer readable program;
• a processor executing the computer readable program, the computer readable program comprising
• a substitution cost module calculating a substitution cost between a first character of a first string and a second character of a second string;
• a spatial vector module calculating a spatial vector between the first character and the second character from a location of a first key representing the first character on a keyboard and a location of a second key representing the second character on the keyboard and modifying the substitution cost if the spatial vector is less than a spatial threshold;
• and
• an edit distance module calculating an edit distance between the first string and the second string using the modified substitution cost for the substitution cost of substituting the first character with the second character.

A method comprising:

• calculating, by use of a processor, a substitution cost between a first character of a first string and a second character of a second string;
• calculating, by use of a processor, a spatial vector between the first character and the second character from a location of a first key representing the first character on a keyboard and a location of a second key representing the second character on the keyboard;
• modifying, by use of a processor, the substitution cost if the spatial vector is less than a spatial threshold;
• and
• calculating, by use of a processor, an edit distance between the first string and the second string using the modified substitution cost for the substitution cost of substituting the first character with the second character.