如何实现diff功能？

Question

如何实现 diff 函数，例如Stack Overflow的问题修订历史记录？

Answer 1

您在这里有一个实现差异算法的 javascript示例。

基于：

P. Heckel，一种隔离文件差异的技术 通讯。 ACM，21，（4），264--268（1978）。

实现本身有两个功能，其中一个建议使用：

diffString( String oldFile, String newFile )

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

Answer 2

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

Answer 3

大多数算法都基于LCS：最常见的子序列。以有效的方式实施它并不明显。您可能会在网上找到各种语言的各种实现。

Answer 4

我想唯一的方法是比较形成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 5

如果您想要的是修订历史记录，请不要从diff开始重新发明轮子。只需将所有内容都放入版本控制并使用其差异和日志记录功能。对于简单的线性历史记录，只需 RCS 即可。或者你可以扔掉最新的大炮并使用 git 。

大多数diff实用程序都会逐行进行差异操作。堆栈溢出执行逐字差异。因为像 wdiff 这样的东西是必要的。大多数版本控制系统允许您插入diff实用程序。开箱即用， git diff --color-words 非常接近这里所做的。稍微摆弄一下设置就可以让它吐出一些你可以制作成漂亮网页的东西。