string - 归一化编辑距离公式解释

Question

基于本文: 关于 PAITERN 分析的 IEEE 交易:Computation of Normalized Edit Distance and Applications In this paper Normalized Edit Distance如下:

Given two strings X and Y over a finite alphabet, the normalized edit distance between X and Y, d( X , Y ) is defined as the minimum of W( P ) / L ( P )w, here P is an editing path between X and Y , W ( P ) is the sum of the weights of the elementary edit operations of P, and L(P) is the number of these operations (length of 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)归一化编辑距离不能简单地用编辑距离计算。您可能需要实现他们的算法。

例3.1(c)的解释:

从aaab到abbb，论文使用了以下转换:

1. 将a与a匹配；
2. 跳过第一个字符串中的a；
3. 跳过第一个字符串中的a；
4. 跳过第二个字符串中的b；
5. 跳过第二个字符串中的b；
6. 匹配最后的 b。

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