什么是以与版本页面上的SO相同的方式对两个字符串进行区分的算法？

Question

我试图逐个区分两个字符串,类似于StackOverflow在版本编辑页面上对两个字符串进行区分的方式.这样做的算法是什么？是否有宝石或其他标准库可以实现这一目标？

编辑:我已经看到其他差异算法(与Ruby不同),他们似乎导致以下结果:

>> 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."

请注意单词基于每个单词的差异？我希望通过短语进行更多区分,所以上面的代码输出:

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

我希望得到太多吗？

Answer 1

您正在寻找的算法是最长公共子序列，它为您完成了大部分工作。

大纲是沿着这些路线的。

1. 按字分割（输入、输出）
2. 计算输入/输出数组的 LCS。
3. 穿过阵列并智能地连接区域。

例如，假设您有：

“你好世界，这是一个测试”

和....相比：

“世界先生你好”

LCS 的结果是

• “先生” +
• “你好” =
• “世界”=
• “这个” -
• “是” -
• “一种” -
• “测试” -

现在你在建造时撒上特制的酱汁。您将字符串连接在一起，同时注意之前的操作。朴素的算法只是连接具有相同动作的部分。

• “先生” +
• “你好世界”=
• “这是一个测试” -

最后将其转换为 html：

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

当然，魔鬼在细节中：

• 您需要考虑如何处理标签
• 你比较 markdown 还是 html
• 是否存在 UI 不再有意义的边缘情况。
• 您是否需要对标点符号进行特殊处理。