# What algorithm(s) can be used to achieve reasonably good next word prediction?

What is a good way of implementing "next-word prediction"? For example, the user types "I am" and the system suggests "a" and "not" (or possibly others) as the next word. I am aware of a method that uses Markov Chains and some training text(obviously) to more or less achieve this. But I read somewhere that this method is very restrictive and applies to very simple cases.

I understand basics of neural networks and genetic algorithms(though have never used them in a serious project) and maybe they could be of some help. I wonder if there are any algorithms that, given appropriate training text(e.g., newspaper articles, and the user's own typing) can come up with reasonably appropriate suggestions for the next word. If not (links to)algorithms, general high-level methods to attack this problem are welcome.

Take a look at n-grams. One n-gram is a sequence of `n` words. In your case you want `n` to be `3`, since you need two `query words` and a `resulting word`. One 3-gram would be for example "I am tired", another one "I am happy".

What you then need is a collection of these 3-grams that are collected over your target language, say English. Since you cannot collect it over everything ever written in English you need to make a selection. That selection of representative texts is called a `corpus`. If your corpus is good it will tell you how often a sequence of three specific words occur together in English. From that you can calculate the probability of a 3-gram.

Collecting this kind of data is the hardest part. Once you have the list of all 3-grams together with their probability you can filter your list to all 3-grams starting with "I am". Then you sort all this list by probability et voilà: your prediction.

• Alright, and is there a optimal value of `n` that yields nice results? It doesn't always have to be the third word that is predicted, you see Commented May 13, 2012 at 9:02
• Well, a larger `n` yields a longer list which will give you a more precise prediction but is also more expensive to search in. So it's a tradeoff between precision and computation time. Commented May 13, 2012 at 9:35
• Also, you need a larger corpus for larger n-grams to be practically useful. Commented Jun 26, 2013 at 2:25
• um this is literally a Markov Chain... not only that, but literally the most textbook example ... Commented Jun 26, 2013 at 6:28

It looks like the problem domain is a subset of string search. By extending words to include white spaces, fuzzy string matching can be applied here.

You might want to consider/allow all user input as one word during training in addition to your dictionary. This allows you to suggest next word but also suggests auto complete of word or phrases.

Here is a link to a compilation of fuzzy string search algorithms

http://ntz-develop.blogspot.com/2011/03/fuzzy-string-search.html

You are looking for a (statistical) language model.

A statistical language model assigns a probability to a sequence of m words `P(w_1,...,w_m)` by means of a probability distribution...

In speech recognition and in data compression, such a model tries to capture the properties of a language, and to predict the next word in a speech sequence...

• Wow. But I think @sebastiangeiger's answer explains this for n=3. Commented Jun 1, 2012 at 12:42
• His answer describes a particular language model, namely n-gram models. There are other language models, e.g., syntactic language models (goo.gl/ffPOg). Commented Jun 5, 2012 at 6:26