I have implemented N-grams by constructing a tree (or a trie, technically) that stores frequencies of each N-gram. Each path in the tree represents an N-gram and its frequency: the path consists of N nodes (each node containing a word), followed by a leaf node containing the frequency. So, each path in the tree is of length N + 1.
I'm now trying to compute the probability of observing a given sentence, and am having some trouble, particularly when N > 2.
For the sentence
<s> Hello world </s> using N = 1, the probability is
P(<s>) * P(Hello) * P(world) * P(</s>).
Using N = 2, the probability is
P(Hello | <s>) * P(world | Hello) * P(</s> | world).
But for N = 3, I'm not sure what to do. If I compute
P(Hello | <s>) * P(world | <s> Hello), then my tree will give an error since
<s> Hello is a bigram and the tree is only defined for trigrams.
I considered maybe wrapping each sentence an additional time, e.g.
<s> <s> Hello world </s> </s> then computing
P(Hello | <s> <s>) * P(world | <s> Hello) * P(</s> | Hello world) * P(</s> | world </s>), but this seems non-intuitive and involves mutating the corpus in an ugly way.
What is the proper way to compute this probability?