Создание алгоритма Diff/Patch для HTML

Описание того, что я собираюсь выполнить:

Ввод 2 (N не является существенным) HTML-документов.
Стандартизировать формат HTML
Разверните два документа - внешние стили не важны, но все, что включено в документ, будет включено.
Определить дельта на уровне элемента HTML-элемента.

Развертывание последней точки:

Представьте себе две страницы одного и того же сайта, в которых есть общая панель с тем, что было, вероятно, обычным предком, который был скопирован/вставлен. На каждой странице есть некоторые незначительные изменения на боковой панели. Разница покажет эти изменения, затем я могу "подойти" к DOM, чтобы найти первый общий элемент блока, который им поделили, или просто по умолчанию <body>. В этом случае, я бы хотел подойти и найти это, о, у них есть общий <div id="sidebar">.

Я знаком с DaisyDiff, и приложение похоже - в мире CMS.

Я также начал играть с библиотекой diff-patch google.

Я хотел бы задать такой неспецифический вопрос, чтобы надеяться, что вы попросите совета или рекомендации, которые, по мнению любого, могут быть полезны. В настоящее время, если вы положили пистолет в голову и сказали "CODE IT", я бы переписал DaisyDiff в Python и добавил эту блочную логику. Но я подумал, может быть, есть лучший способ и ответы на У кого-нибудь есть алгоритм diff для визуализированного HTML? заставляло меня чувствовать себя теплым и нечетким.

Ответ 1

Если вы собираетесь начинать с нуля, полезным поисковым термином будет "tree diff".

Там довольно удивительное сообщение в блоге здесь, хотя я только что нашел его в googling "daisydiff python", поэтому, я уверен, вы уже видели Это. Помимо всего интересного теоретического материала, он упоминает о существовании Logilab xmldiff, причем XML с открытым исходным кодом отличается от Python. Это может быть достойной отправной точкой - может быть, менее корректно, чем пытаться обернуть или переопределить DaisyDiff, но, вероятно, легче быстро встать и работать.

Там также html-tree-diff на pypi, который я нашел через эту ссылку Quora: http://www.quora.com/Is-there-any-good-Python-implementation-of-a-tree-diff-algorithm

Там некоторые теоретические материалы о дереве, отличные от эффективного алгоритма сравнения деревьев и расстояния Левенштейна от cstheory.stackexchange.

Кстати, просто для того, чтобы уточнить, вы говорите о том, чтобы различать два дерева DOM, но не обязательно визуализировать diff/merge обратно в какой-либо конкретный HTML, правильно? (EDIT: Right.). Многие аналогичные вопросы здесь действительно спрашивают: "Как я могу покрасить удаленные строки красным цветом и добавить зеленые линии" или "как я могу сделать соответствующие параграфы визуально", пропуская прямо над теоретической трудной частью "как мне отличить два дерева DOM в первую очередь" и практическую трудную часть "как я могу проанализировать, возможно, искаженный HTML-код в дереве DOM еще до этого".:)

Ответ 2

Я знаю, что эти вопросы связаны с python, но вы можете взглянуть на 3DM-XML 3-way Merging and Differencing Tool (реализация по умолчанию в java), но вот фактическая статья, описывающая используемый алгоритм http://www.cs.hut.fi/~ctl/3dm/thesis.pdf, и вот ссылка на сайт.

Недостатком этого является то, что вам нужно очистить документ и уметь его обрабатывать как XML.

Ответ 3

Вы можете начать с beautifulsoup для анализа обоих документов.

Тогда у вас есть выбор:

используйте prettify, чтобы отобразить оба документа как более или менее стандартизированные HTML и diff те.
сравните деревья синтаксического анализа.

Последний позволяет вам, например, отбрасывать элементы, которые влияют только на презентацию, а не на контент. Первый, вероятно, проще.