I'm working on a word-prediction/spelling-correction software project and I need to calculate the probability that a dictionary word is what the user meant to type, referred to as a "score". I found an article that explains how to score matches using statistical techniques, but I don't understand it 100% (I'm not stats-savvy). I hope it is easy for you to understand!
First, some definitions:
prefix: What the user typed. It is called a prefix because it is usually incomplete since we score words as the user types in order to provide predictions.
word: A word from the dictionary.
probability: The frequency of a word in the language, expressed as the number of times it appears in a codex. The probability distribution is quasi-logarithmic, as you may expect.
edit distance: A measure of the number of errors (i.e. typos) between prefix and word. It is an integer <=0 where 0 = no typos.
score: The article refers to two types of score.
score(prefix,word) (which I will refer to as prediction score) is the probability that word is what the user is typing. It is a function of word probability and edit distance. I think
score(word) (which I will refer to as word score) is just word probability, normalized somehow.
What I don't understand:
The formulas below, especially
score(prefix,word). Can someone please dumb down both the formulas below? I'm sure I can understand them with a little help. If you need more detail I'll do my best to provide it.
Thanks in advance...
Scores for words are defined by the log (base 2) of their probability estimates:
score(word) = log2 p'(word)
where probabilities are estimated using maximum likelihood:
p'(word) = count(word) / Σword' count(word')
Additive smoothing may be easily carried out on the inputs, so it is not carried out here.
The score for a prefix matching a word is given by:
score(prefix,word) = MAXphrase.startsWith(prefix') editDistance.distance(prefix,prefix') + log2 p'(word)
In words, the score for a prefix matching a word is the sum of log probability of the word plus the edit distance between the prefix and the best matching prefix of the word. The edit distances should thus be scaled as log probabilities in order to combine with the phrase probabilities properly.