With N-Grams, N represents the number of words you want to use to predict the next word.
You take a corpus or dictionary of words and use, if N was 5, the last 5 words to predict the next. I will use letters (characters, to predict the next letter in the sequence, as this it will be less typing :D) as an example.
Say you have a corpus or input stream such as wwwaasssssdddaawww ?
Let us use bi-grams (n=2) and we want to predict the next character in the sequence: ?
To do this, we first get all the distinct letters: w,a,s,d
Next, we define a prefix as being the past (most recent) 2 letters: prefix = ww.
We then want to know, given the last two letters were ww, what is the probability of seeing another w? an a? a s? a d?
The first thing to do is work out how many times the prefix appears: 4 times.
So, we build our frequency distribution and we see that within the corpus, a w appears after the sequence ww twice. An a appears 1 time after ww, s appears 0 and d appears 0 times.
From this, we can conclude that the probability of seeing a w next, is 4/2 = 2/4 = 50%. An a: 25%, s: 0, d: 0.
Obviously, having zero probability is not correct. If the words are unknown, you can assign them some dummy character/word like ???. If the words are not unknown, but just not seen given the prefix, you should use some sort of smoothing algorithm (like Laplace).
That is the 'just' of it. I learned about N-Grams from the following resource: https://lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf
As for your data issue... You can create a data structure where each unique possible prefix is the key in, for example, a dictionary.
Your dictionary keys would look something like this (based on the above corpus):
'ww', 'wa', 'aa', 'as', 'ss', 'sd', 'dd', 'da', 'aw'
Every time you encounter a new unique prefix, you add a new entry to your dictionary.
Each key in the dictionary could have an object as a value with n-properties, where n is the number of distinct possible words/characters and each stores the count of observations (initialised to 0). EG:
'ww': w = 0,a = 0,s = 0,d = 0
Then every time you see a word/letter come in, you grab the prefix (in our case ww) and increment the count for the observed character/word:
'ww': w = 2, a = 1, s = 0, d = 0
Now when you see another ww and then get a w, just increment...
'ww': w = 3, a = 1, s = 0, d = 0
To get the probability, just grab the KVP for the given prefix, choose the property with the greatest count and divide it by the number of unique properties.
This means that instead of storing aaaaaall the data, you are just storing counts! Much more data efficient. Further, information is the far past may not be a very good indicator of what is likely to be seen in the near future, so you could limit your corpus to say, 1000 wrods... as they come in, you remove the oldest and add the new incoming one (a stack...), but you will have to play a bit to find out what works best.
Hope this helps!
