Building an HTML Diff/Patch Algorithm
Question: A description of what I'm going to accomplish:

  * Input 2 (N is not essential) HTML documents. 
  * Standardize the HTML format
  * Diff the two documents -- external styles are not important but anything inline to the document will be included. 
  * Determine delta at the HTML Block Element level. 

Expanding the last point:

Imagine two pages of the same site that both share a sidebar with what was
probably a common ancestor that has been copy/pasted. Each page has some minor
changes to the sidebar. The diff will reveal these changes, then I can "walk
up" the DOM to find the first common block element shared by them, or just
default to `<body>`. In this case, I'd like to walk it up and find that, oh,
they share a common `<div id="sidebar">`.

I'm familiar with DaisyDiff and the application is similar -- in the CMS
world.

I've also begun playing with the google diff-patch library.

I wanted to give ask this kind of non-specific question to hopefully solicit
any advise or guidance that anybody thinks could be helpful. Currently if you
put a gun to my head and said "CODE IT" I'd rewrite DaisyDiff in Python and
add-in this block-level logic. But I thought maybe there's a better way and
the answers to [Anyone have a diff algorithm for rendered
HTML?](http://stackoverflow.com/questions/31722/anyone-have-a-diff-algorithm-
for-rendered-html) made me feel warm and fuzzy.


Answer: If you were going to start from scratch, a useful search term would be "tree
diff".

There's a pretty awesome blog post [here](http://useless-
factor.blogspot.com/2008/01/matching-diffing-and-merging-xml.html), although I
just found it by googling "daisydiff python" so I bet you've already seen it.
Besides all the interesting theoretical stuff, he mentions the existence of
[Logilab's `xmldiff`](http://www.logilab.org/859), an open-source XML differ
written in Python. That might be a decent starting point — maybe less correct
than trying to wrap or reimplement DaisyDiff, but probably easier to get up
and running quickly.

There's also [html-tree-diff](http://pypi.python.org/pypi/html-tree-
diff/0.1.2) on pypi, which I found via this Quora link:
<http://www.quora.com/Is-there-any-good-Python-implementation-of-a-tree-diff-
algorithm>

There's some theoretical stuff about tree diffing at [efficient diff algorithm
for trees and Levenshtein
distance](http://cstheory.stackexchange.com/questions/10205/efficient-diff-
algorithm-for-trees-and-levenshtein-distance) on cstheory.stackexchange.

BTW, just to clarify, you _are_ talking about diffing two DOM trees, but not
necessarily rendering the diff/merge back into any particular HTML, right?
**(EDIT: Right.)** A lot of the similarly-worded questions on here are really
asking "how can I color deleted lines red and added lines green" or "how can I
make matching paragraphs line up visually", skipping right over the
theoretical hard part of "how do I diff two DOM trees in the first place" and
the practical hard part of "how do I parse possibly malformed HTML into a DOM
tree even before that". :)

