CVSM Bibliography, Entry [ Tr2007DA ]


Treude, Christoph: Einsatz multidimensionaler Suchstrukturen zur Optimierung der Bestimmung von Dokumentdifferenzen; Diplomarbeit, Fachgruppe Praktische Informatik, Universität Siegen; 2007
Deskriptoren: CVSM, SiDiff, PI, model:difference

Abstract: Durch den Trend zu modellbasierter Entwicklung hat die Bedeutung von Differenzwerkzeugen für Modelldokumente stark zugenommen. Differenzen sind besonders zwischen unterschiedlichen Versionen eines Dokuments und bei Beteiligung mehrerer Personen an der Entwicklung eines Dokuments von Interesse. Die Berechnung von Differenzen zwischen nicht-textuellen Dokumenten gestaltet sich deutlich komplexer als zwischen reinen Textdokumenten. Dabei werden Modelldokumente meist als getypte Graphen interpretiert, in denen die einzelnen Elemente der Dokumente durch Knoten repräsentiert werden. Im Zuge der Differenzberechnung werden alle Elemente der zu vergleichenden Dokumente paarweise und gruppiert nach ihren Typen verglichen. Um die daraus resultierende quadratische Laufzeit, die vor allem für größere Dokumente inakzeptabel ist, zu verringern, wird in dieser Arbeit mit dem S3V Baum eine hauptspeicherbasierte, hochdimensionale und balancierte Datenstruktur zur Verwaltung von Dokumentelementen vorgestellt, die ähnliche Elemente benachbart anordnet. Somit müssen nicht alle Elemente betrachtet werden, um zu einem gegebenen Element die Menge der ähnlichen Elemente in anderen Dokumenten zu finden. Da der S3V Baum numerische Vektoren verwaltet, werden weiterhin mit lexikalischen und metrischen Indizes zwei Mechanismen dargestellt, mit denen Dokumentelemente auf Vektoren abgebildet werden können. Metrische Indizes basieren auf dem Konzept von Software-Metriken und bilden Eigenschaften der Elemente auf Zahlen ab. Das Ziel lexikalischer Indizes ist die Erfassung von Namensähnlichkeiten durch den Einsatz von Namen bzw. Namensteilen als Vektorindizes. Für die Integration der Datenstruktur in die Differenzberechnung ergeben sich mehrere Alternativen, die in dieser Arbeit aufgezeigt werden. Die abschließende Evaluierung des Ansatzes vor allem mit UML-Klassendiagrammen hat ergeben, dass die Laufzeit für große Dokumente teilweise um einen Faktor von bis zu 50 reduziert werden kann