System and method for word matching and indexing
The invention provides a method for retrieving similar sounding words from an electronic database. An input or query word is first converted to a string of corresponding phonemes. The string of phonemes is then used to generate a key, with the key made up of elements corresponding to the phonemes. In a preferred embodiment the key elements correspond to classes of phonemes. The electronic database comprises a plurality of words, each of which have a corresponding, phoneme-based key. Words in the database having a key identical to the key of the input word are retrieved and output. The use of phonemes in generating the search key results in the retrieval of similar sounding words. In another aspect, the invention provides a method of providing a similarity score for an output word or a list of output words compared to an input word. All of the output words are converted into phonemes and the score is based on a comparison of the phonemes in the input word with the phonemes in each output word.
1 . A method for retrieving words from an electronic database, the method carried out on one or more computer processors, and comprising the steps of:
inputting an input word to the one or more computer processors;
transforming the input word into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing an input key from the string of phonemes using the one or more computer processors, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
retrieving words from the electronic database having a key matching the input key, using the one or more computer processors; and
outputting an output indicative of the retrieved words.
2 . The method according to claim 1 , further comprising the steps of determining a number of syllables in the input word and including in the input key an indication of the number of syllables.
3 . The method according to claim 1 , wherein each key element from the set of key elements corresponds to a class of phonemes.
4 . The method according to claim 3 , wherein each key element from the set of key elements corresponds to a manner of articulation.
5 . The method according to claim 1 , wherein the records in the electronic database are names.
6 . The method according to claim 1 , wherein the step of transforming the input word comprises generating two or more different input keys for an input word and retrieving words from the electronic database having a key matching either input key.
7 . The method according to claim 1 , further comprising the step of ranking retrieved words from the electronic database according to a metric, the metric indicative of the similarity of each retrieved word to the input word.
8 . The method according to claim 7 , wherein the metric is based on a comparison between the phonemes in a retrieved word and the phonemes in the input word.
9 . The method according to claim 8 , wherein the metric is based on the result of a distance function performed on phoneme strings.
10 . The method according to claim 9 , wherein the distance function is an edit-distance function.
11 . The method according to claim 1 , wherein the step of transforming the input word comprises checking an electronic dictionary of words and their corresponding phoneme strings, and if a word matching the input word is in the dictionary selecting the matching phoneme string, otherwise executing a phoneme string generating algorithm on the input word.
12 . A system for retrieving words from an electronic database, comprising:
a phoneme converter for converting an input word into a string of phonemes, the phonemes selected from a set of phonemes stored in a memory;
a key generator for converting the string of phonemes into an input key, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
a retrieval engine for retrieving words from the database, wherein each word in the database has a corresponding key, and wherein the retrieval engine retrieves words from the database having a key matching the input key; and
an output coupled to the retrieval engine for outputting the retrieved words.
13 . The system according to claim 12 , wherein the key generator is configured to include an indication of a number of syllables in the input word in the input key.
14 . The system according to claim 12 , wherein each key element from the set of key elements corresponds to a class of phonemes.
15 . The system according to claim 12 , wherein the phoneme converter is configured to generate two or more different input keys for an input word and the retrieval engine is configured to retrieve words from the electronic database having a key matching either input key.
16 . The system according to claim 12 , further comprising a ranking engine, the ranking engine ranking retrieved words from the electronic database according to a metric, the metric indicative of the similarity of each retrieved word to the input word.
17 . The system according to claim 16 , wherein the metric is based on a comparison between the phonemes in a retrieved word and the phonemes in the input word.
18 . The system according to claim 17 , wherein the metric is based on the result of an edit-distance function performed on phoneme strings.
19 . The system according to claim 12 , wherein the phoneme converter is configured to check an electronic dictionary of words and matching phoneme strings, and if a word matching the input word is in the dictionary to select the matching phoneme string, otherwise to generate a phoneme string based on the input word.
20 . A computer readable storage medium containing instructions that are executable on one or more computer processors to retrieve words from an electronic database, the instructions performing steps comprising:
inputting an input word to the one or more computer processors;
transforming the input word into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing an input key from the string of phonemes using the one or more computer processors, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
retrieving words from the electronic database having a key matching the input key, using the one or more computer processors; and
outputting an indication of the retrieved words.
21 . A method of indexing a database of words, the method carried out on one or more computer processors, and comprising the steps of:
transforming each word from the database into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing a key for each string of phonemes using the one or more computer processors, wherein each key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein each phoneme in each string of phonemes is transformed into a corresponding key element from the set of key elements and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes; and
storing as an index a key corresponding to each word in the database together with an indication of the word to which it corresponds.
22 . A method of generating keys corresponding to input words, the method carried out on one or more computer processors, and comprising the steps of:
inputting an input word to the one or more computer processors;
transforming the input word into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing a key from the string of phonemes using the one or more computer processors, wherein the key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein each phoneme is transformed into a corresponding key element from the set of key elements and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes.
23 . A method of ranking a set of output words retrieved from an electronic database based on their similarity to an input word, performed on one or more computer processors, comprising:
transforming the input word into a first string of phonemes, the phonemes selected from a set of phonemes, using one or more computer processors;
comparing the first string of phonemes with a second string of phonemes corresponding to each output word, the phonemes in each second string of phonemes being selected from the set of phonemes, to produce a quantitative measure of the similarity between the input word and each output word, using one or more computer processors, the quantitative measure being based on difference scores between phonemes in the first phoneme string and in each second phoneme string, a predetermined difference score being assigned to each possible pair of phonemes taken from the set of phonemes; and
displaying the output words either in a rank order based on the quantitative measure for each output word or together with an indication of the quantitative measure for each output word.
24 . The method according to claim 23 , wherein the step of comparing the first string of phonemes with each second string of phonemes comprises performing a distance function on the first and second string of phonemes to produce the quantitative measure.
25 . The method according to claim 24 , wherein the distance function is an edit-distance function.
26 . The method according to claim 23 , wherein the step of comparing the first string of phonemes with each second string of phonemes further includes comparing a number of syllables in the input word with a number of syllables in the output word and including a syllable difference score in the quantitative measure.
27 . The method according to claim 23 , wherein each phoneme in the set of phonemes is assigned to a class of phonemes and wherein the step of assigning a difference score to each possible pair of phonemes comprises assigning a higher difference score to pairs of phonemes in different phoneme classes than to phonemes in the same phoneme class.
28 . The method according to claim 23 , further comprising filtering the output words on the basis of the quantitative measure for each output word.
29 . The method according to claim 23 , wherein the output words are names.
30 . The method according to claim 23 , further comprising retrieving the set of output words from the electronic database by the steps of:
inputting an input word to the one or more computer processors;
transforming the input word into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing an input key from the string of phonemes using the one or more computer processors, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
retrieving words from the electronic database having a key matching the input key, using the one or more computer processors; and
outputting an output indicative of the retrieved words.
31 . A system for ranking a set of output words retrieved from an electronic database based on their similarity to an input word, the system comprising:
a phoneme converter for transforming the input word into a first string of phonemes, the phonemes selected from a set of phonemes;
a memory, storing a lookup table assigning a difference score to each possible pair of phonemes taken from the set of phonemes;
a comparator for comparing the first string of phonemes with a second string of phonemes for each output word, the phonemes in each second string of phonemes being selected from the set of phonemes, to produce a quantitative measure of the similarity between the input word and each output word, the quantitative measure being based on difference scores between the phonemes in the first phoneme string and in each second phoneme string; and
a display, connected to the comparing means, for displaying the output words either in a rank order based on the quantitative measure for each output word or together with an indication of the quantitative measure for each output word.
32 . The system according to claim 31 , wherein the comparator is configured to perform a distance function on the first and second string of phonemes to produce the quantitative measure.
33 . The system according to claim 31 , wherein the comparator is configured to compare a number of syllables in the input word with a number of syllables in the output word and include a syllable difference score in the quantitative measure.
34 . The system according to claim 31 , wherein each phoneme in the set of phonemes is assigned to a class of phonemes and wherein the look-up table assigns a higher difference score to pairs of phonemes in different phoneme classes than to phonemes in the same phoneme class.
35 . The system according to claim 31 , further comprising a filter for filtering the output words on the basis of the quantitative measure for each output word.
36 . The system according to claim 31 , further comprising:
a phoneme converter for converting an input word into a string of phonemes, the phonemes selected from a set of phonemes stored in a memory;
a key generator for converting the string of phonemes into an input key, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
a retrieval engine for retrieving words from the database, wherein each word in the database has a corresponding key, and wherein the retrieval engine retrieves words from the database having a key matching the input key; and
an output coupled to the retrieval engine for outputting the retrieved words.
37 . A computer readable storage medium containing instructions that are executable on one or more computer processors to rank a set of output words retrieved from an electronic database based on their similarity to an input word, the instructions performing steps comprising:
transforming the input word into a first string of phonemes, the phonemes selected from a set of phonemes, using one or more computer processors;
comparing the first string of phonemes with a second string of phonemes corresponding to each output word, the phonemes in each second string of phonemes being selected from the set of phonemes, to produce a quantitative measure of the similarity between the input word and each output word, using one or more computer processors, the quantitative measure being based on difference scores between phonemes in the first phoneme string and in each second phoneme string, a predetermined difference score being assigned to each possible pair of phonemes taken from the set of phonemes; and
displaying the output words either in a rank order based on the quantitative measure for each output word or together with an indication of the quantitative measure for each output word.
38 . The computer readable storage medium containing instructions that are executable on one or more computer processors according to claim 37 , the instructions performing steps further comprising:
inputting an input word to the one or more computer processors;
transforming the input word into a string of phonemes, wherein the phonemes are selected from a set of phonemes, using the one or more computer processors;
producing an input key from the string of phonemes using the one or more computer processors, wherein the input key comprises a string of key elements, wherein the key elements are selected from a set of key elements, wherein the phonemes are transformed into corresponding key elements from the set of key elements, wherein each key element in the input key corresponds to one or more phonemes in the string of phonemes and wherein there are fewer key elements in the set of key elements than there are phonemes in the set of phonemes;
retrieving words from the electronic database having a key matching the input key, using the one or more computer processors; and
outputting an indication of the retrieved words.