构建一个HTML差异/补丁算法

18

我要完成的任务描述:

  • 输入两个(N不是必需的)HTML文档。
  • 标准化HTML格式。
  • 比较这两个文档 -- 外部样式不重要,但文档内联任何内容都将包括在内。
  • 确定HTML块元素级别的差异。

扩展上一个点:

想象一下同一站点的两个页面,它们都有一个侧边栏,这个侧边栏可能是一个被复制/粘贴的共同祖先。每个页面对侧边栏进行了一些微小的更改。比较将揭示这些更改,然后可以“向上走”DOM以找到它们共有的第一个块级元素,或者只是默认为<body>。在这种情况下,我想向上走并发现它们共享一个常见的<div id="sidebar">

我熟悉DaisyDiff和应用程序类似--在CMS世界中。

我也开始尝试使用google diff-patch库。

我想提出这种非特定问题,希望能够征求任何人认为可能有帮助的建议或指导。目前,如果你拿枪指着我的脑袋说“写代码”,我会重新用Python编写DaisyDiff并添加这个块级逻辑。但我想也许有更好的方法,Anyone have a diff algorithm for rendered HTML?的答案让我感到温暖和舒适。


1
相关链接:https://dev59.com/rHI-5IYBdhLWcg3w-96b。 - Juho Vepsäläinen
我不确定你的确切应用,但像http://www.readability.com/这样的项目使用DOM排名算法来提取相关内容。如果您只想在页面核心上进行差异比较,那么类似的东西可能是有意义的。 - Pratik Mandrekar
很想听一下关于这个项目的最新进展;你是否找到了你要寻找的内容,是否计划开源其中的任何部分 :) - onassar
在这里对许多库进行了概述:http://web.onassar.com/blog/2012/11/21/htmldiff-software-discoveries/ - onassar
3个回答

9
如果你从头开始,一个有用的搜索术语是“树差异”(tree diff)。
这里有一篇非常棒的博客文章链接,不过我只是通过谷歌搜索“daisydiff python”找到它的,所以我猜你可能已经看过了。除了所有有趣的理论知识外,他还提到了 Logilab's xmldiff 的存在,这是一个用Python编写的开源XML区分器。那可能是一个不错的起点——也许比尝试包装或重新实现DaisyDiff更少正确,但可能更容易快速上手。
此外,还有在PyPI上的html-tree-diff,我是通过这个Quora链接发现的:链接 有一些关于树差异的理论内容在cstheory.stackexchange上的efficient diff algorithm for trees and Levenshtein distance
顺便说一句,只是为了澄清,你确实正在讨论比较两个DOM树,但不一定要将差异/合并呈现回任何特定的HTML,对吗?(编辑:对的。)这里的很多类似问法真正想问的是“如何将删除的行变成红色,添加的行变成绿色”或者“如何使匹配段落在视觉上对齐”,跳过了“首先我如何比较两个DOM树”的理论难点和“即使在那之前我如何解析可能格式不正确的HTML成一个DOM树”的实际难点。 :)

没错 - 这个领域有很多人想要像你描述的那样在HTML中呈现差异。但我并不关心这个,我根本不会呈现差异,而是使用输出块元素增量来驱动更强大的页面和同一页面不同版本之间差异的可视化。感谢您的建议,这与我以前构建的任何东西都不同,我想尝试确保我没有过度思考或忽略任何明显的问题。 - Shane H

1

我知道这个问题与Python有关,但你可以看一下3DM - XML三路合并和差异化工具(Java的默认实现),但这是描述所使用算法的实际论文http://www.cs.hut.fi/~ctl/3dm/thesis.pdf,这是网站的链接。

缺点是你必须清理文档并能够将其解析为XML。


1

您可以使用beautifulsoup来解析两个文档。

然后您有一个选择:

  • 使用prettify将两个文档呈现为更或多或少标准化的HTML,并diff这些文档。
  • 比较解析树

后者允许您丢弃仅影响演示而不是内容的元素。前者可能更容易。


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