Please implement the algorithm for computing edit distance. A template python fi
ID: 3751883 • Letter: P
Question
Please implement the algorithm for computing edit distance.
A template python file “editdistance_incomplete.py” is provided. You need to fill 7 lines, which are indicated by the comments “# Need to add one line here” or “# Need to complete this line”.
You need to submit the complete python file into iCollege.
You need to copy and paste the outputs of your algorithm in the console/terminal for the following two examples.
Example 1:
sString1 = "kitten"
sString2 = "sitting"
Output in your algorithm:
Example 2:
sString1 = "GAMBOL"
sString2 = "GUMBO"
Output in your algorithm:
Explain what you observed and whether the output results make sense or not.
editdistance_incomplete.py:
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)
Explanation / Answer
The algorithm is as follows:
def edit_distance(s1,s2);
m = len(s1)+1
n = len(s2)+1
mTable = {}
for i in range(0,m):
for j in range(0,n):
mTable[i,j]=0
for i in range(0,m):
i++
for j in range(0,n):
j++
for i in range(1,m):
for j in range(1,n):
i++
j++
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])