Die Ähnlichkeitensuche gewinnt mit zunehmender Komplexit¨at der Dokumente an Bedeutung. Während existierende Ansätze den inhaltlichen Aspekt der Suche in den Fokus der Betrachtung setzten, wird die strukturelle Ähnlichkeit weitestgehend außen vor gelassen. Im Rahmen dieser Diplomarbeit wird ein einheitlicher Ansatz für die Ähnlichkeitensuche vorgestellt, welcher die strukturellen Aspekte der Zusammensetzung der komplexen Datentypen ebenfalls berücksichtigt und separat als strukturelle Ähnlichkeit ausweist. Die Berechnung der inhaltlichen Ähnlichkeit erlaubt die Erkennung ähnlicher Teilbäume innerhalb beliebiger komplexer Datentypen. Die Daten werden dem System im XML-Dokument- Format übergeben. Diese werden vom System so weit abstrahiert, dass keine Unterschiede aufgrund verschiedener stilistischer Möglichkeiten der Serialisierung von komplexen Datentypen in das XML-Dokument-Format Auswirkungen auf den inhaltlichen Vergleich nehmen können. Dies ermöglicht den Vergleich komplexer Datentypen hinsichtlich ihres Aufbaus und ihres Inhalts.
Auf einen Blick
- Entwicklung und Implementierung des Ähnlichkeitssuchsystems SimSearch
- Validierung anhand von Laufzeitschranken und Berechnungszwischenergebnissen
- Abgedruckter SSC-Algorithmus zum Vergleich von Zeichenketten
- 46 Quellen im Literaturverzeichnis
- 10 Abbildungen
Inhaltsverzeichnis
1 Einführung
2 Grundlagen
2.1 Eigenschaften komplexer Datentypen
2.1.1 Komplexe Datentypen und ihre primitiven Bestandteile
2.1.2 Das XML-Transport-Dokumentformat
2.1.3 Feste und lose Strukturen
2.1.4 Das RDF-System zur Beschreibung von Ressourcen
2.2 Distanz-Berechnungsvorschriften in Räumen
2.2.1 Suchräume
2.2.2 Edit-Distanzen
2.2.3 Werte-Distanzen
2.2.4 PlusMinus-Ähnlichkeit
2.2.5 Bildung von Teilmengen
2.3 Logische Kombination der Distanzwerte
2.3.1 Aussagenlogik
2.3.2 Prädikatenlogik
2.4 Abfragesprachen mit Datenstrukturen
2.4.1 Abfragesprachen
2.4.2 Datenstrukturen
2.4.3 Bekannte Ansätze auf Datenstrukturen
2.4.4 Ontologien
3 Problemstellung und Abgrenzung
3.1 Problemstellung
3.2 Existierende Ansätze
3.3 Abgrenzung
3.3.1 Baumsignaturen
3.3.2 Similarity Join Frameworks
3.3.3 Tamino & XXL Ontologie
3.3.4 Kernel-Funktionen
4 Lösungsansatz (Konzept)
4.1 Das SimSearch Framework
4.1.1 SimSearch CMD-Engine
4.1.2 Grafische Darstellung der Suchergebnisse
4.2 Strukturelle Ähnlichkeitssuche
4.2.1 Lineare-Baumsignatur (Herleitung)
4.2.2 Strukturelle Ähnlichkeitssuche (Berechnung)
4.3 Inhaltliche Ähnlichkeitssuche
4.3.1 Das abstrakte Datenschema (Herleitung)
4.3.2 Inhaltliche Ähnlichkeitssuche (Berechnung)
4.4 (Teil)Baum-Ähnlichkeitssuche
4.4.1 Bottom-Up Gleichheitssuche
4.4.2 Bottom-Up Ähnlichkeitssuche
5 Lösungsansatz (Validierung)
5.1 Externe Komponenten (Laufzeit)
5.2 Eigene Komponenten (Laufzeit & Validierung)
6 Zusammenfassung und Ausblick
6.1 Zusammenfassung
6.2 Ausblick
Zielsetzung und Themen
Die Arbeit untersucht, wie komplexe, hierarchisch aufgebaute Daten anhand ihrer Struktur und ihres Inhalts auf Ähnlichkeit verglichen werden können. Ziel ist der Entwurf und die Implementierung eines Verfahrens, das XML-Daten in ein einheitliches Modell überführt, strukturelle Ähnlichkeit gesondert ausweist und ähnliche Teilkomponenten auffindbar macht.
- Komplexe Datentypen, XML und ontologische Datenmodelle
- Distanzmaße und bestehende Verfahren der Ähnlichkeitssuche
- Lineare Baumsignaturen für den strukturellen Vergleich
- Inhaltlicher Vergleich von Attributen und Dokumenten
- Gleichheits- und Ähnlichkeitssuche in Teilbäumen
- Implementierung und Validierung des SimSearch Frameworks
Auszug aus dem Buch
Lineare-Baumsignatur (Herleitung)
Um eine beliebige hierarchisch aufgebaute Komponente in ihrer Struktur beschreiben zu können, müssen alle relevanten Informationen bezüglich ihres hierarchischen Zusammenbaus sowie der Art der Teilkomponenten in einer linearen Signatur untergebracht werden. Dieser Vorgang wird hier als Serialisierung bezeichnet und ähnelt in seiner Vorgehensweise auch der von den Programmiersprachen bekannten Serialisierung persistenter Objekte. Ferner muss die Signatur von Informationen befreit werden, die der zugrunde liegenden Baumstruktur innewohnen, diese jedoch in keiner Weise zusätzlich beschreiben und somit den Vergleich äquivalenter Baumstrukturen erschweren. Dabei ist speziell die Anordnung der Kinderkomponenten einer Komponente und somit der Komponenten einer Baumebene mit einem bestimmten Vaterknoten gemeint. Diese Anordnung unterliegt keiner bestimmten Gesetzmäßigkeit und kann völlig willkürlich vom Programmierer oder einer bestimmten Implementierung eines XML-Parsers vorgenommen werden. Um diese Anordnung für den Vergleich außen vor zu lassen, werden die Signaturelemente, welche die Kinderelemente eines Knotens symbolisieren, nach einem bestimmten und eindeutigen Muster sortiert. Dieser Sortiervorgang wird hier als Normalisierung bezeichnet.
Im Folgenden wird das Vorgehen an einem Beispieldatensatz veranschaulicht. Dabei handelt es sich um zwei CD-Kataloge. In beiden ist eine identische CD enthalten. Das obere Crop Circles Diagram veranschaulicht die Sicht auf das Datenmodell des zugrunde liegenden Ontologie-Kompositums, welches aus komplexen Komponenten und Attributen (auch Komponenten) besteht. Darunter wird eine Baumdarstellung gezeigt, welche eine Teilmenge der Attribute hervorgehoben darstellt.
Allen drei in der Abbildung dargestellten Datenansichten kann entnommen werden, dass die Anordnung der Komponenten einer Ebene mit gemeinsamer Vaterkomponente keine zusätzliche Information über die Struktur der Daten enthält. Es ist unerheblich, ob eine CD erst mit dem Titel und dann mit dem Künstler beschrieben wird oder diese Angaben in anderer Reihenfolge stattfinden. Somit ist die Anordnung der Attribute einer CD an keine Gesetzmäßigkeit gebunden, während die Durchnummerierung der CDs in der Baumdarstellung keinen Bestandteil des Datensatzes darstellt und auch sonst keine alphanumerische Reihenfolge impliziert. Die Nummerierung wird intern bei der Benennung konkreter Ausprägungen komplexer Komponenten vorgenommen und dient nur als Unterscheidungskriterium (UK) zwischen diesen untereinander sowie deren abstrakten Datentypen.
Zusammenfassung der Kapitel
1 Einführung: Das Kapitel erläutert den Bedarf an unscharfer Suche und nennt die Konstruktion von Automobilteilen als Anwendungsbereich. Es stellt den Aufbau der Arbeit vor.
2 Grundlagen: Behandelt werden komplexe Datentypen, XML, Distanzmaße, logische Verknüpfungen, Abfragesprachen, Datenstrukturen und Ontologien.
3 Problemstellung und Abgrenzung: Das Kapitel formuliert die Anforderungen an den Vergleich komplexer Daten und setzt sich mit Baumsignaturen, Ähnlichkeitsverbünden, Tamino, der XXL Ontologie und Kernel-Funktionen auseinander.
4 Lösungsansatz (Konzept): Vorgestellt werden das SimSearch Framework, die Bildung linearer Baumsignaturen sowie Verfahren für die strukturelle, inhaltliche und teilbaumbezogene Ähnlichkeitssuche.
5 Lösungsansatz (Validierung): Das Kapitel betrachtet Laufzeiten verwendeter Komponenten und prüft die eigenen Verfahren anhand von Berechnungsschritten und Beispieldatensätzen.
6 Zusammenfassung und Ausblick: Die Arbeit bündelt ihre entwickelten Konzepte und skizziert Erweiterungsmöglichkeiten, insbesondere für die semantische Ähnlichkeitssuche.
Schlüsselwörter
Ähnlichkeitssuche, komplexe Datentypen, strukturelle Ähnlichkeit, inhaltliche Ähnlichkeit, XML, Baumsignaturen, Ontologien, Distanzmaße, Teilbaumsuche, SimSearch, Datenmodell, Levenshtein-Distanz, Validierung
Häufig gestellte Fragen
Worum geht es in der Arbeit?
Die Arbeit entwickelt ein Verfahren, mit dem sich komplexe Daten hinsichtlich ihres Aufbaus und ihres Inhalts auf Ähnlichkeit untersuchen lassen.
Welche Themen stehen im Mittelpunkt?
Im Mittelpunkt stehen hierarchische Daten, Distanzberechnung, Baumsignaturen, ontologische Datenmodelle und die Suche nach ähnlichen Dokumenten und Teilbäumen.
Was ist das Ziel der Untersuchung?
Entwickelt werden soll ein einheitlicher Ansatz, der strukturelle und inhaltliche Ähnlichkeit unterscheidbar macht und auf komplexe XML-Daten anwendbar ist.
Welche wissenschaftliche Vorgehensweise wird verwendet?
Die Arbeit analysiert vorhandene Verfahren, entwirft und implementiert einen eigenen Ansatz und validiert ihn anhand von Laufzeitabschätzungen und Berechnungsbeispielen.
Was behandelt der Hauptteil?
Der Hauptteil erläutert das SimSearch Framework, die Erstellung und Auswertung von Baumsignaturen sowie Algorithmen zum Vergleich von Attributen, Dokumenten und Teilbäumen.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Zu den zentralen Begriffen gehören Ähnlichkeitssuche, XML, strukturelle und inhaltliche Ähnlichkeit, Baumsignaturen, Ontologie und Teilbaumsuche.
Welche Rolle spielen Baumsignaturen?
Sie überführen die hierarchische Struktur von XML-Daten in eine lineare Darstellung, die für den strukturellen Vergleich herangezogen wird.
Wie wird die Suche nach ähnlichen Teilbäumen aufgebaut?
Der vorgestellte Ansatz beginnt bei Attributen beziehungsweise unteren Komponenten und nutzt deren Vergleichsergebnisse beim schrittweisen Aufstieg zu übergeordneten Komponenten.
Welchen Bezug hat die Arbeit zur Automobilfertigung?
Sie nennt Konstruktions- und Angebotsdaten als Anwendungsbereich und erläutert den Attributvergleich unter anderem anhand von Produktstrukturen aus einem Konstruktionssystem.
Welche Bedeutung hat GermaNet für den Ansatz?
Eine Schnittstelle zu GermaNet ist als Grundlage für eine mögliche semantische Erweiterung vorgesehen; innerhalb der beschriebenen Ähnlichkeitssuche wird sie noch nicht verwendet.
- Arbeit zitieren
- Maciej Niemczyk (Autor:in), 2010, Entwurf und Implementierung eines Verfahrens zur Analyse komplexer Daten insbesondere auf strukturelle Ähnlichkeit, München, GRIN Verlag, https://www.grin.com/document/167375
