大字符串编辑距离解决方案

我正试图解决edit distance问题。我一直在使用的代码如下。大字符串编辑距离解决方案

public static int minDistance(String word1, String word2) { 
    int len1 = word1.length(); 
    int len2 = word2.length(); 

    // len1+1, len2+1, because finally return dp[len1][len2] 
    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; 
    } 

    //iterate though, and check last char 
    for (int i = 0; i < len1; i++) { 
     char c1 = word1.charAt(i); 
     for (int j = 0; j < len2; j++) { 
      char c2 = word2.charAt(j); 

      //if last two chars equal 
      if (c1 == c2) { 
       //update dp value for +1 length 
       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; 
      } 
     } 
    } 

    return dp[len1][len2]; 
}

这是一种DP方法。这个问题，因为它使用二维数组我们不能解决这个问题，使用上面的方法大字符串。例如：字符串长度> 100000.

那么无论如何修改这个算法来克服这个困难？

注意：上述代码将准确地解决小字符串的编辑距离问题。（其长度低于1000或接近）

正如您在代码中看到的，它使用Java 2D数组“dp [] []”。所以我们不能为大的行和列初始化二维数组。

例如：如果我需要检查2个字符串，其长度超过10

int[][] dp = new int[len1 + 1][len2 + 1];

以上将是

int[][] dp = new int[100000][100000];

所以这会给出一个计算器错误。

所以上面的程序只适合小长度的字符串。我问的是，有没有什么办法来解决这个问题的大型字符串（长度> 100000）在Java中有效。

来源

2014-10-06 prime

为什么输入了这么长时间？也许更多地了解情况会让我们提出更好的选择。 – 2014-10-06 10:22:26

这是我们想要比较长度超过100000的两个字符串的情况。在这种情况下，我们不能创建Java二维数组。 – prime 2014-10-06 10:23:40

@jurgemaister：我增加了一些细节。这不是一个作业:) – prime 2014-10-06 10:29:40

首先，有一个在分配Java中的100K X 100K int数组没有问题，你就必须做到这一点在堆中，没有堆栈（和周围的内存80GB :)一台机器上）

其次，作为一个（很直接）提示：

注意，在你的循环，你永远只能使用2行一次 - 行i和行i+1。实际上，您可以从第i行计算行i+1。一旦你得到i+1你不需要存储行i了。

这个巧妙的技巧使您可以同时只存储2行，从而将空间复杂度从n^2降低到n。既然你说这是而不是作业（即使你是你的个人档案的CS本科生......），我相信你自己想出了这些代码。

_{试想想它，我记得有，当我在我的CS程度做一类这个确切的问题...}

来源

2014-10-06 10:39:14 Ordous

我明白了你的想法。感谢你的回答。顺便说一句，我正在练习DP进行编程竞赛。我几乎在所有参考文献中发现了这个问题。但是，当我尝试比较大字符串失败。由于上述原因。（我们无法在正常竞争中分配超过256MB的内存），所以我在这里发布这个问题来获得提示。再次感谢。我会检查这个。 – prime 2014-10-06 10:57:18

@prime然后忽略不那么微妙的评论。这应该会将内存需求降低到远低于最大值。 – Ordous 2014-10-06 11:09:31

大字符串编辑距离解决方案

回答

相关问题