string - 归一化编辑距离公式说明

Question

基于这篇论文： IEEE TRANSACTIONS ON PAITERN ANALYSIS : Computation of Normalized Edit Distance and Applications 在本文中 Normalized Edit Distance如下：

给定有限字母表上的两个字符串 X 和 Y，X 和 Y 之间的归一化编辑距离 d( X , Y ) 定义为 W( P ) / L ( P )w 的最小值，这里 P 是之间的编辑路径X 和 Y ，W ( P ) 是 P 的基本编辑操作的权重之和，L(P) 是这些操作的数量（P 的长度）。

我可以安全地将上面解释的归一化编辑距离算法翻译为：

normalized edit distance = 
levenshtein(query 1, query 2)/max(length(query 1), length(query 2))

Answer 1

您可能误解了该指标。有两个问题：

1. 归一化步骤是将W(P)编辑过程的权重除以编辑过程L(P)的长度，而不是像您所做的那样超过字符串的最大长度；

2. 此外，该论文表明（示例 3.1）归一化编辑距离不能简单地用 levenshtein 距离计算。您可能需要实现他们的算法。

示例 3.1 (c) 的解释：

从aaab到abbb，论文使用了以下变换：

1. 匹配; a_a
2. 跳过a第一个字符串；
3. 跳过a第一个字符串；
4. 跳过b第二个字符串；
5. 跳过b第二个字符串；
6. 匹配决赛bs。

这些是 6 个操作，这就是为什么L(P)是 6；从 (a) 中的矩阵来看，匹配的成本为 0，跳过的成本为 2，因此我们的总成本为0 + 2 + 2 + 2 + 2 + 0 = 8，恰好是W(P)，并且W(P) / L(P) = 1.33。(b) 可以得到类似的结果，我将把它留给你作为练习:-)

Answer 2

图 2（a）中的 3 是指将“a”变为“b”或将“b”变为“a”的成本。图 2(a) 中带有 lambda 的列意味着插入或删除“a”或“b”需要花费 2。

在图 2(b) 中，W(P) = 6，因为该算法执行以下步骤：

1. 先保留一个（成本0）
2. 将第一个b转换为a（成本 3）
3. 将第二个b转换为a（成本 3）
4. 保持最后b (成本 0)

这些步骤的成本总和为W(P)。步数为 4，即L(P)。

在图 2(c) 中，步骤不同：

1. 先保留一个（成本0）
2. 删除第一个b（成本 2）
3. 删除第二个b（成本 2）
4. 插入一个（成本 2）
5. 插入一个（成本 2）
6. 保持最后b (成本 0)

在这条路径中，有六个步骤，因此L(P)为 6。步骤的成本总和为 8，因此W(P)为 8。因此归一化编辑距离为 8/6 = 4/3，约为1.33。