Philipps paper equivalent Blog

Innerhalb unseres Projektes ist die Notwendigkeit entstanden, XML-Dokumente, die etwas umfangreicher als die Standard-Java-Deskriptoren sind, auf Gleichheit hin zu untersuchen.
Folgende XML-Strings sind gegeben:

A)
<items>
    <item name="a">
        <value>1</value>
    </item>
    <item name="b">
        <value>2</value>
    </item>
    <item name="c">
        <value>3</value>
    </item>
</items>

B)
<items>
    <item name="a">
        <value>1</value>
    </item>
    <item name="c">
        <value>3</value>
    </item>
    <item name="b">
        <value>2</value>
    </item>
</items>

Diese Untersuchung soll eine Aussagen über:
- Gleichheit: (2 Dateien enthalten das gleiche XML-Modell - sowohl in der gleichen Reihenfolgen A) , als auch in einer anderen Reihenfolge B) ).
- Veränderungen: welche Stellen sind verändert worden.

Während Forderung zwei sich noch mit einem einfachen String-Vergleich lösen lässt, ist Forderung eins nur durch das erkennen eines Modells lösbar.
Hierbei ist es notwendig, die einzelnen Knoten zu erkennen.
Zudem sind die zu-untersuchenden XML-Dateien > 5 MBb sodass viele - professionelle XML-Tools hier streiken müssen und mit Speicherfehlern aufgeben.

Der Ansatz der hier vorgestellt wird, setzt sich aus drei Stufen zusammen:

1. SAX-basiertes Parsen der Datei und einlesen in eine Datenbank (aus Performance-Gründen wird hier H2 als inMemory Datenbank genutzt).
   


2. Um schnelle Vergleiche zu ermöglichen wird ein Modell benutzt, welches u.a. auch in ZFS angewendet wird: Erkennen von Veränderungen anhand von Prüfsummen.
   Was bei ZFS dazu benutzt wird, um Änderungen innerhalb des Dateisystems zu erkennen, soll hier dazu dienen, Unterschieder zwischen zwei XML-Modellen schnell und zuverlässig zu erkennen.
   Hierzu wird für jeden Knoten eine Prüfsumme berechnet. Diese leitet sich jeweils aus den Prüfsummen seiner Kindsknoten, dem Inhalt seiner Attribute und dem Wert des Knotens ab.
   Momentan wird über diesen Gesamt-String ein SHA1-Hash gebildet. Eine weitere Prüfsumme wird benötigt, um den Knoten innerhalb des Modells zu lokalisieren (wir verwenden hier den XML-Path+Knotennummer):
   
   
   
   1. 
      <--                   Hash des Pfades                   -->
      3a52ce780950d4d969792a2559cd519d7ee8c727 
      ./items/item/value           
      
   
   
   2. 
      <--             Hash des Knotens item              -->
      481e6ff69a8402231a3b9c6e46a7fef4f09adbb3
      hash von: "item", attribute "name=b", hash von "value"
      


3. Da sowohl eine Aussage über Unterschied im sortierten Zustand - die Reihenfolge der (Kinder-)Knoten ist wichtig - als auch im unsortierten Zustand (Die Reihenfolge der Kinder-)Knoten ist egal,
   wird vor dem Berechnen des Hashes des Kindes eines Knotens, die Kinder einmal unsortiert und einmal sortiert als Basis für den SHA1-Hash genommen.

Momentan ist das Datenmodell soweit vollständig, die Knotenwerden beim Parsen in die Datenbank eingelesen. Dieser Vorgang wird momentan noch hinsichtlicher Dauer und Speicherverbrauch optimiert. Auch eine aussagekräftige Fortschrittanzeige sollte eingebaut werden. Danach muss der Algorithmus zum Erkennen der unterschiedlichen Stellen implementiert werden.
Als letztes sollen diese Unterschiede in einer übersichtlichen und - für große Dokumente - gut navigierbaren GUI angezeigt werden.