Similarities (More) sometimes fails but works in most cases

Question

For some reason, for some combinations of strings, I receive an IndexError on the compilation of Operations in application.py. However, for most cases, the table renders properly, and in every case, running ./score on the same strings runs perfectly.

I have tried strings of the same length, and these almost always work. I have also tried strings of differing lengths. It seems that in most cases this works, however, I tried the combination of converting grunt into runt, or rainy and grain, and vice-versa. These combinations and others like them, where there is significant overlap causes the following error:

File "/home/ubuntu/workspace/pset6/similarities/application.py", line 68, in score
   s = (prev[:i], s2[i], prev[i:])
IndexError: string index out of range

I am stumped here.

helpers.py

def distances(a, b):
"""Calculate edit distance from a to b"""

x = len(a) + 1
y = len(b) + 1

# helper to return the value of the first element in a tuple
def cost(cell):
    return cell[0]

# Set up 2D list
matrix = []
for m in range(x):
    column = []
    for n in range(y):
        column.append((0,))
    matrix.append(column)

for i in range(x):
    for j in range(y):
         # add values for base cases
        if i == 0 and j == 0:
            matrix[0][0] = 0, None
        elif i == 0 and j != 0:
            matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.DELETED
        elif j == 0 and i != 0:
            matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.INSERTED
        else:
            # fill in other entries
            possibilities = [
                (1 + cost(matrix[i - 1][j]), Operation.DELETED),
                (1 + cost(matrix[i][j - 1]), Operation.INSERTED),
                # account for difference in length of array and length of string
                (cost(matrix[i - 1][j - 1]) if a[i-1] == b[j-1] else (1 + cost(matrix[i - 1][j - 1])), Operation.SUBSTITUTED) ]

            matrix[i][j] = min(possibilities, key=cost)
return matrix

I would appreciate any help in pointing me in the right direction. Am I calculating something improperly??

Answer 1

You seem to confuse Operation.DELETED and Operation.INSERTED.

Operation.DELETED is used when you advance in the source string a (so you change i) without advancing in target string b, i.e. the source character is deleted.

Operation.INSERTED is used when you don't advance in a, but only in b.

Operation.SUBSTITUTED is used when you advance in both at the same time.

Calculations look correct otherwise, but haven't tested.

Answer 2

Based off @Blauelf's earlier response, the following change was necessary. When I was setting up the state of the matrix for converting each string to an empty string, I had inverted the operations.

• matrix[0][j - 1] represents the cost of insertion along string2 since each inner array is of length string2 + 1
• matrix[i - 1][0] represents the cost of deletion along string1 since the length of the outer array is of length string1 + 1

original

elif i == 0 and j != 0:
    matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.DELETED
elif j == 0 and i != 0:
    matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.INSERTED

correct

elif i == 0 and j != 0:
    matrix[0][j] = cost(matrix[0][j - 1]) + 1, Operation.INSERTED
elif j == 0 and i != 0:
    matrix[i][0] = cost(matrix[i - 1][0]) + 1, Operation.DELETED