大字符串編輯距離解決方案

Question

我正試圖解決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中有效。

Answer 1

首先，有一個在分配Java中的100K X 100K int數組沒有問題，你就必須做到這一點在堆中，沒有堆棧（和周圍的內存80GB :)一臺機器上）

其次，作爲一個（很直接）提示：

注意，在你的循環，你永遠只能使用2行一次 - 行i和行i+1。實際上，您可以從第i行計算行i+1。一旦你得到i+1你不需要存儲行i了。

這個巧妙的技巧使您可以同時只存儲2行，從而將空間複雜度從n^2降低到n。既然你說這是而不是作業（即使你是你的個人檔案的CS本科生......），我相信你自己想出了這些代碼。

_{試想想它，我記得有，當我在我的CS程度做一類這個確切的問題...}