字符串相似度算法(编辑距离算法)

编辑距离算法

前言
原理
- 公式
- 例子
实现
后记

前言

比较两个字符串的相似度，通常我们会使用编辑距离算法来实现。
下面是常用字符串相似度计算的方法：
字符串相似度的几种度量方法

原理

最小编辑距离的原理是: 比较两个字符串，记录一个字符串通过移除，替换，添加操作转换到指定字符串的次数，来确定两个字符串直接的相似度。

公式

（操作次数）/ (, )  = 相似度

例子

字符串1: bsada
字符串2: asqa

我们想把字符串2 变成字符串1 那么步骤如下：
bsada -> asada -> asda -> asqa 这里要经过3步操作，所以相似度就是 3/5 = 0.6
当然你也可以这样操作
bsada -> asada -> asqda -> asqd -> asqa 如果这样子做的话要经过4步操作。

所以此算法的核心就是求最小的操作次数，其实可以用矩阵来表示：

		b	s	a	d	a
	0	1	2	3	4	5
a	1	1	2	2	3	4
s	2	2	1	2	3	4
q	3	3	2	2	3	4
a	4	4	3	2	3	3

通过表格分析我们能发现：最小距离的规则如下：

如果两字符相等则取左上角的数
如果两字符不相等则取上，左，左上角的最小数加一

实现

    /**
     * 字符串相似度比较
     * 这里为了使空间使用率较高，
     * 请把字符串较短的放到str1参数
     *
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 相似度
     */
    public static BigDecimal getLevenshteinDistance(String str1, String str2) {
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[] distance = new int[str1.length() + 1];
        int[] nextDistance = new int[distance.length];
        distance[0] = 0;
        //distance 初始化
        for (int i = 1; i < distance.length; i++) distance[i] = i;
        //这里不全量构造矩阵,节省空间
        for (int i = 0; i < char2.length; i++) {
            nextDistance[0] = i + 1;

            for (int j = 0; j < char1.length; j++) {
                int val;
                if(char2[i] == char1[j]) { //如果两个值相等,就取左上角元素
                    val = distance[j];
                } else { //两值不相等时，取左上角,上面,左面元素的最小值 + 1
                    int slash = distance[j] + 1;
                    int left = distance[j + 1] + 1;
                    val = Math.min(slash, left);
                    val = Math.min(val, nextDistance[j] + 1);
                }

                nextDistance[j + 1] = val;
            }

            System.arraycopy(nextDistance, 0, distance, 0, distance.length);
        }

        return BigDecimal.valueOf(1d).subtract(BigDecimal.valueOf((double) nextDistance[nextDistance.length - 1]/Math.max(str1.length(), str2.length())));
    }

后记

编辑距离算法确实在一定程度上可以检测出两个字符串的相似度，但是对于不关心字符顺序的匹配可能并不合适，比如abcd -> dcba 经过此算法计算的结果是0

秒客网

字符串相似度算法(编辑距离算法)

编辑距离算法

前言

原理

公式

例子

实现

后记

相关文章