字符串之间相似度的计算：莱文斯坦算法

水深无声 2022-04-17 06:28 355阅读 0赞

毕业后的第一份工作：MDM主数据的开发。服务的对象是某国企巨头，员工就有几万人。该公司呢，产品有很多，客户也特别多。每天的增量巨大，而负责录入的工作人员也有很多，由于每个人语言表达习惯不同，文化程度不同，工作态度不同等等，所以申请出来的数据也是五花八门。前期的MDM系统功能不够完善，为防止申请的信息重复，对于客户和产品信息的唯一性校验仅仅是对名称进行校验。在学校做过一些课程设计，对名称的校验一般都是直接匹配，等于就不能创建，或者就稍微弄一下模糊查询，所能校验的仅仅是包含或者被包含的数据。但是在这个项目上就行不通了，比如说某人申请了一个客户命名为“”北京市西城区某某科技公司“，然后有个态度比较散漫的工作人员以为这条数据没有创建就又申请了一次“北京西城某某科技有限公司”。这两条数据其实是一家公司，但如果有之前的这种模糊匹配就会使得这两条数据都能创建进去。这样麻烦就大了，你可能觉得，这种数据名称填写应该制定规范，申请人应该严格执行。但是我去的那个国企，额！如果你想被骂就去和他们提要求。为了防止数据重复的情况，所以在申请时对名称进行一次校验，而校验规则就可以使用“莱文斯坦算法”，也就是“编辑距离算法”（扯了半天总算扯回来了，抱歉）。

**莱文斯坦算法（编辑距离算法）**的核心思想其实就是计算从一个字符串编辑转换为另一条字符串所需要的编辑步骤。编辑包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

在数学上，两个字符串**a**,**b**的莱文斯坦距离记作![08f790529822720e481f259f72cb0a46f31fab86.jpg][] 。这里![9f510fb30f2442a716bcd8c3d843ad4bd1130221.jpg][]

这里，![aec379310a55b31908f5b8134aa98226cffc1743.jpg][] 和![71cf3bc79f3df8dc7bbeb5f7c411728b461028d0.jpg][] 分别表示字符串**a**和**b**的长度，![7e3e6709c93d70cf9d008f6bf1dcd100bba12bd9.jpg][] 是当![d62a6059252dd42a79caccc00a3b5bb5c8eab89e.jpg][] 时值为1，否则值为0的示性函数。这样，![37d12f2eb9389b50ce772f398c35e5dde6116ed5.jpg][] 是![9358d109b3de9c8272c437e46581800a19d8433c.jpg][] 的前![a8773912b31bb051fe867d433f7adab44aede03f.jpg][] 个字符和![c2cec3fdfc0392451f0e2f648e94a4c27d1e2526.jpg][] 的前![d0c8a786c9177f3edfaa326679cf3bc79f3d563b.jpg][] 个字符之间的距离。

珍爱生命，远离数学。所以还是简单说一下莱文斯坦算法吧！用矩阵来理解上述公式是最简单的。

计算abcd和abdc的编辑距离：设置初始值（由if min(i,j)=0得初始值为max(i,j)）

然后一行一行计算出每个单元格的值：其实主要是计算该单元格的上方单元格的值+1，左边单元格的值+1，左上方的单元格+1或者+0（如果对应位置上的值相等则+0，不等则+1）。

每个单元格的值其实就是表示该行的前i个字符组成的字符串编辑成该列前j个字符组成的字符串需要的步骤：即编辑距离。（不含开始的空单元格，加0是为了便于初始值的计算）

如上表的第五行第五列：由abc到abd显然是1。

现在我们谈一谈代码实现：刚在再填写矩阵的值时我们是一行一行填写，相当于固定了列编号，行编号递增，这是不是和我们所用的for循环很相似呢？因为有两组数据，我们可以将两组数据放入两个字符数组s,t，然后用嵌套循环实现：

设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建一个数组 d\[0..m, 0..n\]用于保存编辑距离  
将第0行初始化为 0..n，第0列初始化为0..m。   
依次检查 s 的每个字母(i=1..n)。   
依次检查 t 的每个字母(j=1..m)。   
如果 s\[i\]=t\[j\]，则 cost=0；如果 s\[i\]!=t\[j\]，则 cost=1。将 d\[i,j\] 设置为以下三个值中的最小值：   
紧邻当前格上方的格的值加一，即 d\[i-1,j\]+1   
紧邻当前格左方的格的值加一，即 d\[i,j-1\]+1   
当前格左上方的格的值加cost，即 d\[i-1,j-1\]+cost   
重复3-6步直到循环结束。d\[n,m\]即为长度为m和长度为n的字符串编辑距离。

package com.camelot.afly.java;
    
    public class LevenshteinDistance {
    
    	public static void main(String[] args) {
    	       String a= "北京市西城区某某科技公司";
    	        String b = "北京西城某某科技有限公司";
    	        System.out.println("相似度："+getSimilarityRatio(a,b));
    		
    
    	}
    
        private static int compare(String str, String target) {
            int d[][];              // 矩阵
            int n = str.length();
            int m = target.length();
            int i;                  
            int j;                 
            char ch1;               
            char ch2;               
            int temp;              
            if (n == 0) {
                return m;
            }
            if (m == 0) {
                return n;
            }
            d = new int[n + 1][m + 1];
            // 初始化第一列
            for (i = 0; i <= n; i++) {
                d[i][0] = i;
            }
            // 初始化第一行
            for (j = 0; j <= m; j++) {
                d[0][j] = j;
            }
            for (i = 1; i <= n; i++) {
                // 遍历str
                ch1 = str.charAt(i - 1);
                // 去匹配target
                for (j = 1; j <= m; j++) {
                    ch2 = target.charAt(j - 1);
                    if (ch1 == ch2 || ch1 == ch2 + 32 || ch1 + 32 == ch2) {
                        temp = 0;
                    } else {
                        temp = 1;
                    }
                    // 左边+1,上边+1, 左上角+temp取最小
                    d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
                }
            }
            return d[n][m];
        }
     
     
        /**
         * 获取最小的值
         */
        private static int min(int one, int two, int three) {
            return (one = one < two ? one : two) < three ? one : three;
        }
     
        /**
         * 获取两字符串的相似度：1-（编辑距离）/字符串最大长度
         */
        public static float getSimilarityRatio(String str, String target) {
            int max = Math.max(str.length(), target.length());
            return 1 - (float) compare(str, target) / max;
        }
    
    
    }

这里使用的方法是数组的嵌套遍历，有点low,使用递归要简单的多，在这里也就不附上代码了。大家可以试试看！

文章开头提到的这两个公司就可以算出相似度：

![20181114114021241.png][]

然后我们就可以设置一个阀值（如0.6），将所有大于该阀值的数据展示出来，以供用户判断是否该数据已经被申请了。

到此！莱文斯坦算法也介绍完了。感谢您的耐心！

[08f790529822720e481f259f72cb0a46f31fab86.jpg]: http://e.hiphotos.baidu.com/baike/pic/item/08f790529822720e481f259f72cb0a46f31fab86.jpg
[9f510fb30f2442a716bcd8c3d843ad4bd1130221.jpg]: /images/20220417/c96c895437ea48efa25d62926e37e7bd.png
[aec379310a55b31908f5b8134aa98226cffc1743.jpg]: http://d.hiphotos.baidu.com/baike/pic/item/aec379310a55b31908f5b8134aa98226cffc1743.jpg
[71cf3bc79f3df8dc7bbeb5f7c411728b461028d0.jpg]: http://c.hiphotos.baidu.com/baike/pic/item/71cf3bc79f3df8dc7bbeb5f7c411728b461028d0.jpg
[7e3e6709c93d70cf9d008f6bf1dcd100bba12bd9.jpg]: http://g.hiphotos.baidu.com/baike/pic/item/7e3e6709c93d70cf9d008f6bf1dcd100bba12bd9.jpg
[d62a6059252dd42a79caccc00a3b5bb5c8eab89e.jpg]: http://b.hiphotos.baidu.com/baike/pic/item/d62a6059252dd42a79caccc00a3b5bb5c8eab89e.jpg
[37d12f2eb9389b50ce772f398c35e5dde6116ed5.jpg]: http://b.hiphotos.baidu.com/baike/pic/item/37d12f2eb9389b50ce772f398c35e5dde6116ed5.jpg
[9358d109b3de9c8272c437e46581800a19d8433c.jpg]: http://d.hiphotos.baidu.com/baike/pic/item/9358d109b3de9c8272c437e46581800a19d8433c.jpg
[a8773912b31bb051fe867d433f7adab44aede03f.jpg]: http://g.hiphotos.baidu.com/baike/pic/item/a8773912b31bb051fe867d433f7adab44aede03f.jpg
[c2cec3fdfc0392451f0e2f648e94a4c27d1e2526.jpg]: http://b.hiphotos.baidu.com/baike/pic/item/c2cec3fdfc0392451f0e2f648e94a4c27d1e2526.jpg
[d0c8a786c9177f3edfaa326679cf3bc79f3d563b.jpg]: /images/20220417/df1175443c4348af8f1eecf7cabc23cc.png
[20181114114021241.png]: /images/20220417/d1f5d1911fd94d0a8a4b4c045aa81103.png