<p>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. </p>

<p>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. </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 4.0
2018-06-13T18:31:07.483Z
OK, well I might be ignorant about the particulars of Markov Chains, having read about them 30 years ago, so that is fine. But some sort of weighted prediction (more like a tree) is obviously being used to drive the keyboard thing, because I can often type an entire text message just by picking one of the three suggestions for next word on my phone. Pretty good prediction, if you ask me! (Have you used that feature?) The frustrating thing is how the options move position as I type, so I am reaching for the leftmost one and by the time I touch there, it has moved to the center position. Ugh!
Scott Rowe
CC BY-SA 4.0
2018-06-15T13:44:06.147Z
Scott, the same thing happens to me!  My fingers aren't fast enough.  Usually the data structure used for predictive typing is a TRIE - here's one article on how to do it in Javascript: [link] (https://medium.com/@dookpham/predictive-text-autocomplete-using-a-trie-prefix-tree-data-structure-in-javascript-part-1-6ff7fa83c74b)
Java Jive
CC BY-SA 4.0
2018-06-13T17:54:36.533Z
2018-06-13T17:59:51.233Z
2018-06-13T17:59:51.233Z
Buffy
<p>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: <em>manger</em> is not too good in a business context) words.</p>

<p>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 <strong><a href="https://en.wikipedia.org/wiki/Markov_chain" rel="nofollow noreferrer">Markov Chains</a></strong> and a simple program called <a href="https://en.wikipedia.org/wiki/Mark_V._Shaney" rel="nofollow noreferrer">Mark V. Shaney</a> 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.</p>

<p>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 <em>has</em>. Why doesn't it go right to <em>started</em>?</p>

<p>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.</p>

<hr>

<p>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. </p>

CC BY-SA 4.0
2018-06-13T15:07:34.123Z
Hi Scott, I put the question into the header to make the topicality clearer. If I made a mistake, feel free to revert.
Ben I.
CC BY-SA 4.0
2018-06-13T18:36:15.310Z
@Buffy Thanks for locating the article and putting it in the question!
Scott Rowe
CC BY-SA 4.0
2018-06-13T19:32:00.910Z
You should check out http://kingjamesprogramming.tumblr.com/ Which is "Posts generated by a Markov chain trained on the King James Bible, Structure and Interpretation of Computer Programs, and some of Eric S. Raymond's writings Run by Michael Walker (barrucadu)."
Adam
CC BY-SA 4.0
2018-06-14T14:37:58.673Z
@Adam in the original article, it gave an excerpt of some emitted text, which included something like: " '*The simulacrum is true' -- Ecclesiastes*"
Scott Rowe
<lesson-ideas><algorithms><cs-theory><data-structure><artificial-intelligence>
How to structure a Predictive Keyboard project similar to GBoard
# How to structure a Predictive Keyboard project similar to GBoard

(Asked by: username_0 on 2018-06-13)

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](https://en.wikipedia.org/wiki/Markov_chain)** and a simple program called [Mark V. Shaney](https://en.wikipedia.org/wiki/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.

**Tags:** lesson-ideas, algorithms, cs-theory, data-structure, artificial-intelligence

> **Comments:**
> **username_1**: Hi Scott, I put the question into the header to make the topicality clearer. If I made a mistake, feel free to revert.  
> **username_0**: @username_3 Thanks for locating the article and putting it in the question!  
> **username_2**: You should check out http://kingjamesprogramming.tumblr.com/ Which is "Posts generated by a Markov chain trained on the King James Bible, Structure and Interpretation of Computer Programs, and some of Eric S. Raymond's writings Run by Michael Walker (barrucadu)."  
> **username_0**: @username_2 in the original article, it gave an excerpt of some emitted text, which included something like: " '*The simulacrum is true' -- Ecclesiastes*"  

---

## 1 answers

### Answer by username_3 on 2018-06-13. Score: 2

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.

> **Comments:**
> **username_0**: OK, well I might be ignorant about the particulars of Markov Chains, having read about them 30 years ago, so that is fine. But some sort of weighted prediction (more like a tree) is obviously being used to drive the keyboard thing, because I can often type an entire text message just by picking one of the three suggestions for next word on my phone. Pretty good prediction, if you ask me! (Have you used that feature?) The frustrating thing is how the options move position as I type, so I am reaching for the leftmost one and by the time I touch there, it has moved to the center position. Ugh!  
> **username_4**: Scott, the same thing happens to me!  My fingers aren't fast enough.  Usually the data structure used for predictive typing is a TRIE - here's one article on how to do it in Javascript: [link] (https://medium.com/@dookpham/predictive-text-autocomplete-using-a-trie-prefix-tree-data-structure-in-javascript-part-1-6ff7fa83c74b)  

---

