This sounds all very logical. I think option 5 is the best way to go at
this point. However, I am not sure how to go about doing such a
comparison. My situation is as follows: My user selects a subset of the
original XML file. After this action I need to compare the selection of
the user to the original.

Once I find the location of the selection
inside the original I have to surround this selection with a new tag,
say "<selection>", and "</selection>". I have placed an example of
text online at http://www.jborsje.nl/example.txt, so you can see what I mean.

One way I can think of is iterating over all of the elements of the
original, each time calling the "deep-equal()" function, but I do not
know if that is the best approach.

Cheers,
-- Abel Braaksma