可调整的差异算法

3
我希望找到一种比典型算法更为复杂的字符串差异查找算法,可以通过某些参数进行“调整”,以平衡“最大化相同字符数”与“最大化跨度长度”与“尽可能保持整个单词完整”等因素。
最终,我希望能够使结果尽可能地易于人类阅读。例如,如果一个长句子被替换成了一个全新的句子,它与原始句子唯一共同的只有按顺序排列的单词“the”、“and”和“a”,我可能希望将其视为整个句子已更改,而不仅仅是更改了4个特定跨度,就像一个合理的人所看到的那样。
这样的算法是否存在?虽然我正在使用javascript/node.js,但任何语言的算法都将有所帮助。
实际上,我认为使用蒙特卡罗方法或类似方法的算法也可以,如果其结果更好的话。计算时间不是问题(在合理范围内),确定性也不是问题。
注意:虽然这超出了我的要求范围,但我还想提出一件事情:如果它能识别无序的更改……例如,如果有人更改了两段落的顺序,同时保持它们完全相同,如果它能将其识别为简单的移动,而不是一个减法和一个无关的加法,那就太棒了。

1
你是在比较特定的输入,比如(编程)源代码,还是只是自由/纯文本?如果你正在比较某种明确定义的(编程)语言,也许你可以比较它们的AST而不是“diff-like”方法。 - Bart Kiers
我想要处理这段文本。有时候它可能是源代码,但有时候不是。你所描述的方法很有趣,但并不符合我这个项目的需求。 - rob
很遗憾,这个想法不是我的,我必须承认。我从一个名为Google Tech Talk的视频中得到了灵感,其中一个来自SO的用户Ira Baxter提出了这个想法。 - Bart Kiers
+1 我也对这样的东西很感兴趣。 - Tauren
2个回答

1

我在使用diff_match_patch时运气不错。有一些很好的选项可以调整它以提高可读性。


谢谢,这正是我所需要的。实际上,在你发帖之前,我通过查看右侧的“相关”答案找到了它 :) Google有时真的很棒...他们用7种语言提供了这个! - rob

0

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接