Entwurf und Implementierung eines Verfahrens Thema:

Maciej Niemczyk eingereicht von:

19. Juli 2010 eingereicht am:

Abstrakt

Die ¨ Ahnlichkeitensuche gewinnt mit zunehmender Komplexit¨ at der Dokumente an Bedeutung. W¨ ahrend existierende Ans¨ atze den inhaltlichen Aspekt der Suche in den Fokus der Betrachtung setzten, wird die strukturelle ¨ Ahnlichkeit weitestgehend außen vor gelassen.

Im Rahmen dieser Diplomarbeit wird ein einheitlicher Ansatz f¨ ur die ¨ Ahnlichkeitensuche vorgestellt, welcher die strukturellen Aspekte der Zusammensetzung der komplexen Datentypen ebenfalls ber¨ ucksichtigt und separat als strukturelle ¨ Ahnlichkeit ausweist. Die Berechnung der inhaltlichen ¨ Ahnlichkeit erlaubt die Erkennung ¨ ahnlicher Teilb¨ aume innerhalb beliebiger komplexer Datentypen. Die Daten werden dem System im XML-Dokument-Format ¨ ubergeben. Diese werden vom System so weit abstrahiert, dass keine Unterschiede aufgrund verschiedener stilistischer M¨ oglichkeiten der Serialisierung von komplexen Datentypen in das XML-Dokument-Format Auswirkungen auf den inhaltlichen Vergleich nehmen k¨ onnen. Dies erm¨ oglicht den Vergleich komplexer Datentypen hinsicht- lich ihres Aufbaus und ihres Inhalts.

Inhaltsverzeichnis

1  Einf uhrung  1

2  Grundlagen  3

2.1  Eigenschaften komplexer Datentypen  3

2.1.1  Komplexe Datentypen und ihre primitiven Bestandteile  3

2.1.2  Das XML-Transport-Dokumentformat  4

2.1.3  Feste und lose Strukturen  5

2.1.4  Das RDF-System zur Beschreibung von Ressourcen  6

2.2  Distanz-Berechnungsvorschriften in R aumen  7

2.2.1  Suchr aume  7

2.2.2  Edit-Distanzen  12

2.2.3  Werte-Distanzen  16

2.2.4  PlusMinus-  

Ahnlichkeit   22

2.2.5  Bildung von Teilmengen  23

2.3  Logische Kombination der Distanzwerte  26

2.3.1  Aussagenlogik  26

2.3.2  Pr adikatenlogik  27

2.4  Abfragesprachen mit Datenstrukturen  28

2.4.1  Abfragesprachen  28

2.4.2  Datenstrukturen  30

2.4.3  Bekannte Ans atze auf Datenstrukturen  30

2.4.4  Ontologien  34

i

ii

INHALTSVERZEICHNIS

3  Problemstellung und Abgrenzung  35

3.1  Problemstellung  35

3.2  Existierende Ans atze  36

3.3  Abgrenzung  37

3.3.1  Baumsignaturen  37

3.3.2  Similarity Join Frameworks  39

3.3.3  Tamino XXL Ontologie  43

3.3.4  Kernel-Funktionen  46

4  L osungsansatz (Konzept)  49

4.1  Das SimSearch Framework  50

4.1.1  SimSearch CMD-Engine  51

4.1.2  Grafische Darstellung der Suchergebnisse  54

4.2  Strukturelle  

Ahnlichkeitssuche   55

4.2.1  Lineare-Baumsignatur (Herleitung)  55

4.2.2  Strukturelle  

Ahnlichkeitssuche  (Berechnung)  64

4.3  Inhaltliche  

Ahnlichkeitssuche   69

4.3.1  Das abstrakte Datenschema (Herleitung)  71

4.3.2  Inhaltliche  

Ahnlichkeitssuche  (Berechnung)  72

4.4  (Teil)Baum-  

Ahnlichkeitssuche   76

4.4.1  Bottom-Up Gleichheitssuche  78

4.4.2  Bottom-Up  

Ahnlichkeitssuche   84

5  L osungsansatz (Validierung)  97

5.1  Externe Komponenten (Laufzeit)  98

5.2  Eigene Komponenten (Laufzeit Validierung)  99

6  Zusammenfassung und Ausblick  107

6.1  Zusammenfassung  107

6.2  Ausblick  108

Stichwortverzeichnis   115

Literaturverzeichnis   121

Kapitel 1

Einf ¨ uhrung

Auf ¨ Ahnlichkeit, nicht auf Gleichheit ist alles Klassifizieren oder die Sprache aufgebaut,

”

auf ¨ Ahnlichkeit, nicht auf Gleichheit all unser Urteilen oder die Anwendung der Sprache. Alle Logik aber, auch die Algebra der Logik, geht von dem mathematischen Begriff der Gleichheit aus und ist darum eine gef¨ ahrliche Wissenschaft. Um nicht zu weit abzuschweifen, sei nur kurz erw¨ ahnt, daß auch der Begriff oder das Gef¨ uhl der Kontinuit¨ at aus dem Gef¨ uhle der ¨ Ahnlichkeit allein entsteht.“ - Fritz Mauthner, 1906

Immer wieder wird man redensartlich daran erinnert, keine ¨ Apfel mit Birnen zu vergleichen, und dennoch wird dieser Vergleich ¨ ofter als vielleicht angenommen gezogen. Ein derartiger Vergleich wird t¨ aglich sowohl bei der Wahl substitutiver G¨ uter als auch bei der Nutzung von Suchmaschinen und der dort angezeigten Ergebnisse angewendet. Im Allgemeinen wird er seit jeher bei der Klassifizierung von Gegenst¨ anden des reellen Lebens gezogen, indem durch eine Teilmenge gemeinsamer Eigenschaften irgendwelche Gegenst¨ ande zu einer Gruppe von Elementen einer bestimmten Klasse zusammengefasst werden. Durch Generalisierung werden diese Mengen anschließend in gr¨ oßere und durch Spezifizierung in kleinere Mengen unterteilt.

Herk¨ ommliche Suchalgorithmen setzen jedoch die Kenntnis der Eigenschaften voraus. Sie bieten lediglich die M¨ oglichkeit, diejenigen Elemente als Suchergebnis zu identifizieren, welche sowohl den innerhalb der Suchanfrage definierten Kriterien gen¨ ugen als auch ¨ uber

eine einheitliche Menge von Eigenschaften verf¨ ugen. Dabei werden meist harte Grenzen gezogen, welche bei Nichterf¨ ullung den Ausschluss aus der Ergebnismenge bedeuten. Genau das disqualifiziert bestehende Suchalgorithmen in vielen Anwendungsf¨ allen. Einige dieser F¨ alle haben die hier vorliegende Arbeit motiviert. Zum Beispiel im Bereich der Konstruktion von Automobilteilen besteht gleich an mehreren Stellen Bedarf

1

EINF ¨ 2 1.0 UHRUNG

f¨ ur unscharfe Suchalgorithmen. Angefangen bei der Angebotserstellung, welche an einen Kostenvoranschlag gekoppelt ist, bis hin zur Standardisierung von Bauteilen lassen sich erhebliche Zeit- und Kostenersparnisse durch das automatisierte Auffinden ¨ ahnlicher Auftr¨ age oder Produkte erzielen. In [Ent06, S. 16] wird der Angebotsprozess am Beispiel eines Automobilzulieferers ausf¨ uhrlich geschildert. In jener Arbeit wird besonders auf das hohe Einsparpotential innerhalb der Konzept- und Designphase hingewiesen. Dort entstehen Kosten in Verbindung mit Kostenvoranschl¨ agen sowie prototypischen L¨ osungsans¨ atzen und lassen sich durch die Suche ¨ ahnlicher Auftr¨ age und Konstruktionsdaten minimieren. Sowohl Auftr¨ age als auch Produkte samt Konstruktionsdaten werden innerhalb der EDV durch komplexe Daten abgebildet und sollen als solche vergleichbar gemacht werden. Dies ist eine gr¨ oßere Herausforderung als der Vergleich primitiver Datentypen, weil die Anzahl der Attribute und die Gr¨ oße ihrer Wertebereiche nicht von vornherein bekannt sind.

Diese Arbeit gliedert sich wie folgt: Als erstes wird der Unterschied zwischen primitiven und komplexen Daten und der daraus entstehenden Komplexit¨ at erl¨ autert. Anschließend werden die mathematischen und algorithmischen Grundlagen zur ¨ Ahnlichkeits- bzw. Distanzmessung dargestellt. Diese erlauben es, sich dem abstrakten Begriff der ¨ Ahnlichkeit

wissenschaftlich zu n¨ ahern und diesen programmatisch erfassbar zu machen. Weil metrische ¨ Ahnlichkeits- bzw. Distanz-Berechnungsverfahren sowie Abfragesprachen mit Datenstrukturen eher den Grundlagen als der Abgrenzung zuzurechnen sind, aber auch zum Teil komplette ¨ Ahnlichkeits-Messverfahren enthalten, sind die erl¨ auternden Ausf¨ uhrungen durch teilweise Vorwegnahme der Abgrenzung entsprechend umfangreich. Anschließend folgt eine Beschreibung und Auseinandersetzung mit der Problemstellung. Dabei werden vorhandene Algorithmen zur ¨ Ahnlichkeitsmessung vorgestellt sowie deren

Anwendbarkeit gepr¨ uft. Danach findet eine Unterteilung der Problemstellung in inhaltliche und strukturelle ¨ Ahnlichkeit statt. Diese Unterteilung bedarf unterschiedlicher Herangehensweisen und schafft Raum f¨ ur die Schwerpunktsetzung auf die strukturelle ¨ Ahnlichkeitsanalyse. Im darauf folgenden Kapitel 4 wird ein eigener Ansatz zu struktureller und inhaltlicher sowie der (Teil)Baum- ¨ Ahnlichkeitssuche vorgestellt. Dieser wird in Kapi-

tel 5 validiert. Zum Schluss folgt eine Zusammenfassung der erzielten Ergebnisse und der Ausblick auf die semantische Erwartbarkeit.

Kapitel 2

Grundlagen

2.1 Eigenschaften komplexer Datentypen

2.1.1 Komplexe Datentypen und ihre primitiven Bestandteile

Alle guten Worte dieser Welt bestehen doch nur aus Buchstaben.“ - Tse-Tang

”

Komplexe Daten und komplexe Datentypen bezeichnet man als solche vorwiegend zur Abgrenzung von primitiven Datentypen. W¨ ahrend der Begriff der Komplexit¨ at die Eigenschaft eines Systems oder Modells umfasst, welches sein Gesamtverhalten als nicht beschreibbar definiert, selbst wenn alle Informationen ¨ uber seine Einzelkomponenten und

Wechselwirkungen bekannt sind [H¨ ar08], sind dagegen komplexe Datentypen durch die Bekanntheit aller Einzelkomponenten hinreichend beschrieben. Der Begriff der Komplexit¨ at steht hier somit nur im Kontrast zum Begriff der Einfachheit bzw. der Primitivit¨ at, aus welchem sich die Bezeichnung der primitiven Datentypen ableitet.

W¨ ahrend primitive Datentypen nur einen einzigen bin¨ aren Wert aufweisen, welcher

entweder den Flags ¹ , Zahlen oder Zeichen oder Zeichenketten zugeordnet werden kann, k¨ onnen komplexe Datentypen, ¨ ahnlich den komplexen Zahlen, aus mehreren Werten bestehen. Eine genaue Unterteilung verschiedener Kategorien sowie deren Klassifizierung und Gruppierung ist in der folgenden Seminararbeit ausgef¨ uhrt worden: ” Analyse von

komplexen Produkt- und Prozess-Datentypen zur Unterst¨ utzung wissensintensiver Prozesse“ [Nie09, S.11].

¹ Wahrheitswerte, eindeutige Zuordnungsparameter [Nie09].

3

4 2.1 GRUNDLAGEN

In der hier vorliegenden Arbeit steht der hierarchische Aufbau komplexer Daten und Datentypen, welcher als Baum betrachtet ausschließlich primitive Blattknoten aufweist, im Vordergrund. Diese k¨ onnen wiederum zu komplexen Elementknoten zusammengef¨ ugt werden. Diese Art des Aufbaus und der Serialisierung komplexer Objekte entspricht auch dem Ansatz des allgemeinen XML-Transport-Dokumentformats, auf welches im Folgenden n¨ aher eingegangen wird, weil es als Grundlage zum Vergleich komplexer Daten innerhalb dieser Arbeit dient.

2.1.2 Das XML-Transport-Dokumentformat

XML ist eine erweiterbare Auszeichnungssprache (eXtensible Markup Language) und dient dem plattform- und implementationsunabh¨ angigen Austausch von Dokumenten. Sowohl wegen der F¨ ahigkeit, verschiedenste Quellen zu integrieren, als auch wegen der maschinellen und menschlichen Lesbarkeit wird XML allgemein als der Standard der Zukunft angesehen [Guh02]. XML-Dokumente k¨ onnen in der Regel den h¨ ochsten Komplexit¨ atsgrad

aufweisen und sind auch nur an sehr wenige strukturelle Bedingungen gekn¨ upft. ² Diese Eigenschaft macht sie f¨ ur strukturelle Untersuchungen besonders interessant, da gr¨ obere strukturelle Unterschiede feststellbar sind, w¨ ahrend bei vielen strukturellen Bedingungen diese Unterschiede nur noch sehr geringf¨ ugig ausfallen. Die strukturellen Bedingungen seitens XML beschr¨ anken sich lediglich auf das Hinterlegen der Daten in einer Baumstruktur mit ausgezeichnetem Wurzelelement. Inhaltlich werden die Datens¨ atze bei XML als Entit¨ aten bezeichnet und als eine Zeichenkette, umgeben von Auszeichnungselementen (Markup), gespeichert. Dieser Ansatz erlaubt beliebige Kombinationen primitiver Datentypen, weil sich diese immer als Zeichenketten repr¨ asentieren lassen. Außerdem wird dadurch die Lesbarkeit der XML-Dokumente f¨ ur Menschen sichergestellt. Die Auszeichnungselemente dienen einerseits der Zuordnung der Stringrepr¨ asentation der Entit¨ aten zu frei w¨ ahlbaren Klassen, andererseits k¨ onnen die Entit¨ aten ebenfalls auf dieser Ebene mit weiteren Attributen versehen werden. Da, wo den frei gew¨ ahlten Auszeichnungs-Tags bestimmte primitive Datentypen eindeutig zugeordnet werden k¨ onnen, kann diese Zuordnung innerhalb einer Dokumenttypdefinition-Datei (DTD) zwecks Validierung vorgenommen werden. Die DTD tr¨ agt somit einen semantischen Mehrwert zur reinen XML-Datei bei und erlaubt uber die Zeichenketten-Repr¨ asentation weiterreichende Vergleiche. ¨

² Siehe Kapitel ” Klassifizierung von Datentypen“ [Nie09, S. 10].

2.1 5 EIGENSCHAFTEN KOMPLEXER DATENTYPEN

Weil Attribute auch in Form einwertiger Elemente gespeichert werden k¨ onnen, wird an dieser Stelle eine Unterscheidung zwischen der Daten- und der Metaebene vorgenommen, welche eher stilistischer als struktureller oder inhaltlicher Natur ist. Da diese Unterscheidung somit f¨ ur den strukturellen und inhaltlichen Vergleich nicht von Bedeutung ist, stellt eine vereinheitlichte Behandlung von Attributen eine Voraussetzung f¨ ur das innerhalb dieser Arbeit vorgestellte SimSearch Framework dar. Da weitergehende XML-Kenntnisse im Rahmen dieser Arbeit nicht zwingend vorausgesetzt werden, wird an dieser Stelle auf

die entsprechenden Ausf¨ uhrungen verwiesen. 3

2.1.3 Feste und lose Strukturen

Die geringe strukturelle Einschr¨ ankung komplexer Datentypen und daraus folgend auch deren Abbildung durch XML erlaubt es, dass Sammlungen von Entit¨ aten gleichen Typs

an beliebiger Stelle des XML-Baums ⁴ auftreten k¨ onnen. Solche Sammlungen (Collections) weisen gegen¨ uber festen Strukturen den elementaren Unterschied auf, dass ihre Gr¨ oße sowie ihre strukturelle Singnatur von der variablen Anzahl der Elemente der jeweiligen Auspr¨ agung einer Sammlung abh¨ angig ist. Feste Strukturen dagegen zeichnen sich durch eine festgelegte Anzahl von Entit¨ aten aus, welche bei objektorientierter Programmierung

(OOP) der serialisierbaren ⁵ Attributmenge einer Klassendefinition entsprechen. Diese fungiert bei Klassendefinitionen mit fester Attributmenge als eine Art Gatter, welches definierte Wertebereiche f¨ ur elementare oder komplexe Komponenten festsetzt. Werden dem Gatter keine Collections hinzugef¨ ugt, so k¨ onnen diese Gatter strukturell nicht voneinander abweichen. Sind diese Bedingungen dagegen nicht erf¨ ullt, d. h. die Komponente enth¨ alt Collections, so handelt es sich bei der zu betrachtenden Komponente um eine lose Struktur.

Abschließend sei noch erw¨ ahnt, dass feste Strukturen selbst auch als Collections heterogener Komponenten mit fester Elementenanzahl betrachtet werden k¨ onnen, was jedoch dem Grundcharakter der flexiblen Elementenanzahl sowie der Verwaltung homogener Objektklassen der Collections widersprechen w¨ urde und deshalb nicht als sinnvoll zu erachten ist.

³ Transport Dokumente: XML“ [Nie09, S. 17]. ”

⁴ Außer der Blattposition bei Attributen i. S. v. XML [W3C06], [w3s10].

⁵ Sequentiell hintereinander schreibbare, nicht transiente Attribute.

6 2.1 GRUNDLAGEN

2.1.4 Das RDF-System zur Beschreibung von Ressourcen

Das System zur Beschreibung von Ressourcen RDF (Resource Description Framework) dient der Beschreibung und Verkn¨ upfung von Wissensbest¨ anden. Es wurde urspr¨ unglich zur Beschreibung von Metadaten der Online-Inhalte entwickelt, um im Zuge des Semantischen Webs eine bessere Klassifizierung der im Netz verf¨ ugbaren Inhalte vornehmen zu k¨ onnen. Dieser Ansatz wird jedoch in voller Konsequenz nur seitens der Verfechter des Semantischen Webs und der Ontologen verfolgt, wodurch es vorwiegend in Bereichen ein-

gesetzt wird, in denen heterogene Entit¨ aten zu großen Wissensbasen verkn¨ upft werden. ⁶ uber eine eindeutige URI (Uniform Resource Identifier). ⁷ RDF adressiert die Ressourcen ¨

Dies erm¨ oglicht die Aufnahme und Abbildung heterogener komplexer Entit¨ aten sowie die Abbildung der zwischen den Entit¨ aten bestehenden Relationen unter einheitlicher Be-handlung von semantischen und syntaktischen Informationen ¨ uber die Entit¨ aten. Dies ist

ein Vorteil gegen¨ uber reinem XML-Gebrauch, denn es herrschen klare Richtlinien ¨ uber den

Gebrauch und den Speicherort von Metadaten und Attributen. Das ist bei XML nicht der Fall, weil Metadaten teils weggelassen, teils in externen Dateien, wie der DTD, und teils in Attributen, sowohl als Erweiterung der Markup-Tags als auch als einwertige Elemente, gespeichert werden k¨ onnen. Der wohl entscheidende Vorteil des Einsatzes von RDF beruht in der maschinellen Auswertbarkeit der Dokumente, bei welcher sogenannte Reasoner eingesetzt werden. Diese erlauben die Ableitung von Informationen, welche nicht explizit vorliegen, sich jedoch aus einer Kombination der innerhalb der Daten vorhandenen Best¨ ande erschließen lassen. Dies wirkt sich einerseits vorteilhaft auf den Speicherverbrauch aus, weil Informationen, die gewissen Gesetzm¨ aßigkeiten folgen, nicht explizit gespeichert werden m¨ ussen, sondern als Regeln, welche die Reasoner ber¨ ucksichtigen, hinterlegt werden. Andererseits lassen sich h¨ ochst komplexe Abfragen formulieren, welche sogar von implizit vorhandenen, ableitbaren Informationen Gebrauch machen k¨ onnen. Hier bleibt noch anzumerken, dass RDF die Daten als wahre Aussagen ¨ uber die Ressourcen in Form

eines Tripels aus Subjekt, Pr¨ adikat, Objekt speichert. Das Subjekt ist dabei die Ressource, ¨ uber die etwas ausgesagt wird, das Pr¨ adikat kennzeichnet eine Eigenschaft, welche dem Subjekt zugesprochen wird, und das Objekt ist der Wert der Eigenschaft, die entweder elementar oder eine andere Ressource sein kann. Dies f¨ uhrt dazu, dass der zugrunde liegenden Datenstruktur ein gerichteter Graph entspricht.

⁶ Vergleiche: ” Intelligent search on XML data“ [Bla03, S.120].

⁷ Siehe hierzu auch [Nie09, S. 24] und in voller Ausf¨ uhrlichkeit [BL].

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 7 AUMEN

2.2 Distanz-Berechnungsvorschriften in R¨ aumen

¨ Ahnlichkeit schafft Freunde, die Differenzen halten sie zusammen“ - Unbekannt

”

2.2.1 Suchr¨ aume

Suchr¨ aume dienen als Grundlage f¨ ur eine spezielle Implementierung von Suchalgorithmen. Im Folgenden werden die wichtigsten Raum-Begriffe erl¨ autert:

Metrische R¨ aume

Die Bezeichnung des Raumes leitet sich von der den Raum definierenden mathematischen Funktion, der Metrik ab. Diese ordnet je zwei Elementen eines Raums einen positiven, reellen Wert als deren Abstand zu. Formal wird der metrische Raum als eine Abbildung d :

X ×X → R definiert. Diese bezeichnet man als Metrik auf X, wenn folgende Bedingungen erf¨ ullt sind [Zez06, S.8], [Cha01, S.278]:

1 Nicht-Negativit¨ at ∀x, y ∈ D, d(x, y) ≥ 0

2 Symmetrie ∀x, y ∈ D, d(x, y) = d(x, y)

3 Reflexivit¨ at ∀x ∈ D, d(x, x) = 0

4 Positivit¨ at ∀x, y ∈ D, x = y ⇒ d(x, y) > 0

5 Dreiecksungleichung ∀x, y, z ∈ D, d(x, z) ≤ d(x, y) + d(y, z)

Die Postulate 3 und 4 k¨ onnen zum Postulat der Identit¨ at zusammengefasst werden:

3 + 4 Identit¨ at ∀x, y ∈ D, x = y ⇔ d(x, y) = 0

In einigen F¨ allen, wie beispielsweise der Betrachtung von Distanzen zwischen zwei Positionen innerhalb einer Stadt mit Einbahnstrasse, kann es vorkommen, dass die Bedingung der Symmetrie nicht eingehalten wird. In diesen F¨ allen wird von der sogenann-ten Quasi-Metrik gesprochen. Andererseits kann eine Quasi-Metrik z. B. durch das Betrachten der mittleren Distanz zwischen Hin- und R¨ uckweg (d sym (x, z) = (d asym (x, y) + d asym (y, x))/2) in eine Metrik umgeformt werden. Ferner existieren Metriken mit versch¨ arfter Dreiecksungleichung-Bedingung, welche jedoch aus spezifischen - in der Evolu- tionstheorie auftauchenden - Problemen abgeleitet sind und hier nicht weiter betrachtet

8 2.2 GRUNDLAGEN

werden m¨ ussen. Unterschieden wird ferner zwischen diskreter und kontinuierlicher Distanz. Da einerseits die Computer durch die begrenzte Wortl¨ ange, die zum Ausdruck beliebig genauer Werte stets einen ” Flaschenhals“ darstellt, kontinuierliche Distanz nicht

beliebig genau unterscheiden k¨ onnen, und weil die Unterscheidung einer endlichen Anzahl von ¨ Ahnlichkeitsabstufungen v¨ ollig hinreichend f¨ ur die Sicht des Endnutzers erscheint, wird im Rahmen der rechnergest¨ utzten ¨ Ahnlichkeitsanalyse und damit dieser Diplomarbeit von diskreter Distanz als Distanz gesprochen. Die ¨ Ahnlichkeit wird im Rahmen

dieser Diplomarbeit als ein Prozentsatz zwischen 0% und 100% angegeben und bildet da-

mit einen Komplement¨ arwert ⁸ zu der diskreten Distanz. Damit sind zwei Werte maximal unterschiedlich, wenn die Distanz 100% und die ¨ Ahnlichkeit 0% betr¨ agt, und andersherum identisch, wenn die ¨ Ahnlichkeit 100% und die Distanz 0% betr¨ agt.

Im Rahmen dieser Diplomarbeit sowie des SimSearch Frameworks wird noch eine andere Art der Differenzierung der ¨ Ahnlichkeit vorgeschlagen und als PlusMinus ¨ Ahnlichkeit bezeichnet (s. S. 22).

Vektor-Raum Mehrdimensionale R¨ aume, auf denen sich eine Metrik definieren l¨ asst, k¨ onnen auch h¨ aufig als Vektor-R¨ aume aufgefasst werden [Cha01, S. 281]. Dabei werden die Auspr¨ agungen der Attributwerte auf mehrdimensionale R¨ aume projiziert. Die Projektion wird erreicht, indem jedem Attribut eines Objekts eine Dimension zugewiesen wird und dessen Auspr¨ agung einen Punkt innerhalb dieser Dimension darstellt. Ausgehend vom einem Objekt mit n Attributen stellt die Gesamtheit der Auspr¨ agungen seiner Attribute somit einen Punkt in einem n-dimensionalen Raum dar. Dies erlaubt ebenfalls die Definition der Distanz dieser Komponenten als die L¨ ange des Vektors zwischen den Komponenten zugeordneter Punkte (siehe 2.2.1).

L ^p R¨ aume Im Allgemeinen wird durch die sogenannten L ^p -R¨ aume eine Reihe von R¨ aumen definiert, welche unterschiedliche Eigenschaften aufweisen und damit besondere Voraussetzungen an die Berechnung der Distanz stellen. Um das Wesen und die damit zusammenh¨ angenden Paradigmen besser verstehen zu k¨ onnen, werden diese zusammen mit den Distanzvorschriften im Rahmen des Unterkapitels 2.2.1 ” Ermittlung der Distanz in L ^p -R¨ aumen“ auf Seite 10 beschrieben.

⁸ ¨ Ahnlichkeit = 1 - Distanz.

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 9 AUMEN

Grundlagen der Distanz Ermittlung

Der Suchalgorithmus des SimSearch Frameworks arbeitet auf diskreter Basis. Dabei wird ein Durchschnittswert aller feststellbar ¨ ahnlichen Attribute zweier Dokumente gemessen. Dieser wird bei ungerader Teilung gerundet, wodurch das Ergebnis weiterhin diskret bleibt. Dies f¨ uhrt dazu, dass die Distanz zwischen zwei Punkten zu einem gewissen Grad von der Anzahl der Attribute (und damit der Dimensionen) sowie von den jeweils f¨ ur diese Attribute bekannten maximalen und minimalen Wertauspr¨ agungen abh¨ angt. Der durch die Rundung verursachte Fehler kann jedoch h¨ ochstens ein Prozent des gemessenen ¨ Ahnlichkeits-Wertes ausmachen. Diese Herangehensweise entspricht der Distanzmessung innerhalb Euklidischer R¨ aume. Die Distanzvorschrift kann jedoch im Rahmen der ¨ Ahnlichkeitssuche auch innerhalb eines anderen Raumes mit der dort zugeh¨ origen Distanzfunktion durchgef¨ uhrt werden. Die Berechnung der Distanz in einem zweidimensionalen Raum kann leicht veranschaulicht werden, da dieser auch als euklidische Ebene bezeichnet wird und somit den meisten als das Koordinatensystem gel¨ aufig ist.

In der Abbildung 1 werden zwei Komponenten dargestellt. Beide weisen zwei Attribute auf. Die eine Komponente hat bei beiden Attributen den Wert 1 und die andere bei beiden den Wert 2. Damit stellen die beiden Punkte die Koordinaten der Komponenten bei r¨ aumlicher Betrachtung dar. Unter der Annahme, dass die Wertebereiche beider Attribute zwischen 0 und 3 liegen, kann die Distanz sowohl r¨ aumlich als auch rechnerisch ermittelt werden.

R¨ aumliche Ermittlung der Distanz Betrachtet man die Diagonale zwischen dem Ursprung und dem Punkt (3,3), so entspricht die Entfernung zwischen den Koordinaten der bei- den Komponenten genau einem Drittel der L¨ ange der Diagonalen. W¨ urden die Punkte

10 2.2 GRUNDLAGEN

aufeinander liegen, so w¨ are die Entfernung gleich 0. W¨ urden die Punkte stattdessen im Ursprung und auf dem Punkt (3,3) liegen, so w¨ are die Entfernung maximal. Die Distanz entspricht damit dem Abstand zwischen beiden Punkten, w¨ ahrend die ¨ Ahnlichkeit durch

den Rest der Diagonalen repr¨ asentiert wird. Damit betr¨ agt die ¨ Ahnlichkeit 2/3 und die Distanz 1/3.

Rechnerische Ermittlung der Distanz - SimSearch Die Differenz betr¨ agt bei beiden Attributen 1. Die maximal m¨ ogliche Differenz betr¨ agt 3. Um die Distanz berechnen zu k¨ onnen, m¨ ussen beide Werte in Relation gesetzt werden. Dies wird erreicht, indem von der maximalen L¨ angendifferenz (LD) die vorliegende subtrahiert und durch die maximale geteilt wird. Das Ergebnis gleicht der ¨ Ahnlichkeit, weshalb dieses noch von 1 subtrahiert wer-

Ahnlichkeit von (3 − 1)/3 = 2/3 und eine Distanz von den muss. Auch dies ergibt eine ¨ 1 − 2/3 = 1/3.

Rechnerische Ermittlung der Distanz - Pythagoras Die Berechnung innerhalb des SimSearch Frameworks kann, gegen¨ uber der ¨ ublichen Rechenvorschrift f¨ ur den Abstand zweier Punk-

te in der Ebene, vereinfacht durchgef¨ uhrt werden. Dies geschieht aufgrund der Kenntnis der maximalen und minimalen Wertauspr¨ agung bestimmter Klassen von Attributen. Sollte diese Information nicht verf¨ ugbar sein, so muss die Distanz mithilfe des Satzes von Pythagoras berechnet werden. Die Distanz beider Komponenten betr¨ agt damit:

√

(x 1 − x 2 ) ² + (y 1 − y 2 ) ² = (2 − 1) ² + (2 − 1) ² = 1 + 1 ≈ 1, 41421

Die h¨ ochst m¨ ogliche Distanz betr¨ agt dann:

√

(x 1 − x 2 ) ² + (y 1 − y 2 ) ² = (3 − 0) ² + (3 − 0) ² = 9 + 9 ≈ 4, 24264

Dadurch entspricht die Distanz einem Drittel der h¨ ochstm¨ oglichen Distanz, wodurch die ¨ Ahnlichkeit ebenfalls 2/3 betr¨ agt.

Ermittlung der Distanz in L ^p -R¨ aumen Wie bereits angesprochen, ist der Euklidische Raum nur einer von vielen bekannten R¨ aumen. Der Parameter p ist eine beliebige reelle Zahl gr¨ oßer oder gleich 1. Mit n wird die Anzahl der Dimensionen festgelegt. Mit x i wird, bezogen auf das vorherige Beispiel, das i-te Attribut referenziert. Damit l¨ asst sich eine sogenannte p-Norm definieren: n 1/p

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 11 AUMEN

Aus dieser Norm lassen sich Metriken ableiten. Diese werden auch als Minkowski Metriken

bezeichnet. ⁹ Es besteht ein Zusammenhang zwischen der bislang dargestellten Distanz-Berechnungsvorschrift und der aus der Norm ableitbaren Metrik. Die erste Metrik mit p = 1, wird auch als Manhattan-Metrik bezeichnet. Die zugrunde liegende Rechenvorschrift lautet: n 1/1

Die Distanz zwischen zwei komplexen Komponenten gleicht damit der Summe aller zwischen den Attributen bestehenden Differenzen. Im Rahmen des Beispiels 1 ist dies die

Summe (2 − 1) + (2 − 1) = 2. Die Bezeichnung als Manhattan-Metrik ist darauf zur¨ uckzuf¨ uhren, dass statt der Luftlinie zwischen zwei Punkten ein Umweg ¨ uber ein diskretes

Gitternetz, vergleichbar mit dem Straßengitter Manhattans, zur¨ uckgelegt werden muss. Die zweite Metrik mit p = 2, entspricht genau der Berechnung des Pythagoras und damit der Distanz innerhalb der schon gezeigten Euklidischen Ebene. Dies kann durch Einsetzen der 2 in die Norm Gleichung nachgewiesen werden: n 1/2

Mit n = 2 entspricht damit die Gleichung der unter ” Rechnerische Ermittlung der Distanz - Pythagoras“ definierten Distanzgleichung. Mit zunehmendem p lassen sich weitere R¨ aume und Distanzfunktionen unterscheiden (siehe [Zez06]).

⁹ Diese werden im Zusammenhang mit der Minkowski Distanz auf S. 16 noch mal aufgegriffen.

12 2.2 GRUNDLAGEN

2.2.2 Edit-Distanzen

Die Differenz zweier Objekte kann als die Anzahl von Operationen ausgedr¨ uckt werden, welche dazu n¨ otig sind, um das eine Objekt in das andere zu ¨ uberf¨ uhren. Dies ist genau

die Kernfunktionalit¨ at von Edit-Distanzen. Die Edit-Distanzen k¨ onnen je nachdem, ob es sich bei den Objekten um linear oder hierarchisch strukturierte Objekte handelt, in zwei Kategorien unterteilt werden. Im Folgenden werden die beiden Kategorien separat behandelt.

Lineare Edit-Distanzen

Levenshtein Distanz Die Levenshtein Distanz misst die Anzahl der verschiedenen Operationen Ersetzung, Einf¨ ugung und L¨ oschung, die zur Transformation einer Zeichenkette in eine andere ben¨ otigt werden. Die Entscheidung, ob und welche Operation beim Betrachten zweier Zeichen die kosteng¨ unstigste Alternative darstellt, wird mithilfe einer zweidimensionalen Matrix vollzogen. Diese enth¨ alt die Information ¨ uber bislang aufgelaufene Kosten,

welche mit jeder Operation erh¨ oht werden. Stimmen zwei Symbole nicht ¨ uberein, so wird

die bislang aufgelaufene Summe der Kosten um den Kostenbetrag, der zu dem Zeitpunkt kosteng¨ unstigsten Operation erh¨ oht. Die Berechnung wird mit Injizierung der ersten Zeile und der ersten Spalte mit einer von 0 bis zu der jeweiligen L¨ ange der Zeichenkette plus eins fortlaufenden Zahlenreihe begonnen [San83, S.18ff]. Anschließend wird die Matrix spaltenweise durchiteriert. F¨ ur jeden Eintrag wird dabei folgende rekursive Distanzfunktion aufgerufen:

⎧

Dies erlaubt eine differenzierte Gewichtung der Operationen, da die Kosten f¨ ur die Operationen separat vergeben werden k¨ onnen. Um diese jedoch sinnvoll differenziert vergeben zu k¨ onnen, sind Kenntnisse ¨ uber die Semantik der Daten vorausgesetzt. Die Levenshtein Distanz kommt auch im Rahmen des SimSearch Frameworks beim Vergleich primitiver Datentypen unterhalb einer bestimmten LD zum Einsatz. Da dies keine besonderen Vorkenntnisse ¨ uber die Daten voraussetzt, bleiben die Operationen gleichgewichtet.

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 13 AUMEN

Hamming-Distanz Die Hamming-Distanz (HD) wurde urspr¨ unglich zur Erkennung von Missst¨ anden bei der digitalen ¨ Ubertragung von Nachrichten eingef¨ uhrt. Dabei werden je

zwei Nachrichten gleicher L¨ ange bitweise verglichen und die Anzahl der Bits, welche nicht identisch gewesen sind, als Hamming-Distanz ausgegeben [Boo02, S. 354]. Dieser Ansatz l¨ asst sich auch f¨ ur Zeichen anderer endlicher Alphabete verallgemeinern. Die Hamming-Distanz l¨ asst sich wie folgt formalisieren. Gegeben seien zwei Vektoren:

v := (v 1 , v 2 , . . . , v n )

w := (w 1 , w 2 , . . . , w n )

w entspricht der Anzahl der Zeichen,

w unterscheiden:

w) := |{i | v i = w i }| (2.4)

Die hier vorgenommene Zuordnung der Hamming-Distanz zu den linearen Edit-Distanzen ist darauf zur¨ uckzuf¨ uhren, dass die Differenz zwischen den Eingabemengen durch eine eingeschr¨ ankte Operationsmenge ( ¨ Uberschreibung der nicht ¨ ubereinstimmenden Symbole

einer der Mengen mit insert / delete) zum selben Ergebnis f¨ uhrt wie die bloße Z¨ ahlung der nicht ¨ ubereinstimmenden Symbole. Dieser Ansatz ber¨ ucksichtigt auch keine Nachbarschaft von Objekten [Boo02, S.354]. Dies ist darin begr¨ undet, dass jedes einzelne Zeichen, unabh¨ angig von dessen Position, gleichgewichtet wird. Dieser Sachverhalt l¨ asst sich mit folgenden bin¨ aren Folgen veranschaulichen: (a) 1100100000 (b) 1100010000 (c) 1100000001

Den bin¨ aren Folgen (b) und (c) wird mit dem urspr¨ unglichen Ansatz die gleiche Distanz (2) zu (A) zugeordnet. Dieser Sachverhalt repr¨ asentiert zumeist jedoch nur unzureichend die tats¨ achliche Distanz. In den meisten F¨ allen bedeutet die Setzung eines weiteren Bits eine Verdopplung des bislang bestehenden Wertbereichs. Dennoch existieren auch Datenstrukturen, bei denen aus der Reihenfolge der gesetzten Bits keine R¨ uckschl¨ usse auf Unterschiede in der Distanz von Objekten gezogen werden k¨ onnen. Ein Vertreter dieser Gattung ist das Boolsches Array. Dieses speichert Eigenschaften von Objekten, welche nach beliebigen Kriterien sortiert sein k¨ onnen. Dieser und ¨ ahnliche F¨ alle stellen jedoch

14 2.2 GRUNDLAGEN

eine Seltenheit bei der Betrachtung g¨ angiger Datentypen dar. Es ist verbreiteter, die Po-sition eines Bits innerhalb eines Datentyps als zus¨ atzliche Information zu verwenden. ¹⁰ In diesen F¨ allen empfiehlt sich eher der Einsatz einer generalisierten Hamming-Distanz [Boo02, S.355] zur Messung der Distanz auf der Bitebene. Diese wird im Folgenden beschrieben.

Generalisierte Hamming-Distanz W¨ ahrend der eben vorgestellte Ansatz eine sehr begrenzte Operationsmenge aufweist, wird bei der generalisierten Hamming-Distanz (GHD) die Operationsmenge dahingehend erweitert, dass ¨ uber den Distanzwert ebenfalls eine Aussage zu

der Nachbarschaft von Objekten getroffen werden kann. Diese wird um die Shift-Operation erweitert, welche den Transfer eines Bits an eine benachbarte Position effizienter erlaubt als das L¨ oschen und neu Einf¨ ugen. Die Differenz wird bei GHD zwischen der Ausgangs-

(source B S ) und der Zielmenge (target B T ) folgendermaßen bestimmt:

Beide Mengen werden zun¨ achst durch eine nat¨ urliche Zahl repr¨ asentiert. Diese Zahl stellt f¨ ur jedes gesetzte Bit dessen Position (Wertigkeit) dar. Die Repr¨ asentationen werden

im Folgenden als S und T bezeichnet. Ferner wird eine Funktion N (X) eigef¨ uhrt, welche die Anzahl der nicht 0-Elemente einer Menge X zur¨ uckliefert. Dabei gilt N (B S ) = N (S).

Das Ziel ist die Berechnung der Distanz d(S, T ) mithilfe einer Kostenfunktion c(i, j), welche die minimalen Kosten der Transformation der ersten i 1-Bits von B S in die ersten

j 1-Bits von B T misst, wobei 1 ≤ i ≤ N (B S ) und 1 ≤ j ≤ N (B T ) ist. Diese Funktion wird auf den Bitmengen B S und B T aufgerufen: c(N (B S ), N(B T )). Da die GHD sowie die HD Bitfolgen fester L¨ ange betrachten, k¨ onnen Einf¨ uge- sowie L¨ oschoperationen nicht zu einer Ver¨ anderung der Bitfolgen-L¨ ange f¨ uhren. Diese Operationen bewirken in diesem Fall eine Umkehrung des Bits an einer Position beim Einf¨ ugen von 0 zu 1 und beim L¨ oschen von 1 zu 0. Die Berechnung der Kostenfunktion wird f¨ ur das Einf¨ ugen als

c(i, j) = c I + c(i, j − 1) im Fall s i < t j respektive c(i, j) = c I + c(i − 1, j) f¨ ur den Fall s i > i j f¨ ur die L¨ oschoperation definiert. Ferner wird eine Shift-Operation angewandt, wenn der Abstand der Positionen zweier gleicher Bits innerhalb ihrer Komplement¨ ar-Bit-Folgen relativ gering ist. Dieser Abstand wir als () symbolisiert und deren Kosten als eine nichtnegative, monoton steigende Kostenfunktion c S () referenziert. Die Kostenfunktion der Shift-Operation h¨ angt einerseits von der Anzahl der Shift-Operationen ab und wird ande-

¹⁰ Zum Aufbau g¨ angiger Datentypen siehe [Nie09].

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 15 AUMEN

rerseits in einen relativen Bezug zu den Kosten der L¨ oschung und des Einf¨ ugens gesetzt, damit ein Bereich definiert werden kann, in welchem die Shift-Operation kosteng¨ unstiger ausf¨ allt als eine Kombination aus c I und c D .

Die Berechnung des Algorithmus kann effizient mithilfe der dynamischen Programmierung implementiert werden. Da im Rahmen des SimSearch Frameworks stets die Zeichenketten als Repr¨ asentation von Werten betrachtet werden, weil die XML-Daten ohne weitere Betrachtung der DTD als solche hinterlegt werden, wird auf weitere Spezifizierungen des Algorithmus an dieser Stelle nicht eingegangen (siehe [Boo02]).

Hierarchische Edit-Distanzen

Wie bereits im Abschnitt 2.1.2 beschrieben wurde, k¨ onnen XML-Dokumente als B¨ aume aufgefasst werden. Da B¨ aume hierarchisch und nicht linear strukturiert sind, wird im Folgenden von Baum-Edit-Distanzen gesprochen. Diese messen die Distanz zweier B¨ aume als die Anzahl von Einf¨ ugeoperationen, L¨ oschoperationen oder Umbenennoperationen auf Knoten [Guh02, S. 288]. So wie bei der Levenshtein Distanz wird auch hier die Distanz als die Sequenz von Transformations-Operationen mit minimalen Kosten definiert, welche n¨ otig sind, um einen Baum in einen anderen zu ¨ uberf¨ uhren. Guha und Liang weisen in

[Guh02, S. 288] und [Lia05, S. 1] darauf hin, dass die Berechnung der Edit-Distanz sich als sehr kostspielig erwiesen hat. Deshalb wird auch zur Messung der Distanz zwischen

B¨ aumen dort nahegelegt, die Distanz-Messung mithilfe der Einf¨ uhrung von Heuristiken ¹¹ durchzuf¨ uhren. Die Gesamtheit der dort eingesetzten Maßnahmen wird als Approximate XML Join bezeichnet und im Rahmen eines Frameworks implementiert. Das wird zur Abgrenzung des in dieser Arbeit pr¨ asentierten eigenen Ansatzes in 3.2 noch einmal aufgegriffen.

¹¹ Die Erlangung zufriedenstellender Ergebnisse unter Wissens- und Zeitmangel [Gig00].

16 2.2 GRUNDLAGEN

2.2.3 Werte-Distanzen

Mithilfe der Werte-Distanzen wird die Differenz zweier Objekte aus der Differenz der Subbausteine abgeleitet. Die Berechnung der Differenz kann dabei sowohl linear, auf der Folge von direkten Teilkomponenten einer Komponente, als auch ¨ uber die Erkennung von Mustern innerhalb der Teilkomponenten erfolgen. Ferner lassen sich die Teilkomponenten auch als Punkte eines mehrdimensionalen Raumes durch trigonometrische Werte-Distanzen differenzieren. Sollten Abh¨ angigkeiten der Teilkomponenten untereinander einbezogen werden, so wird auch mit quadratischen Werte-Distanzen ein entsprechender Ansatz vorgestellt. Das Unterkapitel wird mit Distanzvorschriften auf Mengen abgeschlossen.

Lineare Werte-Distanzen

Minkowski-Distanz Die Minkowski-Distanz definiert eine Familie metrischer Funktionen zur Messung der L-Distanzen [Zez06, S. 10]. Sie ¨ ahnelt der p-Norm zur Ableitung von Metriken, welche anhand des Beispiels 1 (s. S. 10) veranschaulicht wurde. Die Minkowski-Distanz spezifiziert die p-Norm auf n-dimensionalen Vektoren reeller Zahlen wie folgt:

Es sei angemerkt, dass damit der Aspekt der Distanz als der Betrag der Differenz zweier Werte hinzugef¨ ugt wird. Dies entspricht einem zus¨ atzlichen Schritt, welcher im Zusammenhang mit der p-Norm außerhalb der Gleichung durchgef¨ uhrt wurde.

SimSearch-Distanz Die innerhalb des SimSearch Frameworks angewendete Distanzfunktion wurde bereits vorgestellt. Jetzt wird noch ihre Einordnung zu den linearen Werte-Distanzen sowie eine formale Berechnungsvorschrift dargestellt. Wie bereits erw¨ ahnt, profitiert die SimSearch-Distanz von der Kenntnis der minimalen und maximalen Wertauspr¨ agung bestimmter Attribute. Dadurch wird der Wertebereich, der den jeweiligen Datentypen zugrunde liegt, solange entsprechend eingeschr¨ ankt, bis das System durch die Aufnahme einer kleineren oder gr¨ oßeren Wertauspr¨ agung den Wertbe- reich an neue Gegebenheiten anpasst.

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 17 AUMEN

Da das System eigenst¨ andig pr¨ uft, welche Attribute eines Datensatzes mit welchen Attributen eines anderen verglichen werden k¨ onnen, kann die formale Definition nur f¨ ur Attribute angegeben werden, welche vom System als passende Vergleichskandidaten akzeptiert worden sind. Deshalb kann angenommen werden, dass die Attribute jeweils passende Datentypen aufweisen. Ferner wird statt der Distanz direkt die ¨ Ahnlichkeit berechnet, weshalb der Wert von 1 subtrahiert werden muss. Damit l¨ asst sich die SimSearch-Distanz f¨ ur reelle Zahlen wie folgt definieren: Sei I der Datentyp des i-ten Attributs mx(I) sei der maximale Wert des Datentyps I mi(I) sei der minimale Wert des Datentyps I (x 1 , ..., x n ) seien die Attribute eines Dokumentes A (y 1 , ..., y m ) seien die Attribute eines Dokumentes B min m,n

Zur Berechnung der Distanz auf Zeichenketten wird innerhalb der Rechenvorschrift Levenshtein mit einbezogen. Dies geschieht unterhalb einer als Schwellwert (Threshold) ausgewiesenen maximalen L¨ angendifferenz. Aufgrund dessen kann der Zeichenketten- ¨ Ahnlichkeit-Algorithmus (SSC) nicht direkt den Werte-Distanzen zugeordnet werden (s. S 90).

Sequenzalignment und Pattern Matching

Unter dem Sequenzalignment wird eine aus der Bioinformatik stammende Methodik ver-standen, welche dazu dient, Zeichenketten aufeinander abzugleichen (synonym: alignieren). Dabei sollen die Muster einer Zeichenkette in anderen wiedergefunden werden, weshalb das Verfahren zu einen Teilgebiet der Mustererkennung (Pattern Matching) geh¨ ort. Es kann zwischen zwei Informationen bez¨ uglich des Alignments unterschieden werden. Zum einen kann eine globale ¨ Ubereinstimmung mehrerer Teilmuster beider Sequenzen

durch eine positive Zahl ausgedr¨ uckt werden. Zum Anderen kann ein Teilbereich innerhalb beider Sequenzen lokalisiert werden, welcher besonders hohe ¨ Ubereinstimmungen aufweist.

Im Folgenden wird ein bekannter Algorithmus zum Pattern Matching angegeben sowie zwei weitere, welche die Probleme des globalen und lokalen Sequenzalignment l¨ osen:

18 2.2 GRUNDLAGEN

Knuth Morris Pratt (KMP) Der Algorithmus Knuth Morris Pratt sucht die Position einer Zeichenkette M der L¨ ange m innerhalb einer anderen, l¨ angeren Zeichenkette T der L¨ ange n. Es ist leicht, einen naiven brute-force Ansatz f¨ ur dieses Problem anzugeben. Um die Zeichenkette M (Muster) innerhalb der Zeichenkette T (Text) finden zu k¨ onnen, muss lediglich das Muster M an jeder Stelle der Zeichenkette T angelegt werden und die m Zeichen der Muster-Zeichenkette mit den durch sie maskierten m Zeichen der Zeichenkette T verglichen werden. Sollte das Muster mit den Zeichen nicht ¨ ubereinstimmen, so wird das

Muster weitergeschoben und wieder alle m Zeichen beider Zeichenketten verglichen. Dieser Ansatz erfordert jedoch beim Nichtvorhandensein des Musters innerhalb der Zeichenkette

(worst-case) m × n Vergleiche.

Der KMP Algorithmus profitiert gegen¨ uber dem brute-force Ansatz von der Kenntnis des bislang untersuchten Pr¨ afixes im Falle des Abbruchs beim m i -ten Zeichen. Der Algorithmus weiß demnach nicht nur, ob, sondern auch wieweit die beim Abbruch verglichenen Zeichenketten miteinander ¨ ubereingestimmt haben. Um diese Information sinnvoll

nutzen zu k¨ onnen, wird eine Fehlerfunktion auf dem Muster berechnet, welche pro Position innerhalb des Musters angibt, um wie viele Zeichen weitergesprungen werden kann, da der Vergleich an dieser Position nicht erfolgreich ausfallen kann. Zur Berechnung der Fehlerfunktion wird das Muster einmal mit sich selbst verglichen und dabei die L¨ ange der Wiederholungen des Pr¨ afixes des Musters gespeichert. Sollte ein Teil des Musters dem Pr¨ afix des Musters entsprechen, so kann aus der L¨ ange der ¨ Ubereinstimmung darauf

geschlossen werden, dass bei einem Abbruch des Vergleichs bei der Wiederholung des Pr¨ afixes innerhalb des Musters, die gespeicherte Position der Anzahl der Zeichen entspricht, welche ¨ ubersprungen werden k¨ onnen. Dadurch kann sowohl eine Teilmenge der n Zeichen aus T , als auch eine Teilmenge der m Zeichen aus M vor ¨ uberfl¨ ussigem Vergleich bewahrt

werden. Dies verbessert die Laufzeit auf O(n + m).

Needleman-Wunsch und Smith-Waterman Der Needleman-Wunsch Algorithmus erm¨ oglicht die Berechnung des globalen Sequenzalignments (GSA). Die Berechnung ¨ ahnelt stark der linearen Edit-Distanz nach Levenshtein. Aufgrund des bioinformatorischen Hintergrunds sollen jedoch sogenannte Gaps (L¨ ucken) zugelassen werden. Dies l¨ asst eher den evolution¨ aren Vergleich von DNS (DNA) Sequenzen zu [Nee69, S. 443]. Im Unterschied zu Levenshtein werden die Kosten einer Operation nicht frei vergeben, sondern mittels einer

DISTANZ-BERECHNUNGSVORSCHRIFTEN IN R ¨ 2.2 19 AUMEN

Kostenfunktion berechnet.

W¨ ahrend die urspr¨ ungliche Definition des Needleman-Wunsch-Algorithmus keine Matrix-Rekurrenzen enthalten hat, wurden diese in einem Dokument von Waterman, Smith und Beyer erstmals eingef¨ uhrt [MSW76].

Der Smith-Waterman-Algorithmus dagegen berechnet das lokale Sequenzalignment (LSA), welches jedoch unter bestimmten Bedingungen auch durch Backtracking mithilfe des Needleman-Wunsch-Algorithmus berechnet werden kann. Dabei sollen zwei Teilsequenzen zweier Zeichenketten lokalisiert werden, die im Rahmen beider Zeichenketten die h¨ ochste ¨ Ubereinstimmung aufweisen. Da, wie anfangs erw¨ ahnt, die L¨ osung des GSA und LSA nur im Rahmen der Bioinformatik und damit f¨ ur eine sehr begrenzte Teilmenge von Zeichenketten (DNS-Strukturen) von Bedeutung ist, wird an dieser Stelle auf allgemeinere Metriken n¨ aher eingegangen.

Trigonometrische Werte-Distanzen

Als trigonometrische Werte-Distanz wird im Folgenden speziell das Kosinusmaß betrachtet. Dieses berechnet die ¨ Ahnlichkeit zweier Vektoren als deren Winkel bez¨ uglich des Nullvektors [Sch06, S. 34] und kann wie folgt definiert werden:

x, y sei das Skalarprodukt zweier Vektoren x respektive y sei dessen Betrag

Der hiermit ermittelte ¨ Ahnlichkeitswert hat einen Wertebereich zwischen [-1,1]. Um das Ergebnis den Ergebnissen bislang vorgestellter Distanz-/ ¨ Ahnlichkeits-Werte anzupassen,

muss dieses noch zus¨ atzlich halbiert und anschließend 0,5 addiert werden. Zur Ermittlung der Distanz braucht dieser Wert, so wie auch bei allen anderen zwischen 0 und 1 normierten Verfahren, von 1 subtrahiert zu werden [Sch06, S. 232]. Das Kosinusmaß wird h¨ aufig im Zusammenhang mit der Berechnung der Distanz von Zeichenketten, welche aus mehreren Termen bestehen, angef¨ uhrt. In der letzten Zeit gewinnt dieses Verfahren im Rahmen der immer popul¨ arer werdenden Kernel-Funktionen zunehmend an Bedeutung (s. S. 46).

20 2.2 GRUNDLAGEN

Quadratische Werte-Distanzen

Die quadratischen Werte-Distanzen zeichnen sich dadurch aus, dass sie Zusammenh¨ ange zwischen den einzelnen Dimensionen eines Vektors ber¨ ucksichtigen k¨ onnen. Diese Anforderung wird bei denjenigen Datentypen gestellt, bei welchen die Aussagekraft eines Attributes von weiteren Attributen vervollst¨ andigt wird. Dies ist z. B. bei Bildobjekten der Fall. Inwieweit ein Bild als rot eingestuft werden kann, wird nicht nur anhand des Anteils der roten, sondern auch der Orange und Magenta Farbanteile bestimmt. Im Unterschied zu linearen Werte-Distanzen werden die quadratischen Werte-Distanzen mit einer qua-dratischen n × n Matrix M multipliziert. Die Einflussnahme der einzelnen Dimensionen aufeinander wird durch einen Wert zwischen 0 und 1 repr¨ asentiert, welcher entlang der Diagonalen gespiegelt innerhalb der quadratischen Matrix abgelegt wird [Zez06, S. 11]. Formal kann die quadratische Werte-Distanz wie folgt definiert werden: x und y seinen zwei n-Dimensionale Vektoren.

M sei die gewichtete n × n Matrix

( x − y) ^T · M · ( x − y) d M ( x, y) = (2.8)

Auch wenn bereits eine Reihe effizienter Algorithmen zur Berechnung quadratischer Distanz vorgelegt werden konnte, ist die Berechnung dieser immer noch sehr CPU-intensiv (siehe [Sei98, Abstract]). Es wird deshalb empfohlen, die Berechnung - wie bei der hierarchischen Edit-Distanz - durch die Einf¨ uhrung von Heuristiken zu beschleunigen. Da im Rahmen des SimSearch Frameworks XML-Daten untersucht werden, welche selten als Grundlage zu Kodierung von Medieninhalten verwendet werden, spielt die Betrachtung von Zusammenh¨ angen zwischen den Attributen an dieser Stelle eine rein theoretische Bedeutung (siehe [Sei98]).

Mengen-Werte-Distanzen

Die ¨ Ahnlichkeit bzw. Distanz kann auch bei disjunkten Mengen direkt berechnet werden. Eine einfache Berechnungsvorschrift hierzu wurde bereits anfangs des Jahrhunderts von Paul Jaccard angegeben. Der nach ihm benannte Jaccard-Koeffizient misst die ¨ Ahnlich-

keit zweier Mengen und l¨ asst sich wie folgt formalisieren: