基于本文：
IEEE PAITERN 分析交易：归一化编辑距离的计算及应用本文归一化编辑距离 http://www.csie.ntu.edu.tw/~b93076/Computation%20of%20Normalized%20Edit%20Distance%20and%20Applications.pdf如下：
给定有限字母表上的两个字符串 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))
您可能误解了该指标。有两个问题：
标准化步骤是划分W(P)这是编辑过程的权重L(P)，这是编辑过程的长度，而不是像您那样超过字符串的最大长度；
此外，论文还表明（示例 3.1）归一化编辑距离不能简单地用编辑距离来计算。您可能需要实现他们的算法。
例3.1(c)的解释：
From aaab to abbb，论文使用了以下变换：
- match
a with a;
- skip
a在第一个字符串中；
- skip
a在第一个字符串中；
- skip
b在第二个字符串中；
- skip
b在第二个字符串中；
- 匹配决赛
bs.
这是 6 个操作，这就是为什么L(P)是 6；从 (a) 中的矩阵来看，匹配的成本为 0，跳过的成本为 2，因此我们的总成本为0 + 2 + 2 + 2 + 2 + 0 = 8，这正是W(P), and W(P) / L(P) = 1.33。 (b) 可以获得类似的结果，我将其留给您作为练习:-)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
