Patent ID: 7290209

Claim:
An apparatus, comprising: a computing processor; an electronic memory coupled with the computing processor; an input device to receive an entered string s, and a program in the memory for execution on the computing processor to determine a probability P(s|w) expressing how likely a word w was to have been incorrectly entered as the string s, by partitioning the word w and the string s into different numbers of segments that define varying lengths of character sequences and computing probabilities for various partitionings, as follows: P ⁡ ( s ❘ w ) = ∑ R ∈ Part ⁡ ( w ) ⁢ P ⁡ ( R ❘ w ) ⁢ ∑ T ∈ Part ⁡ ( s )  T  =  R  ⁢ ∏ i = 1  R  ⁢ P ⁡ ( T i ❘ R i ) where Part(w) is a set of possible ways of partitioning the word w, Part(s) is a set of possible ways of partitioning the string s, R is a particular partition of the word w, and T is a particular partition of the string s.