Method and apparatus for multilingual spelling corrections
View Patent ↗A system and method for multilingual spelling corrections employs a lexicon builder, which uses a metadata build process that extracts all words from the data source, along with their frequencies, to build a lexicon file using the data source with which a user will be working; and a spell checker algorithm, which determines the correct spelling of words used as input for a search of the data source by calculating a score value for words in the lexicon file according to a formula that distinguishes similarity between the input word from the user's search request and words contained in the lexicon file; and then rates the frequency of the input word against the words contained in the lexicon file. When a user inputs a word, words in the lexicon file are scored against the input word to determine a correct spelling or other spelling variant for the user to select.
1. Computer-implemented apparatus for making multilingual spelling corrections for an input word in a search query directed against a data source, comprising:
lexicon builder means executed by a computer processor for building a lexicon file using the words in the data source against which the search query is targeted; and
spell checker means for providing suggested correct spellings and variant spellings of the input word in the search query by checking the input word against the lexicon file, wherein the spell checker means includes means for creating a subset of candidate words from the lexicon file, and wherein the means for creating a subset of candidate words includes:
means for splitting the input word and each word in the lexicon file into N-grams based on the length of the input word and for each N-gram of each word in the lexicon file, determining whether it matches an N-gram in the input word and
means for checking only those words in the lexicon file that start with the same letter as an input word and having a word length in the range of Input Word Length−K to Input Word Length+K based on the number of matching N-grams with the input word, where Input Word Length is the number of letters in the input word and where K is a constant.
2. The apparatus of claim 1 , wherein the lexicon builder means includes:
means for testing words in the data source against a threshold value for frequency and for testing words in the data source that fail the threshold value for presence in a well-respected dictionary, and
means for excluding from the lexicon file words that fail the threshold value for frequency and that are not present in the well-respected dictionary.
3. The apparatus of claim 1 , wherein the spell checker means includes:
means for calculating a score for each of the candidate words and for choosing suggested spelling corrections and spelling variations based on the calculated score for each of the candidate words.
4. The apparatus of claim 3 , wherein the score calculated by the means for calculating and choosing is calculated according to a formula utilizing enhanced Levenstein edit distance, number of decimals in the word's frequency, the high decimal digit in the word's frequency, and a bonus to candidate words ending with the same letter as the input word.
5. The apparatus of claim 3 , wherein the score calculated by the means for calculating and choosing is calculated according to the formula
SCORE= w Edit×( N MAX−EditDistance)+ w Frequency×( F ND +(0.1× F HD ))+( w LastCharBonus× LB 1)
where:
wEdit and wFrequency are experimentally determined weight factors;
NMAX is the Edit distance threshold value, which is an experimentally determined constant;
EditDistance is the enhanced Levenstein edit distance;
F ND is the number of decimals in the word's frequency;
F HD is the high decimal digit in the word's frequency;
wLastCharBonus is an experimentally-determined weight factor; and
LB 1 is determined by the condition LB 1 =1 if the last letter of the input word matches the letter of a lexicon word.
6. The apparatus of claim 3 , wherein the means for calculating and choosing includes means for testing the calculated score for each candidate word against a score threshold and for excluding as spelling correction words candidate words having a calculated score less than the score threshold.
7. The apparatus of claim 6 , wherein the threshold score value is calculated as a percentage of the absolute maximum score value for the words.
8. The apparatus of claim 7 , wherein the value of the percentage is determined experimentally.
9. The apparatus of claim 6 , wherein the threshold score value is a constant that depends upon the data source.
10. The apparatus of claim 1 , wherein the means for creating a subset checks each word in the lexicon file for N-gram matches located in the same position as in the input word or shifted on position to the left or to the right from its position in the input word.
11. The apparatus of claim 1 , wherein the means for creating a subset of candidate words uses uni-grams for input words having a length less than or equal to a predetermined number of letters and uses bi-grams for input words having a length greater than the predetermined number of letters.
12. The apparatus of claim 1 , wherein all words in the lexicon file having a number of matched N-grams greater than or equal to a predetermined percentage of the total number of N-grams in the input word are selected as candidate words.
13. A computer-implemented method for making multilingual spelling corrections for an input word in a search query directed against a data source, comprising:
building using a computer processor to build a lexicon file using the words in the data source against which the search query is targeted; and
providing suggested correct spellings and variant spellings of the input word in the search query by checking the input word against the lexicon file and creating a subset of candidate words from the lexicon file, wherein the step of creating a subset of candidate words includes:
splitting each input word and each word in the lexicon file into N-grams based on the length of the input word;
for each N-gram of each word in the lexicon file, determining whether it matches an N-gram in the input word; and
checking only those words in the lexicon file that start with the same letter as each input word and having a word length in the range of Input Word Length−K to Input Word Length+K based on the number of “common N-grams” with the input word, where Input Word Length is the number of letters in the input word and where K is a constant.
14. The method of claim 13 , wherein the step of building a lexicon file includes the further steps of:
testing words in the data source against a threshold value for frequency and testing words in the data source that fail the threshold value for presence in a well-respected dictionary, and
excluding from the lexicon file words that fail the threshold value for frequency and that are not present in the well-respected dictionary.
15. The method of claim 13 , wherein the step of providing suggested correct spellings and variant spellings includes the further step of:
calculating a score for each of the candidate words and choosing suggested spelling corrections and spelling variations based on the calculated score for each of the candidate words.
16. The method of claim 15 , wherein in the step of calculating and choosing, the score is calculated according to a formula utilizing enhanced Levenstein edit distance, number of decimals in the word's frequency, the high decimal digit in the word's frequency, and a bonus to candidate words ending with the same letter as the input word.
17. The method of claim 15 , wherein in the step of calculating and choosing, the score is calculated according to the formula
SCORE= w Edit×( N MAX−EditDistance)+ w Frequency×( F ND +(0.1× F HD ))+( w LastCharBonus× LB 1)
where:
wEdit and wFrequency are experimentally determined weight factors;
NMAX is the Edit distance threshold value, which is an experimentally determined constant;
EditDistance is the enhanced Levenstein edit distance;
F ND is the number of decimals in the word's frequency;
F HD is the high decimal digit in the word's frequency;
wLastCharBonus is an experimentally-determined weight factor; and
LB 1 is determined by the condition LB 1 =1 if the last letter of the input word matches the letter of a lexicon word.
18. The method of claim 15 , wherein the step of calculating and choosing includes testing the calculated score for each candidate word against a score threshold and excluding as spelling correction words candidate words having a calculated score less than the score threshold.
19. The method of claim 18 , wherein in the step of calculating and choosing, the threshold score value is calculated as a percentage of the absolute maximum score value for the words.
20. The method of claim 19 , wherein in the step of calculating and choosing, the value of the percentage is determined experimentally.
21. The method of claim 18 , wherein in the step of calculating and choosing, the threshold score value is a constant that depends upon the data source.
22. The method of claim 13 , wherein the step of creating a subset includes checking each word in the lexicon file for N-gram matches located in the same position as in the input word or shifted on position to the left or to the right from its position in the input word.
23. The method of claim 13 , wherein the step of creating a subset of candidate words includes using uni-grams for input words having a length less than or equal to a predetermined number of letters and using bi-grams for input words having a length greater than the predetermined number of letters.
24. The method of claim 13 , wherein all words in the final lexicon having a number of matched N-grams greater than or equal to a predetermined percentage of the total number of N-grams in the input word are selected as candidate words.