Techniques for phonetic searching

• US 7,062,482 B1
• Filed: 09/26/2001
• Issued: 06/13/2006
• Est. Priority Date: 02/22/2001
• Status: Active Grant

• Current Assignee: Walgreen Co. (Walgreens Boots Alliance Incorporated)
• Original Assignee: Drugstore.com Incorporated (Walgreens Boots Alliance Incorporated)
• Inventors: Madan, Umesh, Eppley, Geary
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US09/965,541
• Time in Patent Office: 1,721 Days
• Field of Search: 707 1- 5, 707/10, 707/100, 704/8, 704/200, 704/251, 704/277, 704/1, 704/4, 704/252, 704/10
• US Class Current: 707/758
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G10L 13/08 Text analysis or generation of parameters for speech synthesis out of text, e.g. grapheme to phoneme translation, prosody generation or stress or intonation determination
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

In a network providing for electronic commerce, a computer system provides a user with access to a set of electronic commerce pages, category pages and databases for locating products electronically. To locate products electronically, the user performs a search using multiple words. The search terms in the search request are converted to canonical phonetic forms, and a phonetic keyword search based on the canonical phonetic forms is performed. The phonetic keyword search is then used to generate search results.

Claims

1. A computer implemented method comprising:

receiving a search request at a server from a client over a network, the search request including one or more search terms;

for each search term in the search request, the server identifying all diphthongs within each search term;

the server determining one or more canonical representations for each diphthong based on pronunciation of each diphthong, the one or more canonical representations being in text formats;

the server generating one or more canonical phonetic forms for each search term based on possible spellings of the one or more canonical representations of each diphthong, including

determining whether any canonical representations exist for one or more letters of each search term, and

including in the one or more canonical phonetic forms of any canonical representations exist for one or more letters of each search term;

the server performing a phonetic keyword search in a database coupled to the server for each canonical phonetic form of the search term, wherein the canonical phonetic search is performed based on the canonical phonetic forms generated from the canonical representation of both letters and diphthongs of the search request; and

the server generating an indication of search results based, on the phonetic keyword search.

2. The method of claim 1, further comprising performing an initial search in the database based on each search term of the search request, wherein identifying all diphthongs, determining one or more canonical representations, generating one or more canonical phonetic forms and performing a phonetic keyword search are performed when the initial search fails to produce a proper result.

3. The method of claim 2, wherein each canonical phonetic form is limited up to six characters.

4. The method of claim 1, wherein performing a phonetic keyword search comprises:

identifying one or more keywords the canonical phonetic forms of the search term; and

searching the canonical phonetic forms of the one or more keywords for the canonical phonetic forms of the search term.

5. The method of claim 1, further comprising:

determining the possible pronunciation for each vowel contained within the search request in consideration of letters before and after the respective vowel;

generating one or more canonical representations for each of the possible pronunciation of each vowel, wherein the one or more canonical representations do not contain the respective vowel itself; and

generating the one or more canonical phonetic forms based on possible spellings of the one or more canonical representations of the respective vowel.

6. The method of claim 4, further comprising:

prior to receiving the search request, generating canonical phonetic forms for a plurality of predetermined keywords including the one or more keywords of the canonical phonetic forms of the search term; and

storing the canonical phonetic forms of the predetermined keywords in the database prior to receiving the search request.

7. The method of claim 6, wherein generating the canonical phonetic forms of the keywords comprises:

identifying one or more diphthongs within each predetermined keyword;

determining one or more canonical representations for at least one of the one or more diphthongs within each predetermined keyword;

determining whether any canonical representations exist for one or more letters within each predetermined keyword; and

generating one or more canonical phonetic forms of each predetermined keywords from the canonical representations of the at least one diphthong within the keyword and any canonical representation of the one or more letters within the keyword.

8. The method of claim 3, further comprising ignoring any letter that is not a letter and ignoring a second consecutive appearance of an identical letter when determining the canonical representation of the respective letter of the search term.

9. A machine-readable medium having stored thereon sequences of instructions that, when executed, cause one or more electronic systems to:

receive a search request at a server from a client over a network, the search request including one or more search terms;

for each search terms in the search request, identify all diphthongs within each search term;

determine one or more canonical representations for each diphthong based on pronunciation of each diphthong, the one or more canonical representations being in text formats;

generate one or more canonical phonetic forms for each search term based on possible spellings of the one or more canonical representations of each diphthong, including

determining whether any canonical representations exist for one or more letters of each search term, and

including in the one or more canonical phonetic forms of any canonical representations exist for one or more letters of each search term;

perform a phonetic keyword search in a database for each canonical phonetic form of the search term, wherein the canonical phonetic search is performed based on the canonical phonetic forms generated from the canonical representation of both letters and diphthongs of the search request; and

generate an indication of search results based on the phonetic keyword search.

10. The machine-readable medium of claim 9, wherein the sequences of instructions that cause the one or more electronic systems to perform an initial search in the database based on each search term of the search request, wherein identifying all diphthongs, determining one or more canonical representations, generating one or more canonical phonetic forms, and performing a phonetic keyword search are performed when the initial search fails to produce a proper result.

11. The machine-readable medium of claim 10, wherein each canonical phonetic form is limited up to six characters.

12. The machine-readable medium of claim 9, wherein the sequences of instructions that cause the one or more electronic systems to perform a phonetic keyword search comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

identify one or more keywords the canonical phonetic forms of the search term; and

search canonical phonetic forms of keywords for one or more of the canonical phonetic forms of the search term.

13. The machine-readable medium of claim 9, wherein the sequences of instructions, when executed, further cause the one or more electronic systems to:

determine the possible pronunciation for each vowel contained within the search request in consideration of letters before and after the respective vowel;

generate one or more canonical representation for each of the possible pronunciation of each vowel, wherein the one or more canonical representations do not contain the respective vowel itself; and

generate the one or more canonical phonetic forms based on possible spellings of the one or more canonical representations of the respective vowel.

14. The machine-readable medium of claim 12, further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

prior to receiving the search request, generate canonical phonetic forms for a plurality of predetermined keywords including the one or more keywords of the canonical phonetic forms of the search term, and

store the canonical phonetic forms of the predetermined keywords in a database prior to receiving the search request.

15. The machine-readable medium of claim 14, wherein the sequences of instructions that cause the one or more electronic systems to generate canonical phonetic forms of the keywords comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

identify one or more diphthongs within each predetermined keyword;

determine one or more canonical representations for at least one of the one or more diphthongs within each predetermined keyword;

determine whether any canonical representations exist for one or more letters within each predetermined keyword; and

generate one or more canonical phonetic forms of each predetermined keywords from the canonical representations of the at least one diphthong within the keyword and any canonical representation of the one or more letters within the keyword.

16. The machine-readable medium of claim 11, wherein the sequences of instructions further cause the system to ignore any letter that is not a letter and ignore a second consecutive appearance of an identical letter when determining the canonical representation of the respective letter of the search term.

17. An apparatus comprising:

a processor; and

a memory coupled to the processor, the memory having stored thereon sequences of instructions that, when executed, cause one or more electronic systems to

receive a search request at a server from a client over a network, the search request including one or more search terms,

for each search term in the search request, identify all diphthongs within each search term,

determine one or more canonical representations for each diphthong based on pronunciation of each diphthong, the one or more canonical representations being in text formats,

generate one or more canonical phonetic forms for each search term based on possible spellings of the one or more canonical representations of each diphthong, including

determining whether any canonical representations exist for one or more letters of each search term, and

including in the one or more canonical phonetic forms of any canonical representations exist for one or more letters of each search term,

perform a phonetic keyword search in a database for each canonical phonetic form of the search term, wherein the canonical phonetic search is performed based on the canonical phonetic forms generated from the canonical representation of both letters and diphthongs of the search request, and

generate an indication of search results based on the phonetic keyword search.

18. The apparatus of claim 17, wherein the sequences of instructions that cause the one or more electronic systems to perform an initial search in the database based on each search term of the search request, wherein identifying all diphthongs, determining one or more canonical representations, generating one or more canonical phonetic forms, and performing a phonetic keyword search are performed when the initial search fails to produce a proper result.

19. The apparatus of claim 18, wherein each canonical phonetic form is limited up to six characters.

20. The apparatus of claim 17, wherein the sequences of instructions that cause the one or more electronic systems to perform a phonetic keyword search comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

identify one or more keywords the canonical phonetic forms of the search term; and

search the canonical phonetic forms of keywords for one or more of the canonical phonetic forms of the search term.

21. The apparatus of claim 17, wherein the sequences of when executed, further cause the one or more electronic systems to:

determine the possible pronunciation for each vowel contained within the search request in consideration of letters before and after the respective vowel;

generate one or more canonical representation for each of the possible pronunciation of each vowel, wherein the one or more canonical representations do not contain the respective vowel itself; and

generate the one or more canonical phonetic forms based on possible spellings of the one or more canonical representations of the respective vowel.

22. The apparatus of claim 20, further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

prior to receiving the search request, generate canonical phonetic forms for a plurality of keywords including the one or more keywords of the canonical phonetic forms of the search term, and

store the canonical phonetic forms of the predetermined keywords in a database prior to receiving the search request.

23. The apparatus of claim 22, wherein the sequences of instructions that cause the one or more electronic systems to generate canonical phonetic forms of the keywords comprise sequences of instructions that, when executed, cause the one or more electronic systems to

identify one or more diphthongs within each predetermined keyword,

determine one or more canonical representations for at least one of the one or more diphthongs within each predetermined keyword,

determine whether any canonical representations exist for one or more letters within each predetermined keyword, and

generate one or more canonical phonetic forms of the keywords from the canonical representations of the at least one diphthong within the keyword and any canonical representation of the one or more letters within each predetermined keyword.

24. The apparatus of claim 19, wherein the sequences of instructions further cause the system to ignore any letter that is not a letter and ignore a second consecutive appearance of an identical letter when determining the canonical representation of the respective letter of the search term.

25. A computer data signal embodied in a data communications medium shared among a plurality of network devices comprising sequences of instructions that, when executed, cause one or more electronic systems to:

receive a search request at a server from a client over a network, the search request including one or more search terms;

for each search term in the search request, identify all diphthongs within each search term;

determine one or more canonical representations for each diphthong based on pronunciation of each diphthong, the one or more canonical representations being in text formats;

generate one or more canonical phonetic forms for each search term based on possible spellings of the one or more canonical representations of each diphthong, including

determining whether any canonical representations exist for one or more letters of each search term, and

including in the one or more canonical phonetic forms of any canonical representations exist for one or more letters of each search term;

perform a phonetic keyword search in a database for each canonical phonetic form of the search term, wherein the canonical phonetic search is performed based on the canonical phonetic forms generated from the canonical representation of both letters and diphthongs of the search request; and

generate an indication of search results based on the phonetic keyword search.

26. The computer data signal of claim 25, wherein the sequences of instructions that cause the one or more electronic systems to perform an initial search in the database based on each search term of the search request, wherein identifying all diphthongs, determining one or more canonical representations, generating one or more canonical phonetic forms, and performing a phonetic keyword search are performed when the initial search fails to produce a proper result.

27. The computer data signal of claim 26, wherein each canonical phonetic form is limited up to six characters.

28. The computer data signal of claim 25, wherein the sequences of instructions that cause the one or more electronic systems to perform a phonetic keyword search comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

identify one or more keywords the canonical phonetic forms of the search term; and

search canonical phonetic forms of keywords for one or more of the canonical phonetic forms of the search term.

29. The computer data signal of claim 25, wherein the sequences of instructions, when executed, further cause the one or more electronic systems to:

determine the possible pronunciation for each vowel contained within the search request in consideration of letters before and after the respective vowel;

generate one or more canonical representation for each of the possible pronunciation of each vowel, wherein the one or more canonical representations do not contain the respective vowel itself; and

generate the one or more canonical phonetic forms based on possible spellings of the one or more canonical representations of the respective vowel.

30. The computer data signal of claim 28, further comprising sequences of instructions that, when executed, cause the one or more electronic systems to

generate prior to receiving the search request, canonical phonetic forms for a plurality of predetermined keywords including the one or more keywords of the canonical phonetic forms of the search term, and

store the canonical phonetic forms of the predetermined keywords in a database prior to receiving the search request.

31. The computer data signal of claim 30, wherein the sequences of instructions that cause the one or more electronic systems to generate the canonical phonetic forms of keywords comprise sequences of instructions that, when executed, cause the one or more electronic systems to:

identify one or more diphthongs within each predetermined keyword;

determine one or more canonical representations for at least one of the one or more diphthongs within each predetermined keyword;

determine whether any canonical representations exist for one or more letters within each predetermined keyword; and

generate one or more canonical phonetic forms of the keywords from the canonical representations of the at least one diphthong within the keyword and any canonical representation of the one or more letters within each predetermined keyword.

32. The computer data signal of claim 27, wherein the sequences of instructions further cause the system to ignore any letter that is not a letter and ignore a second consecutive appearance of an identical letter when determining the canonical representation of the respective letter of the search term.