jaro

参考链接地址如下：

https://www.cnblogs.com/huilixieqi/p/6493089.html

https://www.jb51.net/article/136217.htm

https://www.jb51.net/article/98449.htm

https://pypi.org/project/jaro_winkler/

https://blog.csdn.net/frone/article/details/80080850

关于编辑距离

此前计算短文本的相似度更多使用的是编辑距离(Levenshtein距离)，但是编辑距离更适合计算纯文本的差异，不考虑文本的顺序和含义，所以在相似文本较多，或者我们希望得到的相似文本更符合人的理解时，编辑距离给出的答案就不是那么理想了。

算法简介

The Jaro–Winkler distance (Winkler, 1990)是计算2个字符串之间相似度的一种算法。它是Jaro distance算法的变种。主要用于record linkage/数据连接（duplicate detection/重复记录）方面的领域，Jaro–Winkler distance最后得分越高说明相似度越大。Jaro–Winkler distance 是适合于串比如名字这样较短的字符之间计算相似度。0分表示没有任何相似度，1分则代表完全匹配。

算法定义

The Jaro distance算法最后得分公式： 

dj=13(m|s1|+m|s2|+m−tm)

dj=13(m|s1|+m|s2|+m−tm)

其中:

s1、s2 是要比对的两个字符

djdj是最后得分

m是匹配的字符数

t 是换位的数目

Match Window(匹配窗口)计算公式 

MW=(MAX(|s1|,|s2|)2)−1

MW=(MAX(|s1|,|s2|)2)−1

其中：

s1、s2 是要比对的两个字符

MW是匹配窗口值

上述公式解释

字符串s1与字符串s2在做匹配计算时，当两个字符的距离不大于公式二的最后结果(匹配窗口)即认为是匹配的。

当s1、s2中字符相匹配但是字符位置不一样时发生换位操作、而公式一中换位的数目t为不同顺序的匹配字符的数目的一半。比如:两个字符串CRATE和TRACE做匹配操作，字符串中仅有’R’ ‘A’ ‘E’三个字符是匹配的，即m=3。为什么’C’, ‘T’不算做是匹配的呢。因为虽然’C’, ‘T’都出现在两个字符串中，但是通过公式二得出匹配窗口值为 (5/2)-1=1.5。而两个字符串中’C’, ‘T’字符的距离均大于1.5。所以不算做匹配。因此t=0。在另一组字符串DwAyNE 与 DuANE 。匹配的字符D-A-N-E 在两个字符串中有相同的字符顺序，所以不需要进行换位操作，因此t=0,m=4。

Jaro–Winkler distance算法公式 

Jaro-Winkler算法给予了起始部分就相同的字符串更高的分数，它定义了一个前缀范围p，对于要匹配的两个字符串，如果前缀部分有长度为L的部分字符串相同，则Jaro-Winkler Distance为: 

dw=dj+L∗P(1−dJ)

dw=dj+L∗P(1−dJ)

其中:

djdj是Jaro distance最后得分

L是前缀部分匹配的长度

P是一个范围因子常量，用来调整前缀匹配的权值，但是P的值不能超过0.25，因为这样最后得分可能超过1分.Winkler的标准默认设置值P=0.1。

例子

给出两个字符串 s1 MARTHA 和 s2 MARHTA、我们可以得出：

m = 6

|s1| = 6

|s2| = 6

两组字符T/H和H/T要进行换位操作，因此t=2/2=1; 

我们可以根据公式一得出Jaro得分： 

dj=13(6|6|+6|6|+6−16)

dj=13(6|6|+6|6|+6−16)

如果使用Jaro–Winkler，并且取范围因子P=0.1,我们会得出: 

P=0.1 

L=3 

dw=0.944+(3∗0.1(1−0.944))=0.961dw=0.944+(3∗0.1(1−0.944))=0.961

python 运行

安装lib

pip install jaro_winkler

1

程序运行

print(jaro.jaro_metric("MARTHA".decode("utf-8"),"MARHTA".decode("utf-8")))

Levenshtein.distance(str1, str2)

计算编辑距离（也称Levenshtein距离）。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入、删除、替换。算法实现：动态规划。

Levenshtein.hamming(str1, str2)

计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应位置上不同字符的个数。

Levenshtein.ratio(str1, str2)

计算莱文斯坦比。计算公式 r = (sum – ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是类编辑距离。注意这里是类编辑距离，在类编辑距离中删除、插入依然+1，但是替换+2。

Levenshtein.jaro(s1, s2)

计算jaro距离，Jaro Distance据说是用来判定健康记录上两个名字是否相同，也有说是是用于人口普查，我们先来看一下Jaro Distance的定义。

4.其它算法涉及的相似度衡量方式

4.1基于拼音相似度的汉语模糊搜索算法

不同于传统的以关键词匹配为核心的匹配技术，这里提出基于拼音相似度的编辑距离来衡量汉字字符串之间的相似度。

论文提出三种编辑距离：基于汉字的编辑距离、基于拼音的编辑距离，以及基于拼音改良的编辑距离。

4.2最长公共子序列

（1）将两个字符串分别以行和列组成矩阵。

（2）计算每个节点行列字符是否相同，如相同则为1。

（3）通过找出值为1的最长对角线即可得到最长公共子串。

为进一步提升该算法，我们可以将字符相同节点的值加上左上角（d[i-1，j-1]）的值，这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

4.3最小编辑距离算法

（1）狭义编辑距离

设A、B为两个字符串，狭义的编辑距离定义为把A转换成B需要的最少删除（删除A中一个字符）、插入（在A中插入一个字符）和替换（把A中的某个字符替换成另一个字符）的次数，用ED（A，B）来表示。直观来说，两个串互相转换需要经过的步骤越多，差异越大。

（2）步骤

1.对两部分文本进行处理，将所有的非文本字符替换为分段标记“#”

2.较长文本作为基准文本，遍历分段之后的短文本，发现长文本包含短文本子句后在长本文中移除，未发现匹配的字句累加长度。

3.比较剩余文本长度与两段文本长度和，其比值为不匹配比率。

5.总结

衡量文本相似度的几种手段：

（1）最长公共子串（基于词条空间）

（2）最长公共子序列（基于权值空间、词条空间）

（3）最少编辑距离法（基于词条空间）

（4）汉明距离（基于权值空间）

（5）余弦值（基于权值空间）