一种基于N-Gram模型的模糊字符串相似度匹配实现
1.什么是N-Gram
N-Gram，或者称为N元模型，是NLP一种方法。本文主要用于展示N-Gram在评估字符串之间的差异程度的使用方法，并提供一种基于N-Gram的Bi-Gram实现。
2.N-Gram相似度匹配的理论基础
N-Gram方法主要是通过定义N-Gram距离来体现两个字符串之间的相似度。N-Gram通过将两个字符串切分成$x$个$n$长度的子串，并通过比较字串的之间的命中次数，来决定两个字符串的距离。这是因为我们认为，一个单字出现的概率与它之前的n-1个单字有关，而与任何其它单字都没有关系，那么如果我们有一个m个词组成的句子，其概率应为
$$
P(w_1,w_2,…w_m)
$$
那么根据链式法则，有
$$
P(w_1,w_2,…w_m) = p(w_1)×p(w_2|w_1)×p(w_3|w_2,w_1)×…p(w_m|w_1,…,w_{m-1})
$$
根据马尔科夫链的“无记忆”性质，我们假设这个链中的单字只与前方其$n-1$个单字有关，有
$$
P(w_1,w_2,…w_m) =\prod {i=1}^{m}P(w_i|w{i-1})
$$
我们以Bi-Gram(即$N=2$)方法为例
以一个字符串$s$为例，假设这个s的字串为”elpsycongroo”,那么一个Bi-Gram的拆分就为
$el, lp, ps, sy, yc, co, on, ng, gr, ro, oo, o$
我们又有一子串t,为”elpsy”,Bi-Gram拆分为$el,lp,ps,sy,y$。
以非重复的N-Gram分词来定义N-Gram距离，我们有如下公式。
$$
|GN_s|+|GN_t|−2×|GN_s∩GN_t|
$$
那么此例中
$$
\underline {el},\underline {lp},\underline {ps},\underline {sy},yc, co, on, ng, gr, ro, oo, o
$$
$$
\underline {el},\underline {lp},\underline {ps},\underline {sy},y
$$