如何实现diff功能？

Question

我将如何去实现diff函数，比如stackoverflow的问题修订历史记录。

Answer 1

您在这里有一个javascript example差异算法的实现。基于

：

P. Heckel, A technique for isolating differences between files 通讯。 ACM，21，（4），264--268（1978）。

实施，本身具有两种功能，其中之一是推荐使用：

diffString(String oldFile, String newFile) 

此方法需要两个字符串并计算各个差异。最终的结果是用HTML标记的'newFile'（以表示旧文件的删除和newFile的添加）。

Answer 2

我想唯一的方法是比较形成2个字符串的每个字符。类似这样的：

void diff(String first,String second) { 
    int biggest = (first.length() > second.length()) ? first.length() : second.length(); 
    for(int i = 0;i < biggest;i++) { 
     //compare each char from the longest string with each char from the shorter 
     // do something with them if they're not equal 
    } 
} 

这只是我如何去做的一个草图。一切都取决于你想要对数据做什么。

Answer 3

我会找到FreeBSD diff实用程序的代码并将其用作基准。当许可证允许进行这种复制时，重新制造轮子没有意义。

Answer 4

如果你想要的是修订历史，不要重新开始差异化的轮子。只需将所有内容都投入到版本控制中，并使用它的差异和日志功能对于简单的线性历史记录，就像RCS那样简单。或者你可以扔最新的大炮，并使用git。

大多数差异公用事业公司做一行一行的差异。堆栈溢出做逐字比较。对于那样的东西wdiff是必要的。大多数版本控制系统都允许您插入diff实用程序。开箱即用，git diff --color-words非常接近这里所做的。稍微摆弄一下这些设置，你就可以得到它来吐出一些你可以制作成漂亮的网页的东西。

Answer 5

大多数算法都基于LCS：Longest common subsequence。以有效的方式实施它并不明显。你可能会在网上找到各种各样的语言实现。