performance - 莱文斯坦转置距离

Question

如何使用动态编程单独实现转置/交换/旋转/交换距离。我必须强调我不想检查其他操作（即复制、删除、插入、杀死等）只是转置/交换。

我希望仅将 Levenstein 的算法应用于交换距离。代码会是什么样子？

Answer 1

动态规划的有效应用通常需要将任务分解为同一任务的多个实例以获得更短的输入。在 Levenstein 距离的情况下，这归结为两个字符串的前缀以及从一个字符串到另一个字符串所需的编辑次数。我看不出在您的情况下如何实现这种分解。至少我看不到会导致多项式时间算法的算法。

此外，目前还不清楚您在谈论什么操作。根据上下文，交换或交换可以表示与换位相同的意思，也可以表示用任意其他字母替换一个字母，例如test->text. 如果通过“transpose/swap/twiddle/exchange”你试图只说“transpose”，那么你应该看看Counting the nearest swaps required to convert an permutation into another。如果不是，请澄清问题。

Answer 2

我不确定在这种情况下是否可以使用 Levenstein 的算法。如果没有插入或删除操作，只有在相同长度和相同字符的字符串之间才能很好地定义距离。仅通过换位无法转换为相同字符串的字符串示例：

AB, ABC
AAB, ABB

有了这个，算法可以找到所有可能的字符位置排列，而不是在两个字符串中的相同位置，并寻找可以用最少数量的转置或交换来表示的排列。