谁能解释一下计算 Levenshtein 距离的代码？

Question

我得到的这段代码可以快速返回两个字符串之间的编辑距离是否正好为 2。

def li(s, i):
    try:
        return s[i]
    except IndexError:
        return None
    
def f(str1, str2):
 t = [4, 4, 1, 2, 3]
 for i, str1_symb in enumerate(str1):
    p = 4
    res = []
    for j, t_val in enumerate(t):
        p = min(t_val - (str1_symb == li(str2, i + j - 2)), p, li(t, j + 1) or 4) + 1
        res.append(p)
    t = res
 return li(t, len(str2) - len(str1) + 2) == 3

您可以使用以下方法进行测试：

f("zzzzfood", "zzzzdodod") 

例如它将返回True

和

f("zzzzfood", "zzzzdodo")

这将返回 False。

计算编辑距离的标准算法会构建一个动态规划表，并使用以下公式从左到右、从上到下填充元素：

（来自上面链接的维基页面）

如果您只想在编辑距离最多为 2 时返回，则只能查看距对角线左右最多 2 的动态规划单元。

上面的代码显然没有做到这一点，我无法弄清楚它在做什么。一些特别神秘的部分：

• t=[4,4,1,2,3]的作用是什么？
• 在此代码中，li() 函数同时采用字符​​串和列表。如果索引i大于或等于 ，则仅返回 None len(s)。有时i会是负数，但仍会返回来自 的信件s。
• li(t, j + 1) or 4li(t, j + 1)如果是则返回 4None但我不知道它的目的是什么。
• 的目的/意义是什么p？

有人能破译吗？

Answer 1

好吧——首先，请不要使用此代码。

从高层次来看，它所做的就是 Stef 在评论中所说的，检查近对角线。的索引位置i正在迭代，并且循环j正在遍历对角线附近的第二个字符串

添加一些打印内容可以让这一点变得更清晰：

def f(str1, str2):
    t = [4, 4, 1, 2, 3]
    for i, str1_symb in enumerate(str1):
        print()
        print(f"i={i}, str1_symb={str1_symb}")
        p = 4
        res = []
        print("res:", res)
        for j, t_val in enumerate(t):
            print()
            print(f" - j={j}, t_val={t_val}")
            p1 = t_val - (str1_symb == li(str2, i + j - 2))
            p2 = p
            p3 = li(t, j + 1) or 4
            print(f" - p1a: t_val - (str1_symb == li(str2, i + j - 2))  ==>  {t_val} - ({str1_symb} == li({str2}, {i} + {j} - 2))")
            print(f" - p1b: t_val - (str1_symb == li(str2, i + j - 2))  ==>  {t_val} - ({str1_symb} == li({str2}, {i + j - 2}))")
            print(f" - p1c: t_val - (str1_symb == li(str2, i + j - 2))  ==>  {t_val} - ({str1_symb} == {li(str2, i + j - 2)})")
            print(f" - p1d: t_val - (str1_symb == li(str2, i + j - 2))  ==>  {t_val} - {(str1_symb == li(str2, i + j - 2))}")
            print(f" - p1e: t_val - (str1_symb == li(str2, i + j - 2))  ==>  {p1}")
            print(" - ")
            print(f" - p2: {p}")
            print(f" - ")
            print(f" - p3a: li(t, j + 1) or 4 ==> li({t}, {j} + 1) or 4")
            print(f" - p3b: li(t, j + 1) or 4 ==> li({t}, {j + 1}) or 4")
            print(f" - p3c: li(t, j + 1) or 4 ==> {li(t, j + 1)} or 4")
            print(f" - p3: {li(t, j + 1) or 4}")
            print(f" - ")
            p = min(p1, p2, p3) + 1
            print(f" - p: min(p1, p2, p3) + 1 ==> min({p1}, {p2}, {p3}) + 1")
            print(f" - p: min(p1, p2, p3) + 1 ==> {min(p1, p2, p3) + 1}")
            res.append(p)
        t = res
        print(f"t = {t}")
    print()
    print(f"result: li(t, len(str2) - len(str1) + 2) == 3 ==> li({t}, {len(str2)} - {len(str1)} + 2) == 3")
    print(f"result: li(t, len(str2) - len(str1) + 2) == 3 ==> li({t}, {len(str2) - len(str1) + 2}) == 3")
    print(f"result: li(t, len(str2) - len(str1) + 2) == 3 ==> {li(t, len(str2) - len(str1) + 2)} == 3")
    print(f"result: li(t, len(str2) - len(str1) + 2) == 3 ==> {li(t, len(str2) - len(str1) + 2) == 3}")
    return li(t, len(str2) - len(str1) + 2) == 3

我的阅读是t = [4, 4, 1, 2, 3]，它设置偏移值，并最大化（以便我们有效地忽略 -ive 列表索引值，任何大于 3 的值都应该产生相同的结果）负列表索引是多余的计算，但无害。

我们可以看到 i 和 j 如何在矩阵中移动：

产生以下差分矩阵：

将 p 计算p = min(t_val - (str1_symb == li(str2, i + j - 2)), p, li(t, j + 1) or 4) + 1分为三个部分使其工作更加清晰：

p1 = t_val - (str1_symb == li(str2, i + j - 2))
p2 = p
p3 = li(t, j + 1) or 4
p = min(p1, p2, p3) + 1

我们可以看到，这一步用作t/res最后一次计算的内存，我们在其中查找先前计算的偏移量并计算新值

最后一点是，看起来一切都被放大了，1以便作者可以使用 -true 来表示差异；然后将其添加回 ，min将 的距离缩放2至 的距离，3从而得出最终的相等

这本书太难读了，我不断地获得一些理解，然后失去了想法，这是一个有趣的逆向工程问题，但生产代码却很糟糕。

当我花了一点时间试图想出一个更好的方法时，我意识到我最终还是走上了同样的道路；尽管我对可读性提出了批评，但我还是不得不赞扬作者的效率。计算和存储其他条件的算法并将其执行下来是聪明而高效的。