什么是N-Gram？

N-Gram是一种在自然语言处理(NLP)中常用的一种概率语言模型(Probabilistic Language Model)，常用于语音\手写识别、机器翻译、拼写纠错等等领域。

它的本质就是计算一个句子或者一连串词出现的概率。

/*
T 是由 W1,W2,W3,W4,W5 ... Wn组成的一个句子。
*/

P(T) = P(W1,W2,W3,W4,W5 ... Wn) //这个句子出现的概率是里面每一个词出现的概率的叠加。

P(W5|W1,W2,W3,W4) //已经出现第1个至第4个的词的情况下，第5个词出现的概率。

比如：

I am working 后面很有可能出现at, in, for ，而不是refrigerator, throw, gull。那么如何计算N-Grams呢？我们可以使用链式法则(Chain Rule)，求多个关联事件并存时的概率：

• 2个事件同时发生的概率：P(a, b) = P(a | b) * P(b)
• 3个事件的概率链式调用：P(a, b, c) = P(a | b, c) * P(b, c) = P(a | b, c) * P(b | c) * P(c)
• 推广到N个事件，概率链式法则为：P(X1, X2, ... Xn) = P(X1 | X2, X3 ... Xn) * P(X2 | X3, X4 ... Xn) ... P(Xn-1 | Xn) * P(Xn)

但是这样会有两个问题：

1. 参数空间过大，不可能实用化。（N越大越难计算）
2. 数据稀疏严重，语言有各种各样的组合，数据量太大，无法获取这么全的数据。

所以为了简化这个问题，我们引入马尔科夫假设（Markov Assumption）：”一个词的出现仅仅依赖于它前面出现的一个或者有限的几个词。”

1. 如果一个词的出现仅仅依赖于它本身，我们称之为 Uni-gram model : P(T) = P(W1)P(W2)...P(Wn)
2. 如果一个词的出现仅仅依赖于它前面出现的一个词，我们称之为 Bi-gram model : P(T) = P(W1)P(W2|W1)P(W3|W2)...P(Wn|Wn-1)
3. 如果一个词的出现仅仅依赖于它前面出现的两个词，我们称之为 Tri-gram model : P(T) = P(W1)P(W3|W1,W2)...P(Wn|Wn-2,Wn-1)
4. 依次类推到仅依赖于它前面出现的N个词，还有4-gram, 5-gram。

下面用Bi-gram举个例子，语料库来自 [Berkeley Restaurant Project] ，总词数为 10132。