java - 编辑比较两个字符串之间的单词之间的距离

Question

我从互联网上看到了很多资源，但找不到确切的帮助。我试图找出两个字符串之间的编辑距离示例: String a = "在段落之间放回车gioo"; String b = "在线路电话 gio 之间放置 hello"; 这里我总是将字符串 a 与另一个字符串进行比较，所以这里的编辑距离应该是 4。 我已经执行了一些代码，将我与字符串中的每个字符进行比较。

                           int len1 = row10.length();
                            int len2 = row01.length();
                            int[][] dp = new int[len1 + 1][len2 + 1];

                            for (int i = 0; i <= len1; i++) {
                                dp[i][0] = i;
                            }

                            for (int j = 0; j <= len2; j++) {
                                dp[0][j] = j;
                            }

                            for (int i = 0; i < len1; i++) {
                                char c1 = row10.charAt(i);
                                for (int j = 0; j < len2; j++) {
                                    char c2 = row01.charAt(j);
                                    if (c1 == c2) {
                                        dp[i + 1][j + 1] = dp[i][j];
                                    } else {
                                        int replace = dp[i][j] + 1;
                                        int insert = dp[i][j + 1] + 1;
                                        int delete = dp[i + 1][j] + 1;
                                        int min = replace > insert ? insert : replace;
                                        min = delete > min ? min : delete;
                                        dp[i + 1][j + 1] = min;
                                    }
                                }
                            }
                            System.out.println(dp[len1][len2]);

Answer 1

制作了一个示例函数。它并没有真正考虑到极端情况，但它确实有效。另外，请务必考虑单词的大小写敏感性。

package test;

public class CalcWordDiff {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String a = "My name is ABC.";
        String b = "My name xyz.";
        System.out.println("Edit distance will be : "+calcDistanceBetweenWords(a,b));
    }

    public static int calcDistanceBetweenWords(String first, String second)
    {
        int res = 0;
        String[] words_string_first = first.trim().split(" "); // By trim, I removed the Whitespaces if they exist
        String[] words_string_second = second.trim().split(" ");
        //Check the length of both the arrays
        System.out.println("Size of arrays first is : "+words_string_first.length);
        System.out.println("Size of arrays second is : "+words_string_second.length);
        int lowerWordSentSize = 0;
        if(words_string_first.length<=words_string_second.length)
        {
            lowerWordSentSize = words_string_first.length;
        }
        else
        {
            lowerWordSentSize = words_string_second.length;
        }
        //Now iterate through the array of lower size
        for(int i = 0; i< lowerWordSentSize; i++)
        {
            if(words_string_first[i].equals(words_string_second[i]))
            {
                //Do nothing, it means both the words are same
            }
            else
            {
                System.out.println("Words mismatched at "+(i+1)+" th Position.");
                res = i; 
            }
        }
        return res;
    }

}