此处，|GN(s)|
是字符串 s
的 N-Gram集合，N 值一般取2或者3。以 N = 2 为例对字符串Gorbachev和Gorbechyov进行分段，可得如下结果（我们用下画线标出了其中的公共子串）。
结合上面的公式，即可算得两个字符串之间的距离是8 + 9 − 2 × 4 = 9。显然，字符串之间的距离越小，它们就越接近。当两个字符串完全相等的时候，它们之间的距离就是0。
利用N-Gram计算字符串间距离的Java实例
在一书中，我们给出了在C++下实现的计算两个字符串间N-Gram距离的函数，鉴于全书代码已经在本博客中发布，这里不再重复列出。事实上，很多语言的函数库或者工具箱中都已经提供了封装好的计算 N-Gram 距离的函数，下面这个例子演示了在中使用N-Gram 距离的方法。
针对这个例子，这里需要说明的是：
调用函数需要引用lucene的JAR包，我所使用的是lucene-suggest-5.0.0.jar
前面我们所给出的算法计算所得为一个绝对性的距离分值。而Java中所给出的函数在此基础上进行了归一化，也就是说所得之结果是一个介于0~1之间的浮点数，即0的时候表示两个字符串完全不同，而1则表示两个字符串完全相同。
import org.apache.lucene.search.spell.*;
public class NGram_distance {
public static void main(String[] args) {
NGramDistance ng = new NGramDistance();
float score1 = ng.getDistance("Gorbachev", "Gorbechyov");
System.out.println(score1);
float score2 = ng.getDistance("girl", "girlfriend");
System.out.println(score2);
}
}
有兴趣的读者可以在引用相关JAR包之后在Eclipse中执行上述Java程序，你会发现，和我们预期的一样，字符串Gorbachev和Gorbechyov所得之距离评分较高（=0.7），说明二者很接近；而girl和girlfriend所得之距离评分并不高（=0.3999），说明二者并不很接近。
利用N-Gram模型评估语句是否合理
从现在开始，我们所讨论的N-Gram模型跟前面讲过N-Gram模型从外在来看已经大不相同，但是请注意它们内在的联系（或者说本质上它们仍然是统一的概念）。
为了引入N-Gram的这个应用，我们从几个例子开始。首先，从统计的角度来看，自然语言中的一个句子 s
可以由任何词串构成，不过概率 P(s)
有大有小。例如：
s1
= 我刚吃过晚饭
s2
= 刚我过晚饭吃
显然，对于中文而言 s1
是一个通顺而有意义的句子，而s2
则不是，所以对于中文来说，P(s1)>P(s2)
。但不同语言来说，这两个概率值的大小可能会反转。
其次，另外一个例子是，如果我们给出了某个句子的一个节选，我们其实可以能够猜测后续的词应该是什么，例如
the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?
显然，如果我们知道这个句子片段更多前面的内容的情况下，我们会得到一个更加准确的答案。这就告诉我们，前面的（历史）信息越多，对后面未知信息的约束就越强。
如果我们有一个由 m
个词组成的序列（或者说一个句子），我们希望算得概率 P(w1,w2,⋯,wm)
，根据链式规则，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)
这个概率显然并不好算，不妨利用马尔科夫链的假设，即当前这个词仅仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上诉算式的长度。即P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)
特别地，对于 n
取得较小值的情况当 n=1
, 一个一元模型（unigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi)
当 n=2
, 一个二元模型（bigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−1)
当 n=3
, 一个三元模型（trigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−2wi−1)
接下来的思路就比较明确了，可以利用最大似然法来求出一组参数，使得训练样本的概率取得最大值。
对于unigram model而言，其中c(w1,..,wn)
表示 n-gram w1,..,wn
在训练语料中出现的次数，M
是语料库中的总字数（例如对于 yes no no no yes 而言，M=5
）P(wi)=C(wi)M
对于bigram model而言，P(wi|wi−1)=C(wi−1wi)C(wi−1)
对于n
-gram model而言，P(wi|wi−n−1,⋯,wi−1)=C(wi−n−1,⋯,wi)C(wi−n−1,⋯,wi−1)
来看一个具体的例子，假设我们现在有一个语料库如下，其中<s1><s2>
是句首标记，</s2></s1>
是句尾标记：
<s1><s2>yesnonononoyes</s2></s1><s1><s2>nononoyesyesyesno</s2></s1>
下面我们的任务是来评估如下这个句子的概率：<s1><s2>yesnonoyes</s2></s1>
我们来演示利用trigram模型来计算概率的结果P(yes|<s1><s2>)=12,P(no|<s2>yes)=1P(no|yesno)=12,P(yes|nono)=25P(</s2>|noyes)=12,P(</s1>|yes</s2>)=1
所以我们要求的概率就等于：12×1×12×25×12×1=0.05
再举一个来自文献[1]的例子，假设现在有一个语料库，我们统计了下面一些词出现的数量
下面这个概率作为其他一些已知条件给出：P(i|<s>)=0.25P(english|want)=0.0011P(food|english)=0.5P(</s>|food)=0.68
下面这个表给出的是基于Bigram模型进行计数之结果例如，其中第一行，第二列 表示给定前一个词是 “i” 时，当前词为“want”的情况一共出现了827次。据此，我们便可以算得相应的频率分布表如下。
因为我们从表1中知道 “i” 一共出现了2533次，而其后出现 “want” 的情况一共有827次，所以P(want|i)=827/2533≈0.33
现在设s1=“<s>iwantenglishfood</s>”
，则可以算得P(s1)=P(i|<s>)P(want|i)P(english|want)P(food|english)P(</s>|food)=0.25×0.33×0.0011×0.5×0.68=0.000031
Eg.2 某某作家或者语料库风格的文本自动生成。这是一个相当有趣的话题。来看下面这段话（该例子取材自文献【1】）：
“You are uniformly charming!” cried he, with a smile of associating and now and then I bowed and they perceived a chaise and four to wish for.
你应该还没有感觉到它有什么异样吧。但事实上这并不是由人类写出的句子，而是计算机根据Jane Austen的语料库利用trigram模型自动生成的文段。（Jane Austen是英国著名女作家，代表作有《傲慢与偏见》等）
再来看两个例子，你是否能看出它们是按照哪位文豪（或者语料库）的风格生成的吗？
This shall forbid it should be branded, if renown made it empty.
They also point to ninety nine point six billion dollars from two hundred four oh three percent of the rates of interest stores as Mexico and Brazil on market conditions.
答案是第一个是莎士比亚，第二个是华尔街日报。最后一个问题留给读者思考，你觉得上面两个文段所运用的n-gram模型中，n应该等于多少？
推荐阅读和参考文献：
[1] Speech and Language Processing. Daniel Jurafsky & James H. Martin, 3rd. Chapter 4[2] 本文中的一些例子和描述来自 北京大学 常宝宝 以及 The University of Melbourne “Web Search and Text Analysis” 课程的幻灯片素材