SUBSTITUTION, INSERTION, AND DELETION (SID) DISTANCE AND VOICE IMPRESSIONS DETECTOR (VID) DISTANCE

• US 20120109636A1
• Filed: 10/29/2010
• Published: 05/03/2012
• Est. Priority Date: 10/29/2010
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Iqbal, Syed Talat, Muthusamy, Mareeswari, Mundhra, Abhigyan
• Granted Patent: US 8,548,800 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/237 Lexical tools

Abstract

A device may receive user input, select two strings to compare based on the user input, obtain a first set of keyboard codes for a first of the two strings, obtain a second set of keyboard codes for a second of the two strings, and determine a distance between the two strings based on the first and the second set of keyboard codes. In addition, the device may send a result associated with determining the distance to another device, store the result in a storage device, or display the result.

Claims

1. A method comprising:

receiving user input;

selecting two strings to compare based on the user input;

obtaining a first set of keyboard codes for a first of the two strings;

obtaining a second set of keyboard codes for a second of the two strings;

determining a distance between the two strings based on the first and the second set of keyboard codes; and

sending a result associated with determining the distance to another device, storing the result in a storage device, or displaying the result.

2. The method of claim 1, wherein selecting the two strings includes:

selecting two words in English.

3. The method of claim 1, wherein obtaining the first set of keyboard codes includes:

for each of the symbols of the first string, obtaining a code that is assigned to the symbol based on a keyboard layout.

5. The method of claim 1, wherein determining the distance includes:

determining a minimum number of edits to convert the first string into the second string.

6. The method of claim 5, wherein determining a minimum number of edits includes:

determining a number of insertions, deletions, and transpositions of symbols to convert the first string into the second string.

7. The method of claim 6, wherein determining the distance further includes:

subtracting, from the number of edits, a correction factor for each of the edits.

8. The method of claim 7, wherein determining the distance further includes:

adjusting a result of the subtraction for any insertion operation of a symbol next to a null character that indicates a termination of a string.

9. The method of claim 7, wherein determining the distance further includes:

looking up a correction factor by using a difference, between one of the first set of keyboard codes and a corresponding one of the second set of keyboard codes, as a key into a translation table.

10. The method of claim 9, wherein the translation table includes:

correction factors that decrease exponentially as a function of physical distance between keys of a keyboard layout, the keys corresponding to symbols of the two strings.

11. The method of claim 9, wherein the translation table includes:

correction factors for two mismatching symbols which are associated with a keyboard, the mismatching symbols being associated with keys of different rows of the keyboard.

12. The method of claim 1, wherein obtaining the distance includes:

obtaining a phonetic distance between the two strings.

13. The method of claim 12, wherein obtaining a phonetic distance includes:

obtaining a first phonetic word for the first of the two strings;

obtaining a second phonetic word for the second of the two strings; and

determining a distance between the first and second phonetic words.

14. The method of claim 13, wherein obtaining the first phonetic word includes:

looking up consonant impressions of the first string, wherein each of the consonant impressions belongs to a bucket.

15. The method of claim 14, wherein looking up the consonant impressions includes:

classifying each of consonants of the first string as a consonant impression that belongs to a bucket, wherein determining the distance between the first and second phonetic words includes determining a consonant distance between consonant impressions of the first and second phonetic words.

16. The method of claim 15, wherein determining the consonant distance includes:

outputting a distance indicating a difference between consonant impressions when the consonant impression of the first phonetic word and a corresponding consonant impression of the second phonetic word do not belong to a same bucket;

outputting a distance indicating a minor difference between consonant impressions when the consonant impression of the first phonetic word and the corresponding consonant impression of the second phonetic word belong to a same bucket, wherein the consonant impressions of the first and second phonetic words are not the same; and

outputting a distance indicating sameness of the constant impressions when the consonant impressions of the first and second phonetic words are the same.

17. The method of claim 13, wherein determining a distance between the first and second phonetic words includes:

looking up vowel impressions corresponding to vowels of the first string and the second string; and

obtaining a Euclidean distance between the vowel impressions.

18. The method of claim 17, wherein looking up vowel impressions includes:

looking up codes that represent vectors corresponding to the vowel impressions.

19. The method of claim 18, wherein the vectors include the same endpoints and different directions.

4. The method of clam 3, wherein obtaining a code includes:

looking up a code that is assigned to the symbol based on a QWERTY keyboard layout.

20. A method comprising:

receiving user input;

selecting two strings to compare based on the user input;

obtaining a first set of phonetic codes for a first of the two strings;

obtaining a second set of phonetic codes for a second of the two strings;

determining a phonetic distance between the two strings based on the first and the second set of phonetic codes; and

sending a result associated with determining the phonetic distance to another device, storing the result in a storage device, or displaying the result.

21. A device comprising:

a storage unit to store information;

a transmitter to send information to a remote device;

a display screen to display information; and

one or more processors to;

select two strings;

obtain a first set of codes for a first of the two strings;

obtain a second set of codes for a second of the two strings;

determine a distance between the two strings based the first and the second set of codes; and

send a result associated with determining the distance to the remote device, store the result in the storage unit, or show the result on the display screen.

22. The device of claim 21, wherein when the one or more processors obtain a first set of codes, the one or more processors are configured to:

obtain vowel impressions and consonant impressions of the two strings.

23. The device of claim 22, wherein when the one or more processors determine the distance, the one or more processors are configured to:

obtain a vowel distance by calculating an Euclidean distance between one of the vowel impressions of the first string and a corresponding one of the vowel impressions of the second string; and

obtain a consonant distance based on the consonant impressions.

24. The device of claim 22, wherein when the one o more processors determine the distance, the one or more processors are further configured to:

normalize the vowel distance; and

add the normalized vowel distance to the consonant distance

25. The device of claim 21, wherein the two strings include two words in English.

26. The device of claim 21, wherein the first set of codes includes codes that are assigned to symbols associated with keys of a keyboard.

27. The device of claim 21, wherein when the one or more processors determine a distance, the one or more processors are further configured to:

determine a number of deletions, insertions, substitutions, and transposition operations needed to convert the first of the two strings into the second of the two strings.

28. The device of claim 27, wherein when the one or more processors are further configured to:

subtract correction factors from the number of deletions, insertions, substitutions, and transposition operations.

29. The device of claim 28, wherein the correction factors include:

a value obtained by a lookup

30. The device of claim 28, wherein the one or more processors are further configured to execute an application configured to:

suggest a spelling correction based on the result;

or

suggest the second of the two strings as a replacement string for the first of the two strings.

31. The device of claim 30, wherein the application includes at least one of:

a word processing application;

a web browser application;

a text messaging application;

or

a speech-to-text application.