Speeding-Up the Dynamic Programming Procedure for the Edit Distance of Two Strings.
Giuseppe Lancia, Marcello Dalpasso · 2019
We describe a way to compute the edit distance of two strings without having to fill the whole dynamic programming (DP) matrix, through a sequence of increasing guesses on the edit distance. If the strings share a certain degree of similarity, the edit distance can be quite smaller than the value of non-optimal solutions, and a large fraction (up to 80–90%) of the DP matrix cells do not need to be computed. Including the method’s overhead, this translates into a speedup factor from \(3\times \) up to \(30\times \) in the time needed to find the optimal solution for strings of length about 20,000.