Levenshtein Distance（编辑距离）算法与使用场景

public enum LevenshteinDistance {
    // 单例
    X;
    /**
     * 计算Levenshtein Distance
     */
    public int ld(String source, String target) {
        Optional.ofNullable(source).orElseThrow(() -> new IllegalArgumentException("source"));
        Optional.ofNullable(target).orElseThrow(() -> new IllegalArgumentException("target"));
        int sl = source.length();
        int tl = target.length();
        // 定义矩阵,行列都要加1
        int[][] matrix = new int[sl + 1][tl + 1];
        // 首行首列赋值
        for (int k = 0; k <= sl; k++) {
            matrix[k][0] = k;
        }
        for (int k = 0; k <= tl; k++) {
            matrix[0][k] = k;
        }
        // 定义临时的编辑消耗
        int cost;
        for (int i = 1; i <= sl; i++) {
            for (int j = 1; j <= tl; j++) {
                if (source.charAt(i - 1) == target.charAt(j - 1)) {
                    cost = 0;
                } else {
                    cost = 1;
                }
                matrix[i][j] = min(
                        // 左上
                        matrix[i - 1][j - 1] + cost,
                        // 右上
                        matrix[i][j - 1] + 1,
                        // 左边
                        matrix[i - 1][j] + 1
                );
            }
        }
        return matrix[sl][tl];
    }
    private int min(int x, int y, int z) {
        return Math.min(x, Math.min(y, z));
    }
    /**
     * 计算匹配度match rate
     */
    public BigDecimal mr(String source, String target) {
        int ld = ld(source, target);
        // 1 - ld / max(len1,len2)
        return BigDecimal.ONE.subtract(BigDecimal.valueOf(ld)
                .divide(BigDecimal.valueOf(Math.max(source.length(), target.length())), 2, BigDecimal.ROUND_HALF_UP));
    }
}
复制代码

public static void main(String[] args) throws Exception {
    String s = "doge";
    String t = "dog";
    System.out.println("Levenshtein Distance:" +LevenshteinDistance.X.ld(s, t));
    System.out.println("Match Rate:" +LevenshteinDistance.X.mr(s, t));
}
// 输出
Levenshtein Distance:1
Match Rate:0.75
复制代码

public static void main(String[] args) throws Exception {
    String sourceName = "张*狗";
    String sourcePhone = "123****8910";
    String sourceIdentityNo = "123456****8765****";
    String targetName = "张大狗";
    String targetPhone = "12345678910";
    String targetIdentityNo = "123456789987654321";
    boolean match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 &&
            LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 &&
            LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8;
    System.out.println("是否匹配:" + match);
    targetName = "张大doge";
    match = LevenshteinDistance.X.ld(sourceName, targetName) == 1 &&
            LevenshteinDistance.X.ld(sourcePhone, targetPhone) == 4 &&
            LevenshteinDistance.X.ld(sourceIdentityNo, targetIdentityNo) == 8;
    System.out.println("是否匹配:" + match);
}
// 输出结果
是否匹配:true
是否匹配:false
复制代码

public static void main(String[] args) throws Exception {
    String target = "throwab";
    // 模拟一个单词库
    List<String> words = Lists.newArrayList();
    words.add("throwable");
    words.add("their");
    words.add("the");
    Map<String, BigDecimal> result = Maps.newHashMap();
    words.forEach(x -> result.put(x, LevenshteinDistance.X.mr(x, target)));
    System.out.println("输入值为:" + target);
    result.forEach((k, v) -> System.out.println(String.format("候选值:%s,匹配度:%s", k, v)));
}
// 输出结果
输入值为:throwab
候选值:the,匹配度:0.29
候选值:throwable,匹配度:0.78
候选值:their,匹配度:0.29
复制代码

System.out.println(LevenshteinDistance.X.mr("我是一只小小小小鸟，想要飞呀飞却飞也飞不高", "我是一条小小小小狗，想要睡呀睡却睡也睡不够"));
// 输出如下
0.67
复制代码