[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: xml diff?

• From: Pavel Velikhov <pvelikho@c...>
• To: mda@d..., xml-dev@i...
• Date: Mon, 21 Dec 1998 16:54:33 -0800 (PST)

Mark D. Anderson wrote:
> 
> Suppose I want the "diff" between two xml files.
> 
> I can imagine a few approaches:

> - graph-theoretic:
> surely there must be some CS work on algorithms for finding
> the least cost path between two trees, expressed as a sequence
> of operations? the simplest is with just the operations of
> add/delete of subtrees, but move and copy are interesting too.
> 
> -mda

Here is a great paper on edit distance between trees (includes rather fancy edit commands, the result in an NP-complete problem however. But
you can choose any subset that seems useful and efficient):

S. Chawathe, H. Garcia-Molina "Meaningful Change Detection in Structured Data", SIGMOD 1997, http://www-db.stanford.edu/pub/papers/bbdiff.ps 

Pavel

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@i...
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@i... the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@i... the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@i...)

• Prev by Date: NumberFormatException in Parser()
• Next by Date: Re: xml diff?
• Previous by thread: Re: xml diff?
• Next by thread: Re: xml diff?
• Index(es):
  • Date
  • Thread