levenshtein-distance - 如何计算多个相关的 Levenshtein 距离？

Question

给定两个长度相等的字符串，Levenshtein 距离允许找到在给定第一个字符串的情况下获得第二个字符串所需的最小转换次数。但是，我想找到一种方法来调整多对字符串的算法，因为它们都是以相同的方式生成的。

Answer 1

阅读评论，似乎这是问题所在：

给定一组字符串对，长度相同，每对字符串都是某个函数的输入，与函数的输出配对。因此，对于 A,B 对，我们知道 f(A)=B。目标是使用大量 A、B 对对 f() 进行逆向工程。

在整个集合上使用 Levenshtein 距离最多可以告诉您必须发生的最大转换次数。

一个更好的开始将是汉明距离（修改为允许多个字符）或 Jaccard 相似性，以确定字符串中有多少位置对于所有对都没有改变。然后，您只剩下那些确实发生变化的人。

如果字母移位，这将失败。

要检测移位，您需要使用全局对齐 ( Needleman-Wunsch )。然后你会看到类似"ABCDE"=>"xABCD"的东西，从输入到输出，有一个左移。

总的来说，我觉得 Levenshtein distance 对你获得原始算法的帮助很小。