Method to expand inputs for word or document searching

• US 7,089,188 B2
• Filed: 03/27/2002
• Issued: 08/08/2006
• Est. Priority Date: 03/27/2002
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Moreno, Pedro J., Thong, Jean-Manuel Van, Logan, Beth T.
• Primary Examiner(s): HARPER, V PAUL
• Application Number:
  US10/108,534
• Publication Number:
  US 20030187649A1
• Time in Patent Office: 1,595 Days
• Field of Search: 704/260, 704/3, 704/243, 704/4
• US Class Current: 704/270
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence

Abstract

An electronic document searching system or word searching system which when given an input, expands the input as a function of acoustic similarity and/or word sequence occurrence frequency. Results of the system are alternative input words or phrases. The alternative input words or phrases are output from the system for further processing.

Claims

1. A method for electronic document or word searching, comprising the steps of:

(a) given an input, expanding the input as a function of at least one of (i) acoustic similarity and/or (ii) frequency of word sequence occurrence, said expanding resulting in alternative input words or phrases, wherein the step of expanding includes;

translating words in the given input to one or more phoneme strings;

determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences; and

for each produced phoneme subsequence, generating at least one confusable word phrase having a pronunciation which is acoustically similar to the phoneme subsequence, said confusable word phrase forming an alternative input word or phrase, wherein the step of generating at least one confusable word phrase includes;

comparing each phoneme subsequence to word pronunciations from a dictionary, said comparing resulting in a list of words from the dictionary; and

ordering the list of words from the dictionary, the most likely word being at the top of the list, said ordering of the list including scoring the word pronunciation of each word in the dictionary against the phoneme subsequence using a distance metric based on the distance between a hypothesized pronunciation in the phoneme subsequence and the pronunciation from the dictionary; and

(b) returning the alternative input words or phrases for further processing.

2. A method as claimed in claim 1, wherein the electronic documents are transcriptions of spoken input.

3. A method as claimed in claim 1, wherein the word searching is a spell checker.

4. A method as claimed in claim 1, wherein the input is a query.

5. A method as claimed in claim 1, wherein the step of translating words in the given input to one or more phoneme strings further includes:

converting the words to phonemes by at least (i) looking up the words in a dictionary or (ii) using letter to phoneme rules to automatically generate a pronunciation.

6. A method as claimed in claim 5, wherein the step of translating words in the given input to one or more phoneme strings further includes:

generating one or more phoneme strings of the converted word phonemes based on a confusion matrix; and

scoring the one or more phoneme strings based on the confusion matrix.

7. A method as claimed in claim 6, wherein the confusion matrix stores indications of the likelihood of confusion between pairs of phonemes, the likelihood of deleting each phoneme in a pronunciation of a word, and the likelihood of inserting each phoneme in a pronunciation of a word.

8. A method as claimed in claim 1, wherein the step of determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences uses an example-based word boundary.

9. A method as claimed in claim 8, wherein the example-based word boundary includes:

breaking up each of the phoneme strings into a list of segmented phoneme strings;

looking up each segmented phoneme string in a dictionary; and

producing a list of segmented phoneme strings found in the dictionary.

12. A method as claimed in claim 1, wherein the distance metric is defined as follows:

S(p₀,d₀)=0

$S<br><br>\left(p_i,d_j\right)=\min <br><br>\left\{\begin{array}{c}S<br><br>\left(p_{i-1},d_{j-1}\right)+C_{\mathrm{subs}}<br><br>\left(p_i,d_j\right)\\ S<br><br>\left(p_{i-1},d_j\right)+C_{\mathrm{del}}<br><br>\left(p_i\right)\\ S<br><br>\left(p_i,d_{j-1}\right)+C_{\mathrm{ins}}<br><br>\left(d_j\right)\end{array}\right\}$
S(P,D)=S(p_n,d)+LP(p_n,d_n)

wherein;

P is a hypothesized pronunciation in the phoneme subsequence;

D is the pronunciation from the dictionary;

S(P,D) is the distance between P and D;

S(p_i, d_j) is the score of phoneme string matching a given phoneme p_i of P, and phoneme d_j of D;

C_subs(p_i, d_j) is the cost of substituting phoneme p_i of P with phoneme d_j of D;

C_del(pi) is the cost of deleting phoneme p_i of P;

C_ins(d_j) is the cost of inserting phoneme d_j of D;

LP(p_n, d_n) is the length penalty of decoded phoneme string p_n matching pronunciation d_n.

13. A method as claimed in claim 12, wherein scoring the word pronunciation of each word in the dictionary against the phoneme subsequence using a distance metric further includes, scoring the list of words using a language model.

14. A method as claimed in claim 1, wherein the step of further processing includes using the alternative input words or phrases resulting from said step of expanding, searching an index of electronic documents for the alternative input words or phrases in response to the given input.

15. A method as claimed in claim 14, wherein the step of searching the index includes:

searching for an exact match of each alternative input word or phrase;

searching for a “

proximate”

match of each alternative input phrase;

augmenting an indexer'"'"'s score with a score associated with each alternative input word or phrase, including a probability of the alternative input word or phrase and/or probability of a proximate match; and

re-ranking the electronic documents according to the augmented score.

16. A method as claimed in claim 1, wherein the step of returning to a user the alternative input words or phrases further includes the user choosing correct alternative input words or phrases.

10. A method as claimed in claim 10, wherein the step of determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences uses a syllable-based word boundary.

11. A method as claimed in claim 10, wherein the syllable-based word boundary includes:

breaking up each of the phoneme strings into a list of segmented phoneme strings;

determining if each segmented phoneme string contains at least a vowel; and

producing a list of segmented phoneme strings containing at least one vowel.

17. A computer system for electronic document or word searching, comprising:

an expansion module for expanding a input as a function of at least one of (i) acoustic similarity and/or (ii) frequency of word sequence occurrence, said expanding resulting in alternative input words or phrases and returning the alternative input words or phrases for further processing, wherein the expansion module comprises;

a translation module for translating words in the given input to one or more phoneme strings;

a determination module for determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences; and

a production module for each produced phoneme subsequence, generating at least one confusable word phrase having a pronunciation which is acoustically similar to the phoneme subsequence, said confusable word phrase forming an alternative input word or phrase, wherein the production module comprises;

a comparison module for comparing each phoneme subsequence to word pronunciations from a dictionary, said comparing resulting in a list of words from the dictionary; and

an ordering module for ordering the list of words from the dictionary, the most likely word being at the top of the list, the ordering module scoring the word pronunciation of each word in the dictionary against the phoneme subsequence using a distance metric based on the distance between a hypothesized pronunciation in the phoneme subsequence and the pronunciation from the dictionary.

18. A computer system as claimed in claim 17, wherein the electronic documents are transcriptions of spoken input.

19. A computer system as claimed in claim 17, wherein word searching is a spell checking module.

20. A computer system as claimed in claim 17, wherein the input is a query.

21. A computer system as claimed in claim 17, wherein the translation module comprises:

a conversion module for converting the words to phonemes by at least (i) looking up the words in a dictionary or (ii) using letter to phoneme rules to automatically generate a pronunciation.

22. A computer system as claimed in claim 21, wherein the translation module further comprises:

a generation module for generating one or more phoneme strings of the converted word phonemes based on a confusion matrix; and

a scoring module for scoring the one or more phoneme strings based on the confusion matrix.

23. A computer system as claimed in claim 22, wherein the confusion matrix stores indications of the likelihood of confusion between pairs of phonemes, the likelihood of deleting each phoneme in a pronunciation of a word, and the likelihood of inserting each phoneme in a pronunciation of a word.

24. A computer system as claimed in claim 17, wherein the determination module further comprises an example-based word boundary module for determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences.

25. A computer system as claimed in claim 24, wherein the example-based word boundary module comprises:

a decipher module for breaking up each of the phoneme strings into a list of segmented phoneme strings;

a lookup module for looking up each segmented phoneme string in a dictionary; and

an assembler module for producing a list of segmented phoneme strings found in the dictionary.

26. A computer system as claimed in claim 17, wherein the determination module further comprises a syllable-based word boundary module for determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences.

27. A computer system as claimed in claim 26, wherein the syllable-based word boundary module comprises:

a decipher module for breaking up each of the phoneme strings into a list of segmented phoneme strings;

a determination module for determining if each segmented phoneme string contains at least a vowel; and

a assembler module for producing a list of segmented phoneme strings containing at least one vowel.

28. A computer system as claimed in claim 17, wherein the the distance metric is defined as follows:

S(p₀,d₀)

$S<br><br>\left(p_i,d_j\right)=\min <br><br>\left\{\begin{array}{c}S<br><br>\left(p_{i-1},d_{j-1}\right)+C_{\mathrm{subs}}<br><br>\left(p_i,d_j\right)\\ S<br><br>\left(p_{i-1},d_j\right)+C_{\mathrm{del}}<br><br>\left(p_i\right)\\ S<br><br>\left(p_i,d_{j-1}\right)+C_{\mathrm{ins}}<br><br>\left(d_j\right)\end{array}\right\}$
(P,D)=S(p_n,d_n)+LP(p_n,d_n)

wherein;

P is a hypothesized pronunciation in the phoneme subsequence;

D is the pronunciation from the dictionary;

S(P, D) is the distance between P and D;

S(p_i, d_j) is the score of phoneme string matching a given phoneme p_i of P, and phoneme d_{j of D;}

C_subs(p_i, d_j) is the cost of substituting phoneme p_i of P with phoneme d_j of D;

C_del(p_i) is the cost of deleting phoneme p_i of P;

C_ins(p_i) is the cost of inserting phoneme d_j of D;

LP(p_n, d_n) is the length penalty of decoded phoneme string p_n matching pronunciation d_n.

29. A computer system as claimed in claim 28, wherein the ordering module further scores the list using a language model.

30. A computer system as claimed in claim 17, wherein the step of further processing includes a search module for using the alternative input words or phrases resulting from said step of expanding, searching an index of electronic documents for the alternative input words or phrases in response to the given input.

31. A computer system as claimed in claim 30, wherein the search module comprises:

a matching module for searching for an exact match of each alternative input word or phrase;

a proximity module for searching for a “

proximate”

match of each alternative input phrase;

an augmentation module for augmenting an indexer'"'"'s score with a score associated with each alternative input word or phrase including a probability of the alternative input word or phrase and/or probability of a proximate match; and

a re-ranking module for re-ranking the electronic documents according to the augmented score.

32. A computer system comprising:

(a) means for expanding a given input and resulting in alternative input words or phrases, wherein the means for expanding includes;

means for translating words in the given input to one or more phoneme strings;

means for determining word boundaries in each of the phoneme strings to produce respective phoneme subsequences; and

for each produced phoneme subsequence, means for generating at least one confusable word phrase having a pronunciation which is acoustically similar to the phoneme subsequence, said confusable word phrase forming an alternative input word or phrase, said means for generating at least one confusable word phrase;

comparing each phoneme subsequence to word pronunciations from a dictionary, said comparing resulting in a list of words from the dictionary; and

ordering the list of words from the dictionary, the most likely word being at the top of the list, said ordering of the list including scoring the word pronunciation of each word in the dictionary against the phoneme subsequence using a distance metric based on the distance between a hypothesized pronunciation in the phoneme subsequence and the pronunciation from the dictionary; and

(b) means for searching an index of electronic documents for the alternative input words or phrases in response to the given input.