归一化编辑距离公式的解释

Question

基于本文:分析：归一化编辑距离的计算及其应用如下：

给定有限字母表上的两个字符串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)中有lambdas的列意味着为了插入或删除"a“或"b”，它要花费2。

​

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

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

这些步骤的费用之和为W(P)。步骤数为4，即L(P)。

​

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

​

1. 先保留a(成本为0)
2. 删去首b(费用2)
3. 删除第二个b(费用2)
4. 插入a(费用2)
5. 插入a(费用2)
6. 保留最后b(成本为0)

该路径有6个步骤，L(P)为6，步骤代价之和为8，W(P)为8，因此规范化编辑距离为8/6 = 4/3，约为1.33。