目前最好的基于单词或字符的差异算法是什么？

Question

所以，我希望能够按单词基础找到两个字符串之间的差异（如果按字符比较快，则可能更快，但是如果按字符比较快，则我想以这种方式执行）。

以下是我想要实现的示例： 源文本：

Hello there!

抱歉，我只能以英文回答。

Helay scere?

差异：

Hel[lo](ay) [th](sc)ere[!](?)

• 方括号内的文本是被删除的内容，括号内的文本是添加的内容。

有一种非常hackish的方法可以使用命令行工具（例如opendiff），但它需要在每个字符之间插入换行符，因为opendiff是基于行的。

我正在使用ruby，并没有找到任何工具来做到这一点... 但语言并不是非常重要，因为算法可以很容易地移植。

谢谢。

- NullVoxPopuli

---

因为您提到了现有的工具，我应该指向wdiff（单词差异）和dwdiff（分隔符单词差异）Unix实用程序。我已经使用bash编写了一些Unix实用程序，将dwdiff转换为半图形化工具在这里。源代码注释显示了几种使用方法。 - masukomi

Answer 1

请查看https://github.com/pvande/differ。这个宝石可以实现您想要的功能。

- alex

Answer 2

你可能想检查一下这个链接：http://en.wikipedia.org/wiki/Longest_common_subsequence_problem。它并不难实现。

- Victor Moroz

Answer 3

这里有一个用于字符串比较的Ruby宝石(diff-lcs)：http://rubydoc.info/gems/diff-lcs/1.1.3/frames 之前，我只是在irb中执行了以下代码：

require 'rubygems'
require 'diff/lcs'
require 'diff/lcs/array'
require 'diff/lcs/string'

因此，通过这个二维差异数组的变化，编写插入、内联删除和插入标记的逻辑变得非常简单。

虽然我不确定这是否是最佳方式。

- NullVoxPopuli

Answer 4

因此，您可以反复使用上面链接的LCS（最长公共子序列）来查找所有共同的字符串，并从两个字符串中删除它们，用其他字符串替换它们 - 让我们称之为“*”。然后，同时迭代两个字符串，重新将共同的和不同的部分重新组合在一起。

例如：

A) Hello there!
B) Helay scere?

LCS detection gives us ["Hel"," ","ere"], and after replacement we have
A) *lo*th*!
B) *ay*sc*?

Now you split on the delimiter ("*") giving you
A) ["lo","th","!"]
B) ["ay","sc","?"]

从这里开始，你只需要进行简单的网格划分。需要注意的是，可能会出现空条目，例如如果你在“Hell”和“Hel”上使用此方法，最终可能会得到：

Common LCS) ["Hel"]
A) ["l"]
B) [""]

meaning your result will be Hel[l]() 

Hopefully that is acceptable.

- Noxville

Answer 5

一个解决方案是找到字符串之间的编辑距离。

- Bhavana C