Phonetic sorting and searching

• US 6,408,270 B1
• Filed: 10/06/1998
• Issued: 06/18/2002
• Est. Priority Date: 06/30/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Garber, David G.
• Primary Examiner(s): Korzuch, William
• Assistant Examiner(s): Azad, Abul K.
• Application Number:
  US09/167,416
• Time in Patent Office: 1,351 Days
• Field of Search: 704/251, 704/252, 704/253, 704/254, 704/231, 704/242, 704/270.1
• US Class Current: 704/251
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method of searching keyword phrases based on a search phrase includes a step of ordering the search phrase among the plurality of keyword phrases based on phoneme sequences of the search phrase and the keyword phrases, in accordance with a predefined phonetic search order. The search order is defined so that similar sounding phonemes are adjacent each other. Furthermore, sounds are ordered beginning with sounds made at the front of the mouth and proceeding in order with sounds made farther and farther back in the mouth. When searching for a particular search phase, the method includes returning any matching keyword phrase, as well as any keyword phrases that are adjacent the search phrase in the predefined phonetic search order.

Claims

1. A method of identifying keyword phrases based on a search phrase, comprising the following steps:

identifying phoneme sequences of the search phrase and of the keyword phrases;

ordering the search phrase among the keyword phrases based on the identified phoneme sequences of the search phrase and the keyword phrases, in accordance with a phonetic search order in which similar sounding phonemes are adjacent each other;

identifying at least one of the keyword phrases that is adjacent the search phrase in the phonetic search order.

2. A method as recited in claim 1, wherein the identifying step comprises identifying at least a pair of the keyword phrases that are adjacent the search phrase in the phonetic search order.

3. A method as recited in claim 1, wherein the phrases are represented by characters, and wherein the ordering step comprises:

changing the characters of the phrases in accordance with a pre-defined character mapping;

sorting the phrases alphabetically after changing the characters of the phrases;

wherein the pre-defined character mapping establishes the phonetic search order in accordance with an alphabetic order of the characters.

4. A method as recited in claim 1, wherein the phrases are represented by characters, and wherein the ordering step comprises:

changing the characters of the phrases in accordance with a pre-defined character mapping;

wherein the mapping indicates at least the following character changes;

W to A;

WW to A;

BB to B;

P to C;

PP to C;

V to D;

VV to D;

F to E;

FF to E;

PH to E;

TH to F;

D to G;

DD to G;

T to H;

TT to H;

J to I;

JJ to I;

CH to J;

Z to K;

S to L;

SH to M;

SS to L;

G to N;

GG to N;

C to O;

CC to O;

CK to O;

K to O;

KK to O;

Q to O;

X to P;

XX to P;

GH to Q;

H to Q;

HH to Q;

L to R;

LL to R;

R to S;

RR to S;

M to T;

MM to T;

N to U;

NN to U; and

NG to V;

sorting the phrases alphabetically after changing the characters of the phrases.

5. A method as recited in claim 1, wherein the phrases are represented as strings of characters, and wherein the ordering step comprises:

changing the characters of the phrases in accordance with a pre-defined character mapping;

sorting the phrases alphabetically after changing the characters of the phrases;

wherein the pre-defined character mapping changes single-sound consonant pairs to single characters.

6. A method as recited in claim 1, wherein the phonetic search order begins with sounds made at the front of the mouth and continues in order with sounds made farther and farther back in the mouth.

7. A method as recited in claim 1, wherein the phonetic search order begins with bilabial consonant sounds made at the front of the mouth, and continues in order through labio-dental, dental, alveolar, postalveolar, velar, and glottal consonant sounds made farther and farther back in the mouth.

8. A method as recited in claim 1, wherein the phonetic search order comprises, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates;

glottal fricatives;

alveolar approximants;

postalveolar approximants; and

nasals.

9. A method as recited in claim 1, wherein the phonetic search order comprises, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

glottal fricatives.

10. A method as recited in claim 1, wherein the phonetic search order comprises the following sounds, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affiicates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

glottal fricatives;

wherein the ordering step comprises;

changing the characters of the phrases in accordance with a pre-defined character mapping that maps said sounds to sequential characters of a character set;

sorting the phrases alphabetically after changing the characters of the phrases.

11. A computer,-readable storage medium containing instructions that are executable to select resources based on a search phrase, wherein one or more keyword phrases are associated with each resource, the instructions performing steps comprising:

identifying phoneme sequences of the keyword phrases;

sorting the keyword phrases based on their identified phoneme sequences to form a phonetically ordered list of keyword phrases, in accordance with a phonetic search order in which similar sounding phonemes are adjacent each other;

identifying a phoneme sequence of the search phrase;

indexing into the phonetically ordered list of keyword phrases based on the phoneme sequence of the search phrase, to identify at least one keyword phrase that is adjacent the search phrase in the phonetic search order;

selecting the resource associated with the identified keyword phrase.

12. A computer-readable storage medium as recited in claim 11, wherein the indexing step identifies at least a pair of the keyword phrases that are adjacent the search phrase in the phonetic search order.

13. A computer-readable storage medium as recited in claim 11, wherein the phrases are represented by characters, and wherein the sorting step comprises:

changing the characters of the keyword phrases in accordance with a pre-defined character mapping;

sorting the keyword phrases alphabetically after changing the characters of the keyword phrases;

wherein the pre-defined character mapping establishes the phonetic search order in accordance with an alphabetic order of the characters.

14. A computer-readable storage medium as recited in claim 11, wherein the phrases are represented by characters, and wherein the sorting step comprises:

changing the characters of the keyword phrases in accordance with a pre-defined character mapping;

wherein the mapping indicates at least the following character changes;

W to A;

WW to A;

BB to B;

P to C;

PP to C;

V to D;

VV to D;

F to E;

FF to E;

PH to E;

TH to F;

D to G;

DD to G;

T to H;

TT to H;

J to I;

JJ to I;

CH to J;

Z to K;

S to L;

SH to M;

SS to L;

G to N;

GG to N;

C to O;

CC to O;

CK to O;

K to O;

KK to O;

Q to O;

X to P;

XX to P;

GH to Q;

H to Q;

HH to Q;

L to R;

LL to R;

R to S;

RR to S;

M to T;

MM to T;

N to U;

NN to U; and

NG to V;

sorting the keyword phrases alphabetically after changing the characters of the phrases.

15. A computer,-readable storage medium as recited in claim 11, wherein the phrases are represented as strings of characters, and wherein the sorting step comprises:

changing the characters of the keyword phrases in accordance with a pre-defined character mapping;

sorting the keyword phrases alphabetically after changing the characters of the keyword phrases;

wherein the pre-defined character mapping changes single-sound consonant pairs to single characters.

16. A computer-readable storage medium as recited in claim 11, wherein the phonetic search order begins with sounds made at the front of the mouth and continues in order with sounds made farther and farther back in the mouth.

17. A computer-readable storage medium as recited in claim 11, wherein the phonetic search order begins with bilabial consonant sounds made at the front of the mouth, and continues in order through labio-dental, dental, alveolar, postalveolar, velar, and glottal consonant sounds made farther and farther back in the mouth.

18. A computer-readable storage medium as recited in claim 11, wherein the phonetic search order comprises, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates;

glottal fricatives;

alveolar approximants;

postalveolar approximants; and

nasals.

19. A computer-readable storage medium as recited in claim 11, wherein the phonetic search order comprises, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

,

glottal fricatives.

20. A computer-readable storage medium as recited in claim 11, wherein the phonetic search order comprises the following sounds, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

glottal fricatives;

wherein the sorting step comprises;

changing the characters of the keyword phrases in accordance with a pre-defined character mapping that maps said sounds to sequential characters of a character set;

sorting the keyword phrases alphabetically after changing the characters of the keyword phrases.

21. One or more network servers comprising:

a plurality of topic resources;

a keyword table having a plurality of entries, wherein each entry is associated with one of the topic resources, wherein each entry has a keyword phrase, and wherein each entry also has a phonetic representation of its keyword phrase;

the entries being ordered by their phonetic keyword representations in accordance with a phonetic search order in which similar sounding phonemes are adjacent each other;

a search engine that accepts a search phrase and that finds one or more corresponding target entries in the keyword table by performing a phonetic matching search, the phonetic matching search comprising the following steps;

formulating a phonetic representation of the search phrase;

indexing into the keyword table based on the phonetic representation of the search phrase, to identify at least one keyword table entry whose phonetic keyword phrase representation is adjacent the phonetic search phrase representation in the phonetic search order;

selecting the resource associated with the identified keyword table entry.

22. One or more network servers as recited in claim 21, wherein the indexing step identifies at least a pair of the keyword table entries whose phonetic keyword phrase representations are adjacent the phonetic search phrase representation in the phonetic search order.

23. One or more network servers as recited in claim 21, wherein each phonetic representation comprises a phoneme sequence.

24. One or more network servers as recited in claim 21, wherein each phonetic representation comprises a string of characters, each character representing a single phoneme.

25. One or more network servers as recited in claim 21, wherein the keyword phrases comprise character strings, and wherein the phonetic representations are created in accordance with steps comprising:

changing the characters of the keyword phrases in accordance with a pre-defined character mapping;

wherein the pre-defined character mapping establishes the phonetic search order in accordance with an alphabetic order of the characters.

26. One or more network servers as recited in claim 21, wherein the keyword phrases comprises character strings, and wherein the phonetic representations are created in accordance with steps comprising:

changing the characters of the keyword phrases in accordance with a pre-defined character mapping;

wherein the mapping indicates at least the following character changes;

W to A;

WW to A;

BB to B;

P to C;

PP to C;

V to D;

VV to D;

F to E;

FF to E;

PH to E;

TH to F;

D to G;

DD to G;

T to H;

TT to H;

J to I;

JJ to I;

CH to J;

Z to K;

S to L;

SH to M;

SS to L;

G to N;

GG to N;

C to O;

CC to O;

CK to O;

K to O;

KK to O;

Q to O;

X to P;

XX to P;

GH to Q;

H to Q;

HH to Q;

L to R;

LL to R;

R to S;

RR to S;

M to T;

MM to T;

N to U;

NN to U; and

NG to V;

wherein the keyword entries are sorted alphabetically by their phonetic keyword representations after changing the characters of the phrases.

27. One or more network servers as recited in claim 21, wherein the phonetic search order begins with sounds made at the front of the mouth and continues in order with sounds made farther and farther back in the mouth.

28. One or more network servers as recited in claim 21, wherein the phonetic search order begins with bilabial consonant sounds made at the front of the mouth, and continues in order through labio-dental, dental, alveolar, postalveolar, velar, and glottal consonant sounds made farther and farther back in the mouth.

29. One or more network servers as recited in claim 21, wherein the phonetic search order comprises, in the order given:

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates;

glottal fricatives;

alveolar approximants;

postalveolar approximants; and

nasals.

30. One or more network servers as recited in claim 21, wherein the phonetic search order comprises, in the order given:

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

glottal fricatives.

31. One or more network servers as recited in claim 21, wherein the phonetic search order comprises the following sounds, in the order given:

labial stops;

bilabial fricatives;

bilabial stops;

labio-dental fricatives;

dental fricatives;

alveolar stops;

postalveolar affricates;

alveolar fricatives;

postalveolar fricatives;

velar stops;

velar affricates; and

glottal fricatives;

wherein the keyword phrases comprises character strings, and wherein the phonetic representations are created by changing the characters of the keyword phrases in accordance with a pre-defined character mapping that maps said sounds to sequential characters of a character set.