【2.3.2】字符串编辑距离--JaroWinklerDistance

一、概述

Jaro-Winkler Distance是一个度量两个字符序列之间的编辑距离的字符串度量标准,是由William E. Winkler在1990年提出的Jaro Distance度量标准的一种变体。Jaro Distance是两个单词之间由一个转换为另一个所需的单字符转换的最小数量。Jaro-Winkler Distance通过前缀因子p使Jaro Distance相同时共同前缀长度l越大的相似度越高。Jaro–Winkler Distance越小,两个字符串越相似。如果分数是0,则表示完全不同,分数为1则表示完全匹配。Jaro–Winkler相似度是1 - Jaro–Winkler Distance。

二、Jaro相似度

对于给定的两个字符串\(S_{1}\) 和\(S_{2}\),相似度\(Sim_{j}\),计算公式如下:

$$ Sim_{j} = \begin{cases} 0 & \text{if m=0} \\ \frac{1}{3}\left ( {\frac{m}{\left | {S_{1}} \right |}}+{\frac{m}{\left | {S_{2}} \right |}}+{\frac{m-t}{m}} \right ) & \text{otherwise} \end{cases} $$

其中:

  • \(\left | {S_{i}} \right | \)是字符串\({S_{i}} \)的长度。
  • m是匹配的字符数量。
  • t是字符转换的次数。

只有当\( S_{1} \) 和\(S_{2}\)的字符相同,且距离不超过 \( \left \lfloor \frac{max(\left | S_{1} \right |,\left |S_{2}\right |)}{2} \right \rfloor-1 \)时才认为两个字符是匹配的。将 \(S_{1}\)与\(S_{2}\)匹配的字符进行比较,相同位置但字符不同的字符数除以2就是要转换的次数t。

二、Jaro-Winkler相似度

对于给定的两个字符串\( S_{1} \)和\(S_{2}\),相似度\(Sim_{w}\),计算公式如下:

$$ Sim_{w}=Sim_{j}+\left ( lp \left (1- Sim_{j} \right )\right ) $$

其中:

  • \(Sim_{j}\)是\(S_{1}\) 和\(S_{2}\)的Jaro相似度。
  • l是字符串公共的前缀长度,最大值为4。
  • p是一个常量因子,对于有公共前缀的分数会向上调整,p不能超过0.25,否则相似度会超过1,常量p的默认值为0.1。

三、例子

三个单词\( S_{1}\)、\(S_{2}\)、\(S_{3}\)分别为aboard、abroad、aborad,分为两组进行比较\( S_{1}\)、\( S_{2}\)和\( S_{1}\)、\( S_{3}\)。

Jaro Distance相似度

根据Jaro Distance算法\( S_{1}\)、\(S_{2}\)匹配的字符数为m为6,需要转换的字符为o、a、r,所以转换次数t为3/2=1

它们的Jrao相似度为\( Sim_{s_{1}s_{2}}=\frac{1}{3}\left ( {\frac{6}{6}}+{\frac{6}{6}}+{\frac{6-1}{6}} \right )=0.944\cdots。\)

而\( S_{1}\)、\( S_{3}\)匹配的字符数为m为6,需要转换的字符为a、r,所以转换次数t为2/2=1。

它们Jrao相似度为\( Sim_{s_{1}s_{3}}=\frac{1}{3}\left ( {\frac{6}{6}}+{\frac{6}{6}}+{\frac{6-1}{6}} \right )=0.944\cdots \)


Jaro-Winkler相似度

此时\( S_{1}\)与\( S_{2}\)和\( S_{3}\)的Jaro相似度相同,无法判断\( S_{1}\)与哪个更相似,此时可以通过Jaro-Winkler Distance算法对Jaro相似度进行调整,假设常量因子p为0.25。


\( S_{1}\)、\( S_{2}\)匹配字符的共同前缀ab的长度l为2小于4,

所以它们的Jaro-Winkler相似度为 \( Sim_{w_{S1S2}}=0.944+\left ( 2*0.25 \left (1- 0.944 \right )\right )=0.972 \)。

而\( S_{1}\)、\( S_{3}\)匹配字符的共同前缀abo的长度l为3小于4,

所以它们的Jaro-Winkler相似度为\( Sim_{w_{S1S3}}=0.944+\left ( 3*0.25 \left (1- 0.944 \right )\right )=0.986 \)。

Jaro相似度相同的通过Jaro-Winkler Distance调整后可以比较出与哪个更相似。如上\( S_{1}\)与\( S_{3}\)更相似。

参考资料

https://blog.csdn.net/asty9000/article/details/81348857

这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn