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

Question

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

Answer 1

阅读注释，看来这就是问题所在：

您将得到一组字符串对的，都是一样的长度，每对是输入与来自函数的输出配对的一些功能。所以，对于A，B，我们知道f（A）= B。目标是用大量的A，B对对f（）进行逆向工程。

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

更好的开始将是汉明距离（修改为允许多个字符）或Jaccard相似度来确定字符串中有多少位置根本不会改变所有对。然后，你只剩下那些改变了的人。

如果字母改变，这将失败。

要检测换档，您想使用全局比对（Needleman-Wunsch）。然后，您将看到类似"ABCDE"=>"xABCD"的内容，以显示从输入到输出的结果是左移。总的来说，我觉得Levenshtein距离对于帮助你获得原始算法做的很少。