Question
Using the below Python code, please implement the algorithm for computing edit distance. To do this, please complete the lines of code that are commented
Using the below Python code, please implement the algorithm for computing edit distance. To do this, please complete the lines of code that are commented with # Need to add one line here or # Need to complete this line. Then please show the output of the two examples at the bottom of the code. Thanks!
def edit_distance(s1, s2): m = len(s1) + 1 n = len(s2) + 1
# Initialize the matrix mTable = {} for i in range(0, m): for j in range(0, n): mTable[i, j] = 0
for i in range(0, m): # Need to add one line here
for j in range(0, n): # Need to add one line here
for i in range(1, m): for j in range(1, n): # Need to add one line here
# Need to add one line here
# Print the edit distance matrix print("Edit Distance Matrix ") print(" ", end='') for j in range(n-1): print("| " + s2[j] + " ", end='') print(" ") for i in range(0, m): if i == 0: print(" ", end='') if i > 0: print(" " + s1[i - 1] + " ", end='') for j in range(0, n): print("| " + str(mTable[i, j]) + " ", end='') print(" ")
return mTable, mTable[m - 1, n - 1]
def get_edits(s1, s2, mTable, nEditDist): m = len(s1) + 1 n = len(s2) + 1
i_old = m - 1 j_old = n - 1 i_new = m - 1 j_new = n - 1 sOperation = "" nIndexOfOperation = nEditDist - 1 sOperationList = {} for i in range(0, nEditDist - 1): sOperationList[i] = "" while 1: nLeft = mTable[i_old, j_old-1] nUp = mTable[i_old-1, j_old] nUpLeft = mTable[i_old-1, j_old-1] if nUpLeft <= nLeft and nUpLeft <= nUp: i_new = i_old - 1 j_new = j_old - 1 if mTable[i_old, j_old] > nUpLeft: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 elif nLeft <= nUpLeft and nLeft <= nUp: i_new = i_old j_new = j_old - 1 if mTable[i_old, j_old] > nLeft: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 elif nUp <= nUpLeft and nUp <= nLeft: i_new = i_old - 1 j_new = j_old if mTable[i_old, j_old] > nUp: sOperation = # Need to complete this line sOperationList[nIndexOfOperation] = sOperation nIndexOfOperation -= 1 i_old = i_new j_old = j_new if i_old == 0 and j_old == 0: break
print("the sequence of the edits:") for i in range(0, nEditDist): print("Step " + str(i + 1) + " : " + sOperationList[i])
if __name__ == "__main__": # Example 1 sString1 = "kitten" sString2 = "sitting" # Example 2 # sString1 = "GAMBOL" # sString2 = "GUMBO" mTable, nEditDist = edit_distance(sString1, sString2) print("Edit distance is " + str(nEditDist)) get_edits(sString1, sString2, mTable, nEditDist)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started