数据对齐-编辑距离算法详解（Levenshtein distance）

我会带着你远行 2022-01-19 03:21 306阅读 0赞

**总结一句话：编辑距离就是从一个字符串变到另外一个字符串所需要最小的步骤**

# 一：简介 #

在信息论、语言学和计算机科学中，Levenshtein distance是用于测量两个字符串之间差异的字符串度量。非正式的说就是两个单词之间的Levenshtein distance是将一个单词更改为另一个单词所需的单字符编辑（插入，删除或替换）的最小步骤。

它以苏联数学家弗拉基米尔·莱文斯坦（Vladimir Levenshtein）的名字命名，作者在1965年提出的这个算法。

Levenshtein distance也可以称为编辑距离，尽管该术语也可以表示更大的距离度量系列。

Levenshtein distance与成对字符串对齐密切相关。

> 这里面主要内容为我对[Levenshtein distance][]的英文翻译，也加了一些我的想法~

# 二：算法定义 #

## 1：定义 ##

在两个字符串a和b之间的Levenshtein distance由下面 定义：

其中

当ai = bj时等于0，其他情况下等于1，代表a的前i个字节到b的前j个字节的距离。

其中相对于a变化到b字符串来说：

*  :代表a删除一个字节去匹配b
 *  :代表a添加一个字节去匹配b
 *  :代表匹配或者不匹配，这取决于各个符号是否相同

## 2：a small case ##

我们计算一下kitten和sitting之间的编辑距离

*  **k**itten → **s**itten (替换 "k" -> "s")
 *  sitt**e**n → sitt**i**n (替换 "e" -> "i")
 *  sittin → sittin**g** (插入"g").

上面的变化过程所需要的步数就是最小的步数，所以他们之间的编辑距离就是"3"

## 3：算法的上下界限 ##

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 ：只允许对字符串进行交换

编辑距离通常定义为使用一组特定允许的编辑操作来计算的可参数化度量，并为每个操作分配成本（可能是无限的）

# 五：算法实现 #

## 1：递归实现 ##

这种算法实现比较简单，就是根据上述介绍的上下界限就可以得出逻辑了

//实现方法
    private static int distance(String a, int len_a, String b, int len_b) {
        //递归回归点
        if (len_a == 0)
            return len_b;
        if (len_b == 0)
            return len_a;
        
        int cos;
        if (a.charAt(len_a-1) == b.charAt(len_b-1))
            cos = 0;
        else
            cos = 1;
    
        int re1 = distance(a, len_a - 1, b, len_b) + 1;
        int re2 = distance(a, len_a, b, len_b - 1) + 1;
        int re3 = distance(a, len_a - 1, b, len_b - 1) + cos;
        //返回在a中删除一个字符、在b中删除一个字符、ab中均删除一个字符获得结果中取最小值
        return re1 < re2 ? (re1 < re3 ? re1 : re3) : (re2 < re3 ? re2 : re3);
    }
    //测试
    public static void main(String[] args) {
        String a = "kitten";
        String b = "sitting";
        int re = distnace(a, a.length(), b, b.length());
        System.out.println(re);
        //输出：3
    }
    复制代码

这种方式时间复杂度比较高，效率比较低，重复计算了好多字符串，下面采用动态规划算法实现。

## 2：动态规划实现 ##

> 算法原理部分就借用https://www.cnblogs.com/sumuncle/p/5632032.html 博主的部分文章吧=.=

算法基本原理：假设我们可以使用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\]中；

private static int distance(String a, String b) {
        int[][] dis = new int[a.length()+1][b.length()+1];
        for (int i = 1; i <= a.length(); i++)
            dis[i][0] = i;
        for (int j = 1; j <= b.length(); j++)
            dis[0][j] = j;
        int cas;
        for (int j = 1; j <= b.length(); j++) {
            for (int i = 1; i <= a.length(); i++) {
                if (a.charAt(i-1) == b.charAt(j-1))
                    cas = 0;
                else
                    cas = 1;
                int re = Math.min(dis[i - 1][j] + 1, dis[i][j - 1] + 1);
                dis[i][j] = Math.min(re, dis[i - 1][j - 1] + cas);
            }
        }
        return dis[a.length() - 1][b.length() - 1];
    }
    
    public static void main(String[] args) {
        String a = "kitten";
        String b = "sitting";
        int re = distance(a, b);
        System.out.println(re);
        //输出：3
    }
    复制代码

> 如果转载此博文，请附上本文链接，谢谢合作~ ：[juejin.im/user/5c3036…][juejin.im_user_5c3036]

> **如果感觉这篇文章对您有所帮助，请点击一下“喜欢”或者“关注”博主，您的喜欢和关注将是我前进的最大动力！**

转载于:https://juejin.im/post/5c4702ebe51d45517334af4d

[Levenshtein distance]: https://link.juejin.im?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLevenshtein_distance
[juejin.im_user_5c3036]: https://juejin.im/user/5c30362951882524c84ea9f6/posts