levenshtein
python_Levenshtein
该包中的几个计算字串相似度的几个函数实现。
- Levenshtein.hamming(str1, str2)
计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应位置上不同字符的个数。如
- Levenshtein.distance(str1, str2)
计算编辑距离（也成Levenshtein距离）。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入、删除、替换。
- Levenshtein.ratio(str1, str2)
计算莱文斯坦比。计算公式 r = (sum - ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是类编辑距离
注意：这里的类编辑距离不是2中所说的编辑距离，2中三种操作中每个操作+1，而在此处，删除、插入依然+1，但是替换+2
这样设计的目的：ratio(‘a’, ‘c’)，sum=2,按2中计算为（2-1）/2 = 0.5,’a’,’c’没有重合，显然不合算，但是替换操作+2，就可以解决这个问题。
- Levenshtein.jaro(s1, s2)
计算jaro距离，
其中的m为s1, s2的匹配长度，当某位置的认为匹配 当该位置字符相同，或者在不超过 t是调换次数的一半
- Levenshtein.jaro_winkler(s1, s2)
计算Jaro–Winkler距离
#include
#include
int minvalue(int a, int b, int c)
{
int min = a > b ? b : a;
min = min > c ? c : min;
return min;
}
int same(int a, int b)
{
if (a != b)
return 1;
else
return 0;
}
int main()
{
char a[] = "bca";
char b[] = "abc";
int lena = strlen(a);
int lenb = strlen(b);
int c[lena+1][lenb+1], i, j;
for(i=0; i <= lena; i++)
c[i][0] = i;
for(i=0; i <= lenb; i++)
c[0][i] = i;
for(i = 1; i <= lena; i++)
for(j=1; j <= lenb; j++)
c[i][j] = minvalue(c[i-1][j]+1, c[i][j-1]+1, (c[i-1][j-1]+same(a[i], b[j])));
for(i=0; i <= lena; i++)
{
for(j=0; j <= lenb; j++)
printf("%d\t", c[i][j]);
printf("\n");
}
printf("Lavenshtein distance:%d\n", c[lena][lenb]);
return 0;
}
https://www.php.net/manual/en/function.levenshtein.php
Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量（string metric）。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如修改、插入、删除）所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。
简单例子
从字符串“kitten”修改为字符串“sitting”只需3次单字符编辑操作，如下：
sitten ( k -> s )
sittin ( e -> i )
sitting ( _ -> g )
因此“kitten”和“sitting”的Levenshtein距离为3。
实现思想
如何编程实现这一算法呢？许多人试图用矩阵来解释，但实际上矩阵是最终可视化的工具，配合理解“为什么”比较方便，但从矩阵却比较难想到“怎么做”。
我们试图找到“从字符串𝐴修改到字符串𝐵”这一问题的子解结构。当然反过来说“从字符串𝐵修改到字符串𝐴”和它是同一个问题，因为从𝐴中删掉一个字符来匹配𝐵，就相当于在𝐵中插入一个字符来匹配𝐴，这两个操作是可以互相转化的。
Levenshtein 距离是一种编辑距离，用来表示两个字符串的差异。编辑距离是指从字符串 A 开始，修改成字符串 B 的最小步骤数，每个以步骤中，你可以删除一个字符、修改一个字符或者新增一个字符。
比如我们把 acat 变成 gate 的时候，需要做如下的修改：
删除 a
把 c 改成 g
新增 e
所以 acat 和 gate 的 Levenshtein 距离是 3。
算法
这里使用动态规划的方式来实现。
记 Levenshtein 距离为 l(i, j)，i 是字符串 A 中从开头到第 i 个下标的子字符串，j 是字符串 B 从开头到第 j 个下标的子字符串，i 和 j 都从 0 开始。
如果 A 中第 i + 1 个字符和 B 中第 j + 1 个字符串相同的话，l(i + 1, j + 1) = min( l(i, j), l(i + 1, j) + 1, l(i, j + 1) + 1)。是把这次添加操作和 l(i + 1, j) 相比是添加了一个字符，和 l(i, j + 1) 相比也是。所以这种情况下只要求得这三种情况下的最小值，就可以得到下一个值了。
相似地，如果 A 中第 i + 1 个字符和 B 中第 j + 1 个字符串不相同的话，l(i + 1, j + 1) = min( l(i, j) + 1, l(i + 1, j) + 1, l(i, j + 1) + 1)。差别是这次操作需要修改一个字符，也就是要在 l(i, j) 上加一步。
算法基本原理：假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值），表示将串s[ 1…i ] 转换为 串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在i等于0时，也就是说串s为空，那么对应的d[0,j] 就是 增加j个字符，使得s转化为t，在j等于0时，也就是说串t为空，那么对应的d[i,0] 就是 减少 i个字符，使得s转化为t。
然后我们考虑一般情况，加一点动态规划的想法，我们要想得到将s[1..i]经过最少次数的增加，删除，或者替换操作就转变为t[1..j]，那么我们就必须在之前可以以最少次数的增加，删除，或者替换操作，使得现在串s和串t只需要再做一次操作或者不做就可以完成s[1..i]到t[1..j]的转换。所谓的“之前”分为下面三种情况：
1）我们可以在k个操作内将 s[1…i] 转换为 t[1…j-1]
2）我们可以在k个操作里面将s[1..i-1]转换为t[1..j]
3）我们可以在k个步骤里面将 s[1…i-1] 转换为 t [1…j-1]
针对第1种情况，我们只需要在最后将 t[j] 加上s[1..i]就完成了匹配，这样总共就需要k+1个操作。
针对第2种情况，我们只需要在最后将s[i]移除，然后再做这k个操作，所以总共需要k+1个操作。
针对第3种情况，我们只需要在最后将s[i]替换为 t[j]，使得满足s[1..i] == t[1..j]，这样总共也需要k+1个操作。而如果在第3种情况下，s[i]刚好等于t[j]，那我们就可以仅仅使用k个操作就完成这个过程。
最后，为了保证得到的操作次数总是最少的，我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。
算法基本步骤：
（1）构造 行数为m+1 列数为 n+1 的矩阵 , 用来保存完成某个转换需要执行的操作的次数，将串s[1..n] 转换到 串t[1…m] 所需要执行的操作次数为matrix[n][m]的值；
（2）初始化matrix第一行为0到n，第一列为0到m。
Matrix[0][j]表示第1行第j-1列的值，这个值表示将串s[1…0]转换为t[1..j]所需要执行的操作的次数，很显然将一个空串转换为一个长度为j的串，只需要j次的add操作，所以matrix[0][j]的值应该是j，其他值以此类推。
（3）检查每个从1到n的s[i]字符；
（4）检查每个从1到m的s[i]字符；
（5）将串s和串t的每一个字符进行两两比较，如果相等，则让cost为0，如果不等，则让cost为1（这个cost后面会用到）;
(6)a、如果我们可以在k个操作里面将s[1..i-1]转换为t[1..j]，那么我们就可以将s[i]移除，然后再做这k个操作，所以总共需要k+1个操作。
b、如果我们可以在k个操作内将 s[1…i] 转换为 t[1…j-1] ，也就是说d[i,j-1]=k，那么我们就可以将 t[j] 加上s[1..i]，这样总共就需要k+1个操作。
c、如果我们可以在k个步骤里面将 s[1…i-1] 转换为 t [1…j-1]，那么我们就可以将s[i]转换为 t[j]，使得满足s[1..i] == t[1..j]，这样总共也需要k+1个操作。（这里加上cost，是因为如果s[i]刚好等于t[j]，那么就不需要再做替换操作，即可满足，如果不等，则需要再做一次替换操作，那么就需要k+1次操作）
因为我们要取得最小操作的个数，所以我们最后还需要将这三种情况的操作个数进行比较，取最小值作为d[i,j]的值；
d、然后重复执行3,4,5,6，最后的结果就在d[n,m]中；
在信息论、语言学和计算机科学中，Levenshtein distance是用于测量两个字符串之间差异的字符串度量。非正式的说就是两个单词之间的Levenshtein distance是将一个单词更改为另一个单词所需的单字符编辑（插入，删除或替换）的最小步骤。
它以苏联数学家弗拉基米尔·莱文斯坦（Vladimir Levenshtein）的名字命名，作者在1965年提出的这个算法。
Levenshtein distance也可以称为编辑距离，尽管该术语也可以表示更大的距离度量系列。
Levenshtein distance与成对字符串对齐密切相关。
算法的上下界限
Levenshtein distance数值包含几个上下界限
距离最小是两个字符串之间的长度的差值
距离最大是两个字符串中较长字符串的长度
当且仅当字符串相同时长度为0
当字符串的长度相同时，距离的最大长度是 Hamming distance （下面会介绍一下）
两个字符串之间的距离小于等于与另外一个字符串距离之和（三角形等式 a+b<c）
Hamming distance 是两个相同长度的字符串从头开始分别比对两个字符串对应字符位置的值是否相同，不相同则距离加1，最后得到的结果就是 Hamming distance
例如abcd、abhg的距离为2，abcd、bcda的距离是4
三：应用场景
1：数据对齐
笔者在做一个关联网络项目时，后台有两种特别数据：地址和公司，这两种数据都是用 户自己输入的数据，所以特点就是同一个地点可能有多种不同的字符串，就比如同一个地点：“北京市朝阳区IT产业园“，在后台数据中可能有“北京朝阳区IT产业园”或者“北京朝阳区it园”等一系列数据，我们又不能去做模糊查询（因为节点数据和边关系为千万级的，模糊查询可能会匹配到大量的节点返回导致返回大量的数据影响项目稳定），我们就采用了数据对齐的方式解决这个问题，当用户输入一个地址时，我们通过编辑距离算法就可以获取到其他相关的数据显示出来，就可以达到一个比较好的效果。具体的实现步骤就不在此介绍了。
2：拼写纠错
笔者所在公司就有一个公司内部提供的拼写纠错的组件，其中就有一部分使用了编辑距离算法。下面是组件的简单介绍：
纠错主要解决 query 中输入错误的情况，比如 query 为拼音，query中包含同音错别字或不同音的别字，漏字的情况等等。 本纠错主要基于两种规则：拼音纠错和编辑距离纠错。 离线主要生成两个词典，即拼音词典和编辑距离词典。来源词典主要来自于 cmc 数据，小区数据，topquery，以及白名单数据等。通过 **脚本 生成拼音词典和编辑距 离词典。脚本执行完之后，会在 ***目录 下生成词典数据。拼音词典的生成主要是将来源词典中的词转换为拼音，编辑距离词典的生成主要是省略某个字或者某个拼音的字母生成的。生成字典的代码在 tool 下。 在线纠错逻辑 通过 make 编译代码可以生成 so 目录下的动态链接库。 对外提供的是 java RPC 服务，通过 java jni 链接 c++动态链接库。
主要纠错逻辑如下：首先对 query 解析，判断是全拼音或包含中文。若全是拼音，则会直接走对应的拼音纠错召回结果，如果不能通过拼音解决，再走编辑距离召回，解决是否漏字母的情况；若是部分中文或全中文的 query，则先进行拼音纠错，解决同音错别字问题，若无召回，则先进行分词，将前后相邻 term 拼接在一起进行拼音和编辑距离的召回。
四：其他的编辑距离算法
还有很多流行的编辑距离算法，他们和Levenshtein distance算法不同是使用了不同种类的方式去变换字符串
Damerau–Levenshtein distance: 可以对字符串进行插入、删除、替换、相邻两个字符之间的交换
longest common subsequence (LCS) distance ：只允许对字符串进行插入、删除、替换
Hamming distance ： 允许对字符串进行替换，只可用于计算两个相同长度字符串的编辑距离
Jaro distance ：只允许对字符串进行交换
编辑距离通常定义为使用一组特定允许的编辑操作来计算的可参数化度量，并为每个操作分配成本（可能是无限的）
