Damerau–Levenshtein distance

lev.py

# -*- coding: utf-8 -*-

def edit_distance(first_word, second_word):
    first_word_len = len(first_word)
    second_word_len = len(second_word)
    matrix = [[0 for j in range(second_word_len+1)] \
                    for i in range(first_word_len+1)]
    for i in range(1, first_word_len+1):
        for j in range(1, second_word_len+1):
            cost = first_word[i-1] != second_word[j-1] and 1 or 0
            matrix[i][j] = min(matrix[i-1][j] + 1,
                               matrix[i][j-1] + 1,
                               matrix[i-1][j-1] + cost)
            if i>1 and j>1 and (first_word[i-1] == second_word[j-2]) \
            and (first_word[i-2] == second_word[j-1]):
                matrix[i][j] = min(matrix[i][j],
                                   matrix[i-2][j-2] + cost)

    return matrix[first_word_len][second_word_len]


if __name__ == '__main__':
    import sys
    print edit_distance(sys.argv[1], sys.argv[2])