Website of the project
For information about this project, please refer to http://www.horizonideas.com/spellingdice/
No matter you are a
native English speaker or not, you may make some spelling mistakes every now and
then. Isn't it neat, if the computer
can provide some spelling suggestion for your unsure input? The most famous one
should be Google Suggest. Every time you input some mistakes, there will be "Did
you mean? XXX XXX XXX" on the next page. We know the whole system is based on Bayesian network, but how? On the other hand,
if our own website or small size program could include this great function, that
would be a valuable asset to attract people.
Peter Norvig, the Director of Google
Research revealed the secrets of Google Suggest. I believe it's not the whole algorithm,
but it's good enough for us to add spices ourselves and utilize in our own small-scale
I believe his essay is much better
than my following descriptions. You can find his paper at
Suppose someone input "Majar", the
program should be able to identify what the user actually meant was "major".
Ok, then how does it work?
We let P(s|i) denotes the probability of one suggested word s by providing an input
So we have P(s|i)=P(s,i)/P(i)
P(i) is the probability of one random input string. As the user can input anything,
so the probability is neglectable. We let it be 1. So we have:
At the same time,
P(s,i)=P(i|s) * P(s) so we have :
P(s|i)=P(s,i)= P(i|s) * P(s)
Where P(s) is the probability of one word's probability. Question: How can we define
Answer: find any book and read it through then make statics of each word's occurrence.
Or download the API which includes the 5000 most commonly used English word. For
instance, the word "the" must have a lot higher probability than "tae" [therapeutic
Ok, what about P(i|s)? literately, P(i|s) is the probability of one input string
by providing an recommend string. But it does not make sense. So it becomes the
probability of one suggested string by calculating the editing distance.
Oh, edit distance. You don't know what? Read
The most famous one is Levenshtein Distance which is a build-in function in PHP.
Another example is Hamming Distance in Information Theory. For instance D(01010,
10010)=2 . now you get what I mean by edit distance, right?
Ok, let's continue. They less edit distance you have, the higher probability you
For instance if someone inputs "hallo", "hello" has much higher P(i|s) than "helen".
What if the word is correct? In other words, if one in the dictionary matches the
input. Then the program should not return any suggesition. To save time complexity,
ths program should break here.
Understand what I said? If not, again, please refer to his original article.
Ok. Let's take a closer look at "hallo". The program may find "Hallow" "Mallo"(if
indeed, there is such word) and "Hello". They may have the same P(s) as we won't
see too many people use tons of "hello" in their formal writings. And they have
the same edit distance, so should they be placed in the order of alphabets? No!
Absolutely not. Use your head to think! How many people would mis-type the first
letter? Not so many~ So get rid of "mallo". Cool! Then you will find people tend
to mis-type more vowels than consonants. The reason is because it's very obvious
for human eyes to discover the typos of consonants. So they may correct them before
submit to computer. Thus, "hello" must have much better P(i|s) "hallow". Is that
The above are all in Dr. Peter Norvig's essay. But I don't think that's totally
enough for determining P(i|s). So I observe how people type and find out some of
us like me have giant fingers. So instead of type "hello" , we type "hrllo" or "hekko".
If you take a closer look at your keyboard you will realize why. Because these 'e'
and 'r' are near so are 'k' and 'l'. So here we have another standard, the P(i|s)
will be increased if a letter is replaced by its neighbors on the keyboard. So when
type "hrllo", "hello" must have higher probability than "hillo" (if indeed this
is such word"). Ok, I hope you are not lost here. This is the idea of SpellingDice.
If you don't want to know about the Algorithm, you can skip the following and go
directly to download the APIs for PHP and C# at HERE
Try out the online SpellingDice Corrector PHP
Please click HERE
Array<string> ReturnSuggestion(string inputWord)
if( inputWord.ToLowerCase()<='z' && inputWord.ToLowerCase()<='a')
// if continues only if it's a English letter
Array<string> Candidates = ReadFromXML(inputWord.ToLowerCase()); // To
speed up the process, only read the dictionary that start with the first letter.
For instance, if input is "hallo" only read 'h.xml'.
Maps<string, double> RefinedCandidates;
foreach(string candidate in Candidates)
if(LevenshteinDistance(candidate, inputWord)<=2) //only check those words who
have an edit distance of 2 comparing to the input. Otherwise the candidate list
will be long and it does not help that much.
To Download the Set, please click HERE
// no matter the input is a sentence or a word, it will return a suggested sentence
or 5 suggested words. if no suggestion, null will be returned. NOTE: When the input
is a word, the return value will be a string array, if it is a sentence, a sentence
string will be returned.
//only process a sentence, return a suggested sentence
//only process a word, a array of at most 5 suggested words will be returned.
public class SpellingDice
public SpellingDice() //intilize method
ReturnSuggestion(string input); ///no matter the input is a sentence or a word,
it will return a suggested sentence or 5 suggested words. if no suggestion, null
will be returned. NOTE: When the input is a word, the return value will be a string
array, if it is a sentence, an array of only one element will be returned.
public List<string> WordProcess(string word) //only process a word,
a array of at most 5 suggested words will be returned.
A Snippet of Codes
$parser = xml_parser_create();
xml_parser_set_option($parser,XML_OPTION_SKIP_WHITE,1); <o:p />
$data = implode("",file('dictionary/'.$letter.'.xml'));
if($d_ar[$j]['tag'] == 'word')
$word = $d_ar[$j]['value'];
}elseif($d_ar[$j]['tag'] == 'probability')
$probability = $d_ar[$j]['value'];
as $key=> $value)
return $result; <o:p />
public List<string> WordProcess(string
List<string> result = new List<string>();
listOfCandidates = new SortedDictionary<double, string>();
if (word <= 'z' &&
word >= 'a')
DictionaryItem in candidatesList[word])
(DictionaryItem.word == word)
int LD = Levenshtein(word, DictionaryItem.word);
if (LD <= 2)
double editDistance = StringDistance(word, DictionaryItem.word,
listOfCandidates[1 / (DictionaryItem.probability * (1 / editDistance))] = DictionaryItem.word;
} } } <o:p />
foreach (KeyValuePair<double,string> kvp in listOfCandidates)
if (listOfCandidates.Count > 5)
result.RemoveRange(5, listOfCandidates.Count - 5);
result.Add(word); <o:p />
The performance of this algorithm is actually very good as we have some heuristic to ensure the least loops.
It needs O(n) to read the dictionary
Then O(n) to loop the dictionary
O(m) to check every word( m) is the length of words)
O(nlogn) to sort
So in totally we are looking at a O(n)+O(nlogn)+o(n*m) algorithm.
The PHP version is slightly faster than C# as it has some neat build-in functions. C# don't have a auto-sorted data structure to handle the array (SortedDictionary only sort the keys not value, and it's from low to high which is something we want in opposite way).
The program also largely depends on your dictionary. My dictionary included has 5000 English words. But it's not enough. You may want to expand the dictionary yourself. I made them 26 XML files. You can do it more yourself. This program could deal with regular spelling corrections, but I cannot guarantee it provides the same effects as Google Suggest does as they have much larger data stored and other advantages.
In all, this is a small-size fast program to help you achieve a neat feature on your website or small project. If you have any question or comments, please contact me directly.