The algorithm used is Stupid Backoff, described in Brants et al, 2007 (link, see section 4).
I chose this because it is inexpensive and loads fast, while
performing nearly as well as Kneser-Ney smoothing – which is quite good.
The algo gives each candidate word a score, based on its n-gram frequency.
Mathematically, let
\( Score = \begin{cases} \frac {freq(w_i)_{n=k+1}} {freq(w_{i-k}^{i-1})_{n=k+1}} & \text{if } freq(w_{i-k}^i)_{n=k+1} > 0 \\ \alpha \frac {freq(w_i)_{n=k}} {freq(w_{i-(k-1)}^{i-1})_{n=k}} & \text{otherwise} \end{cases} \)
Hypothetical example: user types cat in the. One possible next word is hat.
We look in the 4-gram first (n = 4). The score for hat is given by:
\[ Score(\text{"hat"}) = \begin{cases} \frac {freq(\text{"hat"})_{n=4}} {freq(\text{"cat in the"})_{n=4}} & \text{if } freq(\text{"cat in the hat"})_{n=4} > 0 \\ \alpha \frac {freq(\text{"hat"})_{n=3}} {freq(\text{"in the"})_{n=3}} & \text{otherwise} \end{cases} \]
Note that the score depends on the relative frequency, which is
also the Maximum Likelihood Estimate (MLE), in this case.
