Levenhstein algorithm implementation

levenshtein-algorithm.py

#!/usr/bin/env python
#
#   Python Script
#
#   Copyleft © Manoel Vilela
#
#

# complexity time: O(n x m)

def debug(data):
    print('[debug]')
    for index, dataline in enumerate(data):
        print('{}:{}'.format(index, dataline))


def edit_distance(s1, s2):
    """
        Calculate the minimum edit distance of two strings using
        the Levenshtein Algorithm.
    """

    # the lenghts of strings
    n, m = len(s1), len(s2)

    # create a matrix (n + 1) x (m + 1) for distances
    d = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # initial values
    for i in range(1, n + 1):
        d[i][0] = i
    for j in range(1, m + 1):
        d[0][j] = j

    # iteration: delete, insert and substitution
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            d[i][j] = min(d[i - 1][j - 1] + int(s1[i - 1] != s2[j - 1]) * 2,
                          d[i - 1][j] + 1,
                          d[i][j - 1] + 1)

    # minimum distance of s1 and s2
    return d[n][m]


def tests(keywords):
    """
        List of keywords like:
        >>> keywords = [('abacate', 'banana'), ('crazy', 'insane')]
    """
    print("Minimum edit distance testes session")
    for a, b in keywords:
        print("{} x {} = {}".format(a, b, edit_distance(a, b)))


def main():
    test_keys = [
        ('abacate', 'banana'),
        ('azul', 'chocolate'),
        ('cast', 'cats'),
        ('fast', 'cats')
    ]

    tests(test_keys)


if __name__ == '__main__':
    main()