METHOD, APPARATUS, AND SYSTEM FOR MODIFYING SUBSTITUTION COSTS

• US 20100251105A1
• Filed: 03/31/2009
• Published: 09/30/2010
• Est. Priority Date: 03/31/2009
• Status: Abandoned Application

• Current Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Original Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Inventors: Ganey, Harriss Christopher Neil, Zawacki, Jennifer Greenwood, Stewart, Aaron Michael, Dubs, Justin Tyler
• Application Number:
  US12/415,695
• Publication Number:
  US 20100251105A1
• Time in Patent Office: Days
• US Class Current: 715/257
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A method, apparatus, and system are disclosed for modifying substitution cost. A substitution cost module calculates a substitution cost between a first character of a first string and a second character of a second string. A spatial vector module calculates 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. The spatial vector module modifies the substitution cost if the spatial vector is less than a spatial threshold. An edit distance module calculates 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.

Claims

1. A computer readable storage medium comprising a computer readable program stored on a tangible storage device for modifying substitution cost, wherein the computer readable program when executed on a computer causes the computer to:

calculate a substitution cost between a first character of a first string and a second character of a second string;

calculate 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;

modify the substitution cost if the spatial vector is less than a spatial threshold; and

calculate 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.

2. The computer readable storage medium of claim 1, wherein the modification of the substation cost c is calculated as k₁*c where k₁ is a constant.

3. The computer readable storage medium of claim 1, wherein the modification of the substation cost c is calculated as c*k₂*(v/v_max)² where k₂ is a constant, v is a length of the spatial vector from the first key to the second key and v_max is a longest spatial vector from the first key to any other key on the keyboard.

4. The computer readable storage medium of claim 1, wherein modification of the substation cost c is calculated as k₃*(1−

a)*c where a is an area of a user touch location within an area of the second key divided by a total area of the user touch location and k₃ is a constant.

5. The computer readable storage medium of claim 1, wherein the computer readable program further causes the computer to:

modify the first string to the second string in response to the edit distance;

log each user touch location on the keyboard for a plurality of modified first strings;

calculate a user adjustment vector from the plurality of logged user touch locations; and

modify the spatial vector with the user adjustment vector.

6. The computer readable storage medium of claim 1, wherein the keyboard is a touch screen keyboard.

7. The computer readable storage medium of claim 1, wherein the keyboard is an optical projection on a surface.

8. 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.

9. The apparatus of claim 8, wherein the modification of the substation cost c is calculated as k₁*c where k₁ is a constant.

10. The apparatus of claim 8, wherein the modification of the substation cost c is calculated as c*k₂*(v/v_max)² where k₂ is a constant, v is a length of the spatial vector from the first key to the second key and v_max is a longest spatial vector from the first key to any other key on the keyboard.

11. The apparatus of claim 8, wherein modification of the substation cost c is calculated as k₃*(1−

a)*c where a is an area of a user touch location within an area of the second key divided by a total area of the user touch location and k₃ is a constant.

12. The apparatus of claim 8, the substitution cost module further modifying the first string to the second string in response to the edit distance and the computer readable program further comprising:

a touch location module logging each user touch location on the keyboard for a plurality of modified first strings and calculating a user adjustment vector from the plurality of logged user touch locations; and

a user adjustment module modifying the spatial vector with the user adjustment vector.

13. The apparatus of claim 8, wherein the keyboard is a touch screen keyboard.

14. The apparatus of claim 8, wherein the keyboard is an optical projection on a surface.

15. 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.

16. The method of claim 15, wherein the modification of the substation cost c is calculated as k₁*c where k₁ is a constant.

17. The method of claim 16, wherein k₁ is in the range of 0.5 to 0.67.

18. The method of claim 15, wherein the modification of the substation cost c is calculated as c*k₂*(v/v_max)² where k₂ is a constant, v is a length of the spatial vector from the first key to the second key and v_max is a longest spatial vector from the first key to any other key on the keyboard.

19. The method of claim 15, wherein modification of the substation cost c is calculated as k₃*(1−

a)*c where a is an area of a user touch location within an area of the second key divided by a total area of the user touch location and k₃ is a constant.

20. The method of claim 15, further comprising:

logging each user touch location on the keyboard for a plurality of modified first strings;

calculating a user adjustment vector from the plurality of logged user touch locations; and

modifying the spatial vector with the user adjustment vector.