Levenshtein 距离（编辑距离，动归） Python 实现

Levenshtein 距离

叫编辑距离大家就都秒 get√ 了，经典动归。
这里给出 Python 的实现。

def levenshtein(first, second):
    first_length = len(first)
    second_length = len(second)
    if first_length > second_length:
        first, second = second, first
        first_length, second_length = second_length, first_length
    if first_length == 0:
        return second_length
    if second_length == 0:
        return first_length
    distance_matrix = [range(second_length+1) for x in range(first_length+1)]
    # print distance_matrix
    for i in range(1, first_length+1):
        for j in range(1, second_length+1):
            deletion = distance_matrix[i - 1][j] + 1
            insertion = distance_matrix[i][j - 1] + 1
            substitution = distance_matrix[i - 1][j - 1]
            if first[i - 1] != second[j - 1]:
                substitution += 1
            distance_matrix[i][j] = min(insertion, deletion, substitution)
    print distance_matrix
    return distance_matrix[first_length][second_length]

有需要的自取。