问题标签 [word-diff]

我有两个字符串，想显示它们之间的区别。例如，如果我有字符串“我来自火星”和“我来自金星”，输出可能是“我来自金星”。（通常用于显示审计日志中的更改等）

有一个简单的算法吗？我正在使用 C#，但我想通用算法可以适用于任何编程语言。

或者是否有一个框架类/第三方库可以做这种事情？

突出PHP中两个字符串之间差异的最简单方法是什么？

我正在按照 Stack Overflow 编辑历史页面的思路进行思考，其中新文本为绿色，删除的文本为红色。如果有任何预先编写的函数或类可用，那将是理想的。

分析显示这是我编写的一个小文字游戏代码中最慢的部分：

笔记：

• distance()被调用超过 500 万次，其中大部分来自 getchildren，它应该获取单词列表中与word恰好相差 1 个字母的所有单词。
• wordlist 被预先过滤为仅包含包含相同数量字母的单词，word因此可以保证word1并且word2具有相同数量的字符。
• 我对 Python 相当陌生（3 天前开始学习它），所以对命名约定或其他样式的评论也很感激。
• 对于单词表，使用“2+2lemma.txt”文件获取12dict 单词表

结果：

谢谢大家，结合不同的建议，我现在让程序运行速度提高了两倍（除了我在询问之前自己进行的优化，所以速度比我最初的实现提高了大约 4 倍）

我用两组输入进行了测试，我将它们称为 A 和 B

优化 1：迭代 word1,2 的索引... from

迭代字母对使用zip(word1, word2)

输入 A 的执行时间从 11.92 到 9.18，输入 B 的执行时间从 79.30 到 74.59

优化 2：除了距离方法（我在其他地方仍然需要 A* 启发式）之外，还添加了一种单独的方法

输入 A 的执行时间从 9.18 到 8.83，输入 B 的执行时间从 74.59 到 70.14

优化3：这里的大赢家是使用izip而不是zip

输入 A 的执行时间从 8.83 到 5.02，输入 B 的执行时间从 70.14 到 41.69

我可能会更好地用较低级别的语言编写它，但我现在对此感到满意。谢谢大家！

再次编辑：更多结果使用 Mark 的方法检查第一个字母不匹配的情况使其从 5.02 -> 3.59 和 41.69 -> 29.82 下降

在此基础上并合并izip而不是range，我最终得到了这个：

挤压得更多，使时间从 3.59 -> 3.38 和 29.82 -> 27.88

甚至更多的结果！

尝试 Sumudu 的建议，即我生成一个与“word”相差 1 个字母的所有字符串的列表，然后检查哪些字符串在 wordlist中，而不是 is_neighbor 函数，我最终得到了这个：

最终速度变慢了（3.38 -> 3.74 和 27.88 -> 34.40），但看起来很有希望。起初我认为我需要优化的部分是“one_letter_off_strings”，但分析显示并非如此，而且慢的部分实际上是

我想如果我切换“oneoff”和“wordlist”并在我正在寻找两个列表的交集时以另一种方式进行比较，是否会有任何区别。我用字母上的 set-intersection替换它：

砰！3.74 -> 0.23 和 34.40 -> 2.25

这真是令人惊讶，与我最初的幼稚实现的总速度差异：23.79 -> 0.23 和 180.07 -> 2.25，比原来的实现快大约 80 到 100 倍。

如果有人有兴趣，我会发表博客文章来描述程序并描述所做的优化，包括此处未提及的优化（因为它位于不同的代码部分中）。

大辩论：

好的，我和 Unknown 正在进行一场大辩论，您可以在他的回答的评论中阅读。他声称，如果将其移植到 C 中，使用原始方法（使用 is_neighbor 而不是使用集合）会更快。我尝试了 2 个小时来获得我编写的 C 模块来构建和可链接，但在尝试后没有太大成功按照这个和这个例子，看起来这个过程在Windows中有点不同？我不知道，但我放弃了。无论如何，这是程序的完整代码，文本文件来自12dict单词列表使用“2+2lemma.txt”文件。对不起，如果代码有点乱，这只是我一起破解的。此外，我忘记从单词列表中删除逗号，因此这实际上是一个错误，您可以保留它以进行相同的比较，或者通过在 cleanentries 的字符列表中添加逗号来修复它。

我留下了 is_neighbors 方法，即使它没有被使用。这是建议移植到 C 的方法。要使用它，只需将 getchildren 替换为：

至于让它作为 C 模块工作，我并没有那么远，但这就是我想出的：

我使用以下方法对此进行了分析：

python -m cProfile "Wordgame.py"

记录的时间是AStar方法调用的总时间。快速输入集是“诗歌诗人”，而长输入集是“诗人诗歌”。不同机器之间的时间显然会有所不同，因此如果有人最终尝试这样做，请按原样比较程序的结果，以及与 C 模块的比较。

只是试图让 diff 对某些类型的文档更好地工作。以 LaTeX 为例，我可能有一个很长的段落，严格来说只有一行，但如果只更改了一个句子，我不想看到整个段落。特别是如果我正在运行某种版本控制并且共同作者与我编辑相同的段落（但不是相同的句子）。我不希望这表现为冲突。

这是次要问题。主要问题是我是否可以使用 diff 逐句查看。谢谢。

编辑

wdiff几乎是完美的。diff但是是否有一个合并等价物，就像diff3?

这个 StackOverflow 答案有一张 KDiff3 突出显示行内差异的图像。有人知道可以在命令行上显示相同（例如，通过颜色）的工具吗？

考虑这一点的另一种方法是想要区分补丁文件中的每个差异。

我经常需要比较 SQL 过程以确定最新版本中发生了什么变化。问题是，每个人都有自己的格式化风格，SQL（通常）不关心换行符放在哪里（例如，where 子句都在一行上，而每个 AND 之前的换行符）。

这使得很难看到实际差异（尤其是对于长程序）。我似乎找不到一个免费的 diff/merge 实用程序可以让我忽略换行符（即视为空格）。到目前为止，我已经尝试过 WinMerge 和 Beyond Compare，但没有任何运气。有谁知道可以将这两个示例视为相同的差异工具（最好是免费的）？

前任。1：

前任。2：

提前致谢。

我需要逐字比较两个字符串。类似于 diff 的东西，但是对于文字，而不是对于线条。

就像在维基百科 http://en.wikipedia.org/w/index.php?title=Horapollo&action=historysubmit&diff=21895647&oldid=21893459

结果我想返回两个单词索引的两个数组，它们在两个字符串中是不同的。

.NET 是否有任何库/框架/独立方法可以做到这一点？

PS我想比较几千字节的文本

我想显示两个文本块之间的差异。而不是比较文本行或单个字符，我只想比较由指定字符分隔的单词（例如'\n'、''、'\t'）。我这样做的主要原因是，我将要比较的文本块通常没有很多换行符，而且字母比较可能很难理解。

我在 C# 中遇到了以下用于比较行和字符的 O(ND) 逻辑，但是对于如何修改它来比较单词我有点茫然。

此外，我想跟踪单词之间的分隔符并确保它们包含在差异中。因此，如果一个空格被硬返回所取代，我希望它作为一个差异出现。

我正在使用 Asp.Net (c#) 显示整个文本块，包括已删除的原始文本和添加的新文本（两者都将突出显示以表明它们已被删除/添加）。一个适用于这些技术的解决方案将不胜感激。

任何关于如何实现这一点的建议都值得赞赏。

有谁知道一个类似 diff 的工具，它可以向我显示两个文本文件之间的更改，但忽略空格中的更改，包括换行符？

这是一个例子：

我所做的只是删除一个单词并重新排列它，但是“diff -b”检测到每一行的更改（应该如此；我并不是说这是 diff 中的错误）。但是对于大型 LaTeX 文件，这是一个主要问题；长段换一个字，得到的 diff 基本没用。

顺便说一句，我知道这需要比通常的行原子差异更多的计算能力。我只对人为生成的小文件执行此操作，如果需要，我很乐意等待很长时间。

我有两段文字。我想在它们之间进行基于单词的差异（就像 unix 实用程序wdiff那样），但在输出中包含更多信息（我的意思是，添加/删除的单词开始的字符位置）。

我需要在 Java 中执行此操作，因此差异的简单输出（如wdiff）不适合我：我想操作表示差异的对象。