Using the below Python code, please implement the algorithm for computing edit d
ID: 3753706 • Letter: U
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 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)
Explanation / Answer
In the below algorithm I have added the line to complete the edit distance algorithm where a blue line is visible.
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):
mTable[i,0]=i (#Added line)
for j in range(0, n):
mTable[0,j]=j (#Added line)
for i in range(1, m):
for j in range(1, n):
cost=0 if s1[i-1] = s2[j-1] else 1
mTable [i,j] = min(mTable [ i, j-1] +1, mTable[i-1,j] +1, mTable[i-1,j-1] +cost)
# 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 = mtable[i-1,j-1] # Added 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 =mTable[i,j ] # Added 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])
Given the two strings are
1.”kitten”
2.”sitting”
The edit distance between the two strings is 3
Example 2:the two strings are
1.”GAMBOL”
2.”GAMBO”
The edit distance between the two strings is 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.