python - 计算编辑距离

Question

我编写了一个函数来计算两个给定字符串之间的编辑距离。但是，它似乎无法正常工作。替换成本 = 2，插入成本 = 1，删除成本 = 1

def MyLevenshtein(String1, String2):
    if len(String1) and len(String2) != 0:
        rows = len(String1) + 1
        columns = len(String2) + 1
        distance = [[0 for x in range(columns)] for x in range(rows)]
        for i in range(1, rows):
            distance[i][0] = i
        for i in range(1, columns):
            distance[0][i] = i
        for column in range(1, columns):
            for row in range(1, rows):
                if String1[row - 1] == String2[column - 1]:
                    cost = 0
                else:
                    cost = 2
                distance[row][column] = min(distance[row - 1][column] + 1,  # deletion
                                     distance[row][column - 1] + 1,  # insertion
                                     distance[row - 1][column - 1] + cost) #substitution
    Distance = distance[row][column]
    return Distance

例如，当我使用字符串“hamchenoonan”和“hamchenin”调用该函数时，会返回 5，尽管它应该返回 7。

Answer 1

在这里我看到了很多实现: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

所以我只是询问所有开箱即用的人对成本的理解。

import numpy as np

def Mylevenshtein(String1, String2):
    if len(String1) and len(String2) != 0:
        rows = len(String1) + 1
        columns = len(String2) + 1
        distance = [[0 for x in range(columns)] for x in range(rows)]
        for i in range(1, rows):
            distance[i][0] = i
        for i in range(1, columns):
            distance[0][i] = i
        for column in range(1, columns):
            for row in range(1, rows):
                if String1[row - 1] == String2[column - 1]:
                    cost = 0
                else:
                    cost = 2
                distance[row][column] = min(distance[row - 1][column] + 1,  # deletion
                                     distance[row][column - 1] + 1,  # insertion
                                     distance[row - 1][column - 1] + cost) #substitution
    Distance = distance[row][column]
    return Distance


def levenshtein1(s1, s2):
    if len(s1) < len(s2):
        return levenshtein1(s2, s1)

    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[
                             j + 1] + 1  # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1  # than s2
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]


def levenshtein2(a, b):
    if not a: return len(b)
    if not b: return len(a)
    return min(levenshtein2(a[1:], b[1:])+(a[0] != b[0]), levenshtein2(a[1:], b)+1, levenshtein2(a, b[1:])+1)


def levenshtein3(s,t):
    s = ' ' + s
    t = ' ' + t
    d = {}
    S = len(s)
    T = len(t)
    for i in range(S):
        d[i, 0] = i
    for j in range (T):
        d[0, j] = j
    for j in range(1,T):
        for i in range(1,S):
            if s[i] == t[j]:
                d[i, j] = d[i-1, j-1]
            else:
                d[i, j] = min(d[i-1, j], d[i, j-1], d[i-1, j-1]) + 1
    return d[S-1, T-1]




def levenshtein5(source, target):
    if len(source) < len(target):
        return levenshtein5(target, source)

    # So now we have len(source) >= len(target).
    if len(target) == 0:
        return len(source)

    # We call tuple() to force strings to be used as sequences
    # ('c', 'a', 't', 's') - numpy uses them as values by default.
    source = np.array(tuple(source))
    target = np.array(tuple(target))

    # We use a dynamic programming algorithm, but with the
    # added optimization that we only need the last two rows
    # of the matrix.
    previous_row = np.arange(target.size + 1)
    for s in source:
        # Insertion (target grows longer than source):
        current_row = previous_row + 1

        # Substitution or matching:
        # Target and source items are aligned, and either
        # are different (cost of 1), or are the same (cost of 0).
        current_row[1:] = np.minimum(
                current_row[1:],
                np.add(previous_row[:-1], target != s))

        # Deletion (target grows shorter than source):
        current_row[1:] = np.minimum(
                current_row[1:],
                current_row[0:-1] + 1)

        previous_row = current_row

    return previous_row[-1]

def levenshtein6(s, t):
    ''' From Wikipedia article; Iterative with two matrix rows. '''
    if s == t:
        return 0
    elif len(s) == 0:
        return len(t)
    elif len(t) == 0:
        return len(s)
    v0 = [None] * (len(t) + 1)
    v1 = [None] * (len(t) + 1)
    for i in range(len(v0)):
        v0[i] = i
    for i in range(len(s)):
        v1[0] = i + 1
        for j in range(len(t)):
            cost = 0 if s[i] == t[j] else 1
            v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
        for j in range(len(v0)):
            v0[j] = v1[j]

    return v1[len(t)]


for implementation_variant in [g for g in globals() if "leven" in g]:
    print("Try variant %s" % implementation_variant)
    for a, b in [("hamchenoonan", "hamchenin"),
                 ("Tier", "Tor")]:
        print(" -Distance of %s and %s is %i" % (a, b, globals()[implementation_variant](a, b)))

输出显示:

Try variant Mylevenshtein
 -Distance of hamchenoonan and hamchenin is 5
 -Distance of Tier and Tor is 3
Try variant levenshtein1
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein2
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein3
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein5
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein6
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2

德语维基百科中提到了 Tier 和 Tor 的距离，只是作为第二次验证。所以民主的答案似乎是 4。