Редактировать решение для больших строк

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. Проблема с тех пор, как он использует 2D-массив , мы не можем решить эту проблему, используя метод выше для больших строк. Пример: длина строки> 100000.

Итак, есть ли способ изменить этот алгоритм, чтобы преодолеть эту трудность?

ПРИМЕЧАНИЕ: Приведенный выше код точно решит проблему «Редактировать расстояние» для небольших строк. (который имеет длину ниже 1000 или около)

Как вы можете видеть в коде, он использует Java 2D-массив «dp [] []». Поэтому мы не можем инициализировать 2D-массив для больших строк и столбцов.

Ex: Если мне нужно проверить 2 строки, длины которых более 100000

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

выше будет

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

Так это даст ошибку StackOverflow.

Таким образом, вышеуказанная программа подходит только для небольших строк. Что я прошу, есть ли способ решить эту проблему для больших строк (длина> 100000) эффективно в java.

Answer 1

Прежде всего, нет никаких проблем в выделении целочисленного массива 100k х 100k в Java, вы просто должны это делать в куче, а не стек (и на машину с около 80GB памяти :))

во-вторых, как (очень прямой) намек:

Обратите внимание, что в цикле, вы только когда-либо с помощью 2 строки в то время - ряд i и грести i+1. Фактически, вы вычисляете строку i+1 из строки i. Как только вы получите i+1 вам не нужно хранить строку i больше.

Этот аккуратный трюк позволяет хранить только 2 строки одновременно, уменьшая сложность пространства от n^2 до n. Поскольку вы заявили, что это не домашнее задание (даже если вы являетесь подчиненным CS своим профилем ...), я верю, что вы сами придумаете код.

_{Давай думать об этом я помню, чтобы это точно проблема, когда я делаю класс в моей степени CS ...}