Algorithms For Dummies

 Challenging Difficult Problems

You can render the counting algorithm as a recursion or an iteration. However, it 

works much faster using a bottom-up dynamic programming solution, as described 

in the 1974 paper “The String-to-string Correction Problem,” by Robert A. Wagner 

and  Michael  J.  Fischer  (

http://www.inrg.csie.ntu.edu.tw/algorithm2014/

homework/Wagner-74.pdf

). The time complexity of this solution is 

O(mn)

, where n 

and m are the lengths in letter of the two words being compared. The following 

code computes the number of changes required to turn the word Saturday into 

Sunday by using dynamic programming with a matrix (see Figure 16-2) to store 

previous results (the bottom-up approach). (You can find this code in the 

A4D; 16; 

Levenshtein.ipynb

 file on the Dummies site as part of the downloadable code; see 

the Introduction for details.)

import numpy as np

import pandas as pd

s1 = 'Saturday'

s2 = 'Sunday'

m = len(s1)

n = len(s2)

D = np.zeros((m

+1,n+1))

D[0,:] =  list(range(n

+1))

D[:,0] = list(range(m

+1))

for j in range(1, n

+1):

    for i in range(1, m

+1):

        if s1[i-1] == s2[j-1]:

            D[i, j] = D[i-1, j-1]

        else:

                D[i, j] = np.min([

                D[i-1, j]   

+ 1,  # a deletion

                D[i, j-1]   

+ 1,  # an insertion

                D[i-1, j-1] 

+ 1   # a substitution

                ])

print ('Levenshtein distance is %i' % D[-1,-1])

Levenshtein distance is 3

You can plot or print the result using the following command:

pd.DataFrame(D,index=list(' '

+s1), columns=list(' '+s2))

The algorithm builds the matrix, placing the best solution in the last cell. After 

building the matrix using the letters of the first string as rows and the letters of 

the second one as columns, it proceeds by columns, computing the differences 

---

CHAPTER 16