我想差异比较两个字符串由语，类似于计算器的diff两个字符串上的版本编辑页面的方式。什么是一个算法来做到这一点？是否有宝石，或者说，做到这一点其它标准库？

I'm trying to diff two strings by phrase, similar to the way that StackOverflow diffs the two strings on the version edits page. What would be an algorithm to do this? Are there gems, or other standard libraries that accomplish this?

编辑：我见过的其他版本比较算法（ 的不同使用Ruby），他们似乎导致以下：

I've seen other diffing algorithms (Differ with Ruby) and they seem to result in the following:

>> o = 'now is the time when all good men.'
>> p = 'now some time the men time when all good men.'
>> Differ.diff_by_word(o,p).format_as(:html)
=> "now <del class=\"differ\">some</del><ins class=\"differ\">is</ins> 
   <del class=\"differ\">time </del>the <del class=\"differ\">men </del>time
   when all good men."

请注意如何将字显示差异在每个单词的基础？我想用语版本比较多的一些方法，因此上述code输出：

Note how the words are diffed on a per word basis? I'd like some way of diffing more by phrase, so the above code output:

=> "now <del class=\"differ\">some time the men</del><ins class=\"differ\">is
   the</ins> time when all good men."

我是希望太多了？

Am I hoping for too much?

推荐答案

您正在寻找的是最长的算法公共子的它大部分的工作给你。

The algorithm you are looking for is Longest Common Subsequence it does most of the work for you.

轮廓是沿着这些路线的东西。

The outline is something along these lines.

将字（输入，输出）分割 在计算LCS输入/输出数组。 漫步阵列，并加入了智能化领域。

因此​​，例如说你有：

So for example say you have:

你好世界，这是一个测试

"hello world this is a test"

则为：

先生你好世界

这是濒海战斗舰的结果是

The result from the LCS is

在老总+ 在你好= 在世界= 在本 - 在是 - 在一 - 在测试 -

现在你建立的时候洒上特制的酱汁。你加入了串起来，同时保持铭记previous行动。天真的算法是刚刚加入的是同一个动作的部分。

Now you sprinkle the special sauce when building up. You join the string together while staying mindful of the previous action. The naive algorithm is just join sections that are the same action.

在老总+ 在世界你好= 在这是一个测试 -

最后，你将其转换为HTML：

Finally you transform it to html:

<ins>mister</ins> hello world <del>this is a test</del>

当然，魔鬼在细节：

Of course the devil is in the detail:

您需要考虑如何处理标记 请你比较降价或HTML 是否有任何边缘情况下，用户界面​​停止决策意识。 您是否需要特殊处理的标点符号。