基本字符串差异算法的推荐寻求

Question

我正在寻找一种算法，它以两个字符串source和destination作为参数，并返回将源字符串转换为目标字符串所需的步骤。这是一种将Levenshtein距离推进一步的方法。

例如，

输入：source为"abc"，dest为"abbc" 输出：在源字符串的位置1处插入'b'

输入：source为"abc"，dest为"ac" 输出：在源字符串的位置1处删除'b'

非常感谢。

- kujawk

---

听起来像是作业题，如果是的话你应该打上标签，我们也不会拒绝回答。 - Bill K

绝对不是作业，这是为了在我的自定义塞班文本框中进行基于触摸的单词校正。 - kujawk

如果你没有Dan Gusfield的书，我强烈推荐它。这确实是该主题唯一明确的书籍。 - San Jacinto

会去看看，感谢推荐。 - kujawk

http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198 但不要被“计算生物学”这个词吓到。 - San Jacinto

Answer 1

只需按照wikipedia上显示的算法进行操作，理解并进行必要的修改。它确实可以解决您的问题，您可能只是不知道，并且在操作过程中没有记录答案。

- Steinbitglis

Answer 2

请查看维基百科上关于差异算法的内容：http://en.wikipedia.org/wiki/Diff。

- jvilalta

Answer 3

你可以先尝试将所有字母成对排列。当你尽可能配对后，插入和删除的部分就会变得明显起来。

abcde
| /|
acbdd

所以你要移除 b & e 并添加一个 b & d

记住线不能交叉。

- Bill K

---

实际上，你的方法不能保证最优解。最优解可能是做出不直观的决策，进行两次替换而不是一次插入。这取决于你如何权衡操作（插入和删除通常非常昂贵）。著名的算法会考虑到这一点。它们通常依赖于动态规划解决方案。 - San Jacinto

你说得对。我一开始以为这是一个学校作业，简单性比准确性更有价值。如果你想要准确性，可以扫描最大的匹配块，然后取出该块两侧剩余的内容（对于两个字符串都是如此），并进行递归处理。 - Bill K

Answer 4

我会尝试找到一种方法将其发送到现有的经过充分测试的差异工具，并使用该差异的结果，例如 diff -e 或 diff -n。

- shoover