How would I go about predicting the next word in a sentence if I have a n-gram model available? A intuitive solution would be to just ask the probability of all the words that can come next and see which has the highest. But this would be dreadfully slow if I have a very large set of n-grams wouldn't it?
If anyone could point me in the right direction that would be great!
Here is what I have so far. We have a data structure and this data structure will allow lookup of context(so the previous words) via hashing. This can be done in O(m) with m the length of the context but since this is always very short it is safe to say lookup can be done in O(1). Now let's say the previous words are "I want to" I would look this up in my ngram model in O(1) time and then check all the possible words that could follow and check which has the highest chance to come next. But with something as generic as "I want to" I can imagine this would be quite a few words. Our application must run on mobile devices so I would like to know if there is a more efficient way to get the word with the highest chance. I was thinking about maybe sorting the ngrams but since we are using some sort of hashtable this isn't really an option.
The more I think about this however the more I realize that even if it would be lets say 500 words that can come next, that this is still a fairly small number and even a slow processor could easily go over those very quickly so maybe I am over thinking things.