1	Effiziente Ähnlichkeitssuche Wie findet man ähnliche Objekte in großen Datenmengen ?
2	Übersicht Thematik Ähnlichkeitsbegriff Ein mehrstufiges Suchverfahren Anwendungsgebiete
3	Thematik Suche von "ähnlichen" Objekten in Datenbanken mit sehr vielen Einträgen Übersetzung Katalogen Gesetzestexte EU: 30 Mio Sätze in verschiedenen Sprachen Bilddatenbanken
4	Verwendete Abkürzungen und Begriffe Fuzzy Search Unscharfe Suche Similarity Ähnlichkeit Match Treffer Exact Match 100 % gleich Fuzzy Match < 100 % Ähnlichkeit
5	Was bedeutet Ähnlichkeit ? Zeichenketten/Byte-orientiert abcde ~ a\|cde ~ bacde linguistisch (sprachlich) motiviert morphologisch orientiert Haus ~ Häuser / kaufen ~ kaufte syntaktisch orientiert Aktiv vs. Passiv semantisch orientiert Bank ~ Kreditinstitut, Programm ~ Anwendung Synonyme, Antonyme Genetik Ähnliche Chromosonenabschnitte, Proteine ... Bilder ?
6	Anforderungen an Ähnlichkeit Anwendungsorientiert Funktional Gesucht Abbildungsfunktion – „Signatur“ - eines Objektes in einen „charakteristischen Schlüssel“ Sig(A) Ähnlichkeitsfunktionen Similarity_Sig(Sig(A), Sig(B)) Similarity(A, B) Monotonie Kleine Änderungen/Unterschiede in Objekten A, B sollen nur in kleinen Ähnlichkeitsunterschieden resultieren Monotoniekriterum Beispiel: ANSI-Wert ist schlechtes Ähnlichkeitsmaß für Zeichenkettenähnlichkeit
7	Verfahren Brute-Force-Verfahren Ganze Datenbank durchsuchen Die ersten n Bytes, Zeichen müssen gleich sein Suche über Volltextindex bei Texte Morphologische Varianten Ein stufenweises Suchverfahren Optional 1. Normalisierungsschritt Haus è haus Trigram-basierte Suche in Spezialindex Verallgemeinern der Suche Levenshtein-Vergleich
8	Trigram basierter Suchindex Zeichen/Byte-Kette wird in eine Menge von Trigramen – drei aufeinander folgende Zeichen/Bytes - zerlegt. Beispiel: „Hallo“ è „Hal“, „all“, „llo“ Allgemeiner können auch n-Grame verwendet werden Grundidee ist nun die Häufigkeitsverteilung der Trigram-Menge mittels einer Transformation in einen Vektor fester Länge abzubilden und in dessen Vektorelementen abzuspeichern Signatur
9	Trigram-Signatur Transformation des Trigrams A in eine Zahl 1. Sum = a[0]const² + a[1]const + a[2] Ermittlung des Index des zum Trigrams gehörenden Vektorelements durch die Modulo-Operation 2. Index = Sum % VectorLength und Inkrementierung des Vektorelements 3. Vector[Index]++
10	Trigram Beispiel
11	Fuzzy Index Baum Verwendung eines nicht ausbalancierten ternären Baumes
12	Datenbank-Aufbau Fuzzyindex-Datei + Relationale Datenbank Jeder Fuzzyknoten enthält im Datenbereich einen Verweis auf einen Eintrag in der Datenbank
13	Suche im Fuzzy-Index Bestimmen der Unter- und Obergrenze auf Grund der gewünschten Ähnlichkeit Bei n Trigramen des Suchsegments UL = n – nSimilarity/100 OL = n + nSimilarity/100 Selektion aller innerhalb dieser Grenzen sich befindlichen Wurzel-Fuzzyknoten Durchsuche der zu dieser Menge dazugehörenden Knoten Statistik: bei gegebener Ähnlichkeit 70 % werden bei 100.000 Knoten im Baum etwa 50.000-75.000 Knoten besucht Erzeugt eine Menge potentieller Trefferkandidaten mit Verweisen in die Datenbank mit der jeweiligen "Fuzzyquality"
14	Eintragsselektion Für Kandidatenmenge werden alle Einträge aus der Datenbank gelesen und auf ihre Ähnlichkeit geprüft. Als Ergebnis liegt ein prozentuales Ähnlichkeitsmaß vor. Raw Quality, Before ReplacementClass Quality
15	Ähnlichkeitsbewertung Ermitteln der Byte/Zeichenkettenähnlichkeit zwischen Suchobjekt und Objekten aus der Datenbank Levenshtein - Ähnlichkeitsmaß Berücksichtigt Einfügungen, Löschungen, Ersetzungen Ermöglicht diese unterschiedlich zu gewichten Trefferqualifizierung 100 % Perfect Match 100 % mit Verallgemeinerung Full Match < 100 % Fuzzy Match
16	Ersetzungsklassen / Verallgemeinerung Verbesserung der Suchergebnisse durch Verallgemeinerung Zahlenklassen Begriffsklassen, Monatsnamen … Akronyme, UNO, NATO, CEC … … Generalisieren des Objektes und Suche damit Generalisierte Objekte in Datenbank abspeichern Anschließend Neuberechnung der Ähnlichkeit After ReplacementClass Quality
17	Beispiel Treffer
18	Anwendungsgebiete 1 Dokumentenverarbeitung Übersetzung Wíederverwenden von Übersetzungen Textbausteindatenbank Konkordanzanalyse Automatische Extraktion von Übersetzungen, Begriffen Ähnlichkeitsanalyse von Texten Plagiatserkennung basierend auf der Trigram-Struktur Textklassifikation Durch Vergleich mit Sätzen aus bekannten Sachgebieten
19	Anwendungsgebiete 2 Gen-Datenbanken Suche nach ähnlichen Gensequenzen Proteinen, Chromosomen Bilddatenbanken Suche nach ähnlichen Bildern Personenerkennung Bytedarstellung der Bildformat für Trigram-Berechnung verwenden Biometrische Maße Iris, Fingerabdruck