一种基于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
$$

两个字符串之间的距离计算如下：
$$
(12+5)-2×4=9
$$
将其Normalize,则
$$
\frac {9-0}{17-0}=0.529
$$
如果两者完全一样，则值为0，如果两者完全不同，则值为1。

3.基于JavaScript的实现

我们想将这个模糊相似度匹配机制用于爬虫的信息过滤中，即如果两个房子的发布信息是同一房子多次发布，我们能够实现将其过滤掉的功能。

Bi-Gram实现代码如下：

function biGramComp(s,t){
   let sSet = new Set();
   let tSet = new Set();

   let sArr = s.split("");
   let tArr = t.split("");
   let hit = 0;
   
   for(let i=0;i<sArr.length;i++){
      let str = sArr[i];
      if(sArr[i+1]!= null){
          str += sArr[i+1];
      }
      sSet.add(str);
   }

   for(let i=0;i<tArr.length;i++){
       let str = tArr[i];
       if(tArr[i+1] != null){
           str += tArr[i+1];
       }
      tSet.add(str);
   }
   
   for(let item of sSet){
       if(tSet.has(item)) hit++;
   }
   
   let size = sSet.size + tSet.size;
   let correlate = size - 2*hit; 
   let normal = correlate/size;
   
   return normal; 
}

如果将测试字符串输入“elpsycongroo”和’”elpsy”得到答案为0.529，符合我们的预期。如果输入字符串”233”和“2333333333”则得到答案0，即两字符串为同一字符串，如果输入字符串”Basement房子”和”1234567”的答案1,即两字符串完全无关，亦符合我们的预期。

# filter, ngram

一种基于N-Gram模型的模糊字符串相似度匹配实现