similarities_more.py

from enum import Enum


class Operation(Enum):
    """Operations"""

    DELETED = 1
    INSERTED = 2
    SUBSTITUTED = 3

    def __str__(self):
        return str(self.name.lower())


def distances(a, b):
    """Calculate edit distance from a to b"""
    # TODO
    length1 = len(a)
    length2 = len(b)

    # initializing the matrix
    matrix = [[[0 for l in range(2)] for m in range(length1 + 1)] for n in range(length2 + 1)]

    # initializing the [0, 0] element
    matrix[0][0] = (0, 0)

    # initializing the first row and columns
    for i in range(1, length2 + 1):
        matrix[i][0] = (i, Operation.INSERTED)
    for j in range(1, length1 + 1):
        matrix[0][j] = (j, Operation.DELETED)

   # populating the matrix with values
    for i in range(1, length1 + 1):
        for j in range(1, length2 + 1):
            up = left = diag = 0
            # edit distance via insertion
            up = matrix[i - 1][j][0] + 1
            # edit distance via deletion
            left = matrix[i][j - 1][0] + 1
            # edit distance from substitution
            if a[i - 1] == b[j - 1]:
                diag = matrix[i - 1][j - 1][0]
            else:
                diag = matrix[i - 1][j - 1][0] + 1

            # calculating the minimum edit distance
            final = min(up, left, diag)
            element = (final, )

            # checking for the type of operation
            if final == up:
                oper = (Operation.INSERTED, )
            elif final == left:
                oper = (Operation.DELETED, )
            else:
                oper = (Operation.SUBSTITUTED, )

            # creating a tuple for insertion
            ans = element + oper
            matrix[i][j] = ans

    return matrix