计算2个字符串相似度（动态规划）-Java用最小编辑距离算法实现

素颜马尾好姑娘i 2023-10-07 20:54 15阅读 0赞

参考：  
[基于编辑距离算法的文本相似度3种解决方案][3]

#### 需求 ####

给出2个字符串str1和str2，计算将str1转换为str2的最少操作次数。  
操作方法只有三种：插入一个单字符串、删除一个单字符串、替换一个单字符串。

#### 操作步骤&核心逻辑 ####

其核心算法：

*  设计一个二维表格，表格列数为字符串1的长度加1，行数为字符串2的长度加1。
 *  表格的第1行按照列，自左往右，依序填列0,1,2，…字符串1的长度n;
 *  表格的1列按照行，自上往下，依序填列0,1,2，…字符串2的长度m;
 *  然后自第2行，第2列开始，自左往右，填充数据，

该数据的规则是：**如果两个字符串对应位置的字符相同，则取左上角单元格的值；如果不同，则取该单元格左方、左上方、上方的三个但单元格的值的最小值+1。重复上述操作，直到填满最后一个单元格，最后右下角单元格中数字就是最小编辑距离。**

![在这里插入图片描述][91d15fc1409544e1bf9e62f9db487825.png]

例1：将字符串“大美河山“转换为”大号中山河”需要的最少操作次数是3。
    第一步：替换”大美河山”中的字符串“美”为“号”-->"大号河山"
    第二步：替换"大号河山"中的字符串“河”为“中”-->"大号中山"
    第三步：在字符串“山”后新增字符串“河”-->"大号中山河"
    
    例2：将字符串“大美河山“转换为”大号中河山”需要的最少操作次数是2。
    第一步：替换”大美河山”中的字符串“美”为“号”-->"大号河山"
    第二步：在字符串“号”后新增字符串“中”-->"大号中河山"

#### java代码实现获取最小编辑距离 ####

参考：[Java 算法-编辑距离(动态规划)][Java _-]

/**
         * 获取将str1变为str2的最小编辑距离
         *
         * @param str1 字符串1
         * @param str2 字符串2
         * @return 最小编辑距离
         */
        public static int minDistance(String str1, String str2) {
        
    
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    
            for (int i = 0; i < str1.length() + 1; i++) {
        
                // 从i个字符变成0个字符，需要i步（删除）
                dp[i][0] = i;
            }
            for (int i = 0; i < str2.length() + 1; i++) {
        
                // 当从0个字符变成i个字符，需要i步(增加)
                dp[0][i] = i;
            }
    
            for (int i = 1; i < str1.length() + 1; i++) {
        
                for (int j = 1; j < str2.length() + 1; j++) {
        
                    //当相同的时，dp[i][j] = dp[i - 1][j - 1]
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
        
                        //当不同的时候，我们需要求三种操作的最小值
                        //其中dp[i - 1][j - 1]表示的是替换，dp[i - 1][j]表示删除字符，dp[i][j - 1]表示的是增加字符
                        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                    }
                }
            }
            return dp[str1.length()][str2.length()];
        }

#### 获取2个字符串相似度 ####

/**
         * 获取相似度评分
         *
         * @param str1        字符串1
         * @param str2        字符串2
         * @param minDistance 最小编辑距离
         * @return 相似度评分
         */
        public static double getScore(String str1, String str2, int minDistance) {
        
            int max = Math.max(str1.length(), str2.length());
            return (double)(max - minDistance)/max;
        }

[3]: https://zhuanlan.zhihu.com/p/256006420
[91d15fc1409544e1bf9e62f9db487825.png]: https://img-blog.csdnimg.cn/91d15fc1409544e1bf9e62f9db487825.png
[Java _-]: https://www.jianshu.com/p/6de1c31e6ca6