c# - 以与 SO 在版本页面上相同的方式区分两个字符串的算法是什么？

Question

我正在尝试按短语区分两个字符串，类似于 StackOverflow 在版本编辑页面上区分两个字符串的方式。执行此操作的算法是什么？是否有 gems 或其他标准库可以实现此目的？

编辑:我见过其他差异算法(Differ 与 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

您要查找的算法是Longest Common Subsequence它会为您完成大部分工作。

大纲就是这样的。

1. 按词拆分(输入，输出)
2. 计算输入/输出数组的 LCS。
3. 遍历阵列并智能地连接区域。

例如假设您有:

“你好，这是一个测试”

相比于:

“先生 Hello World ”

LCS的结果是

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

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

• “先生”+
• “ Hello World ”=
• “这是一个测试” -

最后将其转换为 html:

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

当然，细节决定成败:

• 您需要考虑如何处理标签
• 你比较markdown还是html
• 是否存在用户界面不再有意义的极端情况。
• 您需要对标点符号进行特殊处理吗？