Summary

The goal of this project is a smartphone-style keyboard feature that suggests the next word as someone types, like SwiftKey. This report:

  1. confirms the English text data (blogs, news articles and tweets) has been downloaded and loaded;
  2. summarises the size and main features of the data;
  3. describes a first working prediction model and how well it performs; and
  4. outlines the plan for the final algorithm and the Shiny web app.

All numbers in this report are calculated directly from the data when the report is generated. The R code is in ngram_model.R and in the source of this report.

1. Getting the data

The data is the English part of the HC Corpora collection provided by Coursera and SwiftKey. It contains three files, each built from a different kind of text.

2. Basic summary of the data

Size of the three source files (all lines, before sampling)
Source File size (MB) Lines Words Words per line (median) Longest line (characters)
Blogs 200.4 899,288 37,334,131 28 40,833
News 196.3 1,010,242 34,372,530 31 11,384
Twitter 159.4 2,360,148 30,373,583 12 140

Some points worth highlighting:

  • The files range from 159 to 200 MB on disk, but differ in structure: Twitter has the most lines, while News has the most words per line (median of 31).
  • In total there are about 102.1 million words. That is far more than is needed, or than fits comfortably on a phone or a small web server, so the model below is built from a random 5% sample of the lines of each file.
Distribution of words per line in the sample (log scale)

Distribution of words per line in the sample (log scale)

The chart shows how differently the three sources are written. This matters for the model: short, informal tweets and longer, edited news and blog text use different words and phrases, so the model is trained on a mix of all three.

3. Cleaning the text

Before counting words, the text was cleaned so that “The”, “the” and “THE” count as the same word, and so that things a keyboard should not suggest are removed:

  • converted to lower case;
  • removed web addresses, e-mail addresses, Twitter handles and hashtags;
  • removed numbers, punctuation and non-English characters such as emoji (apostrophes are kept, so “don’t” stays one word);
  • split each line into sentences, so a word pair is never counted across the end of one sentence and the start of the next.

Common words such as “the” and “to” (often called stop words) are kept, because they are exactly the words people type most often and the words a keyboard most needs to suggest.

4. Word frequencies

The 15 most common words, word pairs (bigrams) and word triples (trigrams) in the training sample

The 15 most common words, word pairs (bigrams) and word triples (trigrams) in the training sample

How many distinct words are needed to cover a given share of all the words in the text

How many distinct words are needed to cover a given share of all the words in the text

Key findings

  • The training sample contains 4,536,540 words, but only 107,167 distinct words.
  • A small share of the vocabulary covers most of the text: the 142 most common words make up 50% of all words used, and 7,011 words make up 90%.
  • 48% of distinct words appear only once. A random selection of them: gurney’s, mokuro, turnkey, penulis, refusals, wilgeheuwel, rangeley, ballgown, sportsonesource, blg, lemasters, picanco.
  • Many word combinations are rare. 75% of distinct word pairs and 89% of distinct word triples appear only once in the sample.

The last two findings are the main way to make the model small: rare words and rare combinations take up a large share of the storage but are unlikely to be what a user wants suggested, so they can be dropped.

5. A first prediction model

How it works

The model is an n-gram model. It predicts the next word from the previous few words by looking up which words most often followed those same words in the training text. For example, after “thanks for the”, the words that most often come next are looked up and the most frequent ones are suggested.

  • It uses up to the last 3 words typed (a “4-gram” model), and also keeps tables for the last 2 words and the last 1 word.
  • Efficient storage (a Markov chain). Each table is stored as a lookup table where the key is the previous words (the state) and the values are a few candidate next words with their probabilities. A lookup is a fast indexed search, not a scan of the text.
  • Pruning. Word combinations seen only once are dropped, and for each set of previous words only the 5 most likely next words are kept, because the app only shows 3 suggestions.
  • Unseen word combinations (backoff). If the last 3 words were never seen together, the model “backs off” and tries the last 2 words, then the last word. If none of them were seen, it falls back to the most common words overall, so it always has a suggestion. This uses Stupid Backoff (Brants et al., 2007): each step back multiplies the score by 0.4, so a match on a longer phrase is preferred over a shorter one.

Example predictions

Typed text Top 3 suggestions
thanks for the follow, rt, mention
i would like to see, thank, be
at the end of the day, year, month
happy mothers day, and, out
the new york times, knicks, city
zqxv blorf the, to, and

The last example is made-up text: none of its words are known, so the model falls back to the most common words.

How good is it, how big and how fast?

To check the model honestly it was tested on the 46,959 held-back sentences it never saw during training. From these, 2,000 positions were picked at random; the model was given the preceding words and asked for its top 3 guesses for the word that actually came next.

Accuracy, memory and speed of model variants on held-out text
Words of context Min. count kept Size in memory (MB) Top-1 accuracy Top-3 accuracy Time per prediction (ms)
1 2 3.317 0.103 0.186 4.795
2 2 13.924 0.136 0.226 5.910
3 2 21.592 0.140 0.226 6.730
3 4 6.053 0.130 0.216 6.425
  • The main model (3 words of context) suggests the correct next word as its first choice 14.0% of the time, and among its 3 suggestions 22.6% of the time.
  • It takes about 21.6 MB of memory (measured with object.size()) and about 6.7 ms per prediction, which is fast enough to update suggestions as someone types. Building it took 15 seconds, but that is done once, in advance, not in the app.
  • The table shows the trade-off between size and accuracy: how much each extra word of context, and keeping rarer combinations, adds in accuracy compared with how much memory it costs. This will guide the final settings.

6. Answers to the design questions

  • Storage. One lookup table per n-gram length, keyed on the previous words (a Markov chain), holding only the top candidate next words and their probabilities.
  • Using word frequencies to shrink the model. Drop word combinations seen only once and keep only the top 5 next words per context. As shown in Section 4, many combinations appear only once, so this removes a large part of the data; the evaluation table shows what it costs in accuracy.
  • How big should n be? Up to 4 (3 words of context) for now. Each extra word of context makes the tables larger, and longer phrases are seen less often, so the gain shrinks; the evaluation table in Section 5 compares 1, 2 and 3 words of context to decide.
  • Smoothing. The simplest option, adding 1 to every count (“Laplace smoothing”), gives every possible word pair a small non-zero probability, but takes far too much probability away from common words. Backoff is used instead; Kneser-Ney smoothing is a better option to test for the final model.
  • Evaluation. Top-1 and top-3 accuracy on held-out text (what a user experiences), plus memory size and time per prediction. Perplexity, the standard measure of how “surprised” a model is by new text, needs properly normalised probabilities and will be added for the final model.
  • Backoff for unseen combinations. Stupid Backoff (Section 5). Katz backoff is the more rigorous version: it sets aside part of the probability of seen combinations, using Good-Turing discounting, and shares it out among unseen ones so the probabilities add up to 1. It will be compared with Stupid Backoff for the final model.

7. Plans for the final algorithm and app

Algorithm

  • Train on a larger sample, as far as the memory limits of the shinyapps.io server allow, and tune the pruning settings and the backoff factor using the held-out test data.
  • Compare Stupid Backoff with Katz backoff and Kneser-Ney smoothing, and add perplexity as a second measure of quality.
  • Store words as integer codes instead of text to cut the memory used.
  • Filter out profanity so it is never suggested.

Shiny app

  • A text box where the user types a phrase. The top 3 suggested next words appear as buttons below it, and clicking one adds it to the text.
  • The model is built in advance and saved as a single compressed .rds file, which the app loads once at start-up, so it starts quickly and each prediction takes only milliseconds.

Appendix: reproducibility

Session information for the run that produced this report:

## R version 4.6.1 (2026-06-24 ucrt)
## Platform: x86_64-w64-mingw32/x64
## Running under: Windows 11 x64 (build 26200)
## 
## Matrix products: default
##   LAPACK version 3.12.1
## 
## locale:
## [1] LC_COLLATE=Chinese (Simplified)_China.utf8 
## [2] LC_CTYPE=Chinese (Simplified)_China.utf8   
## [3] LC_MONETARY=Chinese (Simplified)_China.utf8
## [4] LC_NUMERIC=C                               
## [5] LC_TIME=Chinese (Simplified)_China.utf8    
## 
## time zone: America/Toronto
## tzcode source: internal
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] ggplot2_4.0.3       data.table_1.18.6.1
## 
## loaded via a namespace (and not attached):
##  [1] vctrs_0.7.3        cli_3.6.6          knitr_1.52         rlang_1.3.0       
##  [5] xfun_0.60          otel_0.2.0         S7_0.2.2           jsonlite_2.0.0    
##  [9] glue_1.8.1         htmltools_0.5.9    sass_0.4.10        scales_1.4.0      
## [13] rmarkdown_2.32     grid_4.6.1         evaluate_1.0.5     jquerylib_0.1.4   
## [17] fastmap_1.2.0      yaml_2.3.12        lifecycle_1.0.5    compiler_4.6.1    
## [21] RColorBrewer_1.1-3 rstudioapi_0.19.0  farver_2.1.2       digest_0.6.39     
## [25] R6_2.6.1           bslib_0.12.0       withr_3.0.3        tools_4.6.1       
## [29] gtable_0.3.6       cachem_1.1.0