How to structure a Predictive Keyboard project similar to GBoard

Question

Many are now familiar with GBoard, the Google / Android predictive Keyboard. I don't actually know how it works. Obviously it must gather usage data on the device where it is being used, but it probably also includes a database of general usage patterns, downloaded initially and perhaps updated periodically. (Well, that is how I would do it.) In this way, it would be like a spellcheck database that let the user add (and subtract: manger is not too good in a business context) words.

I have long been brushing aside the obvious question of "how does it do that?", but this morning as I was texting, I suddenly recalled the article in [Scientific American* (long ago, can't find it on the web) about Markov Chains and a simple program called Mark V. Shaney that would learn and then output words in a sensible order. That is how it could work. It should be quite easy to store and compress such a simple database.

The particular thing I am focusing on is how GBoard offers three word suggestions as I type, so that I can just pick words instead of typing the words in. The prediction is at the word level, not the letter level. What frustrates me is that it usually does not offer the proper tense for a word, making me type far more letters until the proper word shows up. For example: I want to type "He has started on it" and I type H and choose 'He' from the suggestions, then ha and pick 'has' then type sta and the suggestions are: start starts starting, none of which agree with has. Why doesn't it go right to started?

Has anyone implemented a similar project for analyzing and predicting or even uttering strings of words? It seems dead easy using Markov Chains. Do you think this would make a good project for using things like a 'dictionary' data structure to store words, and some kind of tree to encode the word association weights? Sounds like it would be very interesting to present-day students, already using the product.

---

The SciAm article mentioned is likely: Dewdney, A.K. (June 1989). "A potpourri of programmed prose and prosody; Computer Recreations; computer-generated commentary". Scientific American. 260 (6): 122–125. doi:10.1038/scientificamerican0689-122.

Answer 1

Markov Chains are great for putting out nonsense based on statistical data. However, a predictive keyboard that outputs nonsense isn't very useful. It needs much more context than a Markov Chain can produce. Such a program would base its next output entirely on the most recent entry.

That said, a project to do something like the Mark V. Shaney program might be fun in an Introduction to Data Structures course. However, it is unlikely that students would have previously seen Markov Chains at that point in their studies so some background in that would also need to be incorporated. Markov Chains might be taught in a Discrete Math course, but that usually comes later. Some schools might teach these two courses in tandem, however, making it a bit more feasible.

Such a project would, however, also have the advantage that the statistical basis (the Dictionary) used could introduce concepts of Big Data and how to process it.

You are correct that a predictive keyboard uses past data, but I'm pretty sure that it is based on a much more complex predictive model than could be provided by a Markov Chain. "Predictive Keyboard based on Markov Chains" is probably an oxymoron, though. You can do either or, but likely not both together.