1	Ähnlichkeitssuche in Texten Am Beispiel von Übersetzungsdatenbanken
2	Inhalt Thematik und Fragestellung Ähnlichkeitsbegriff Ein mehrstufiges Suchverfahren
3	Thematik Bei vielen zu übersetzenden Texten ändert sich von einer Version zur nächsten nur 5 – 20 % Softwaredokumentation Gesetzestexte EU Amtssprachen Benutzermanuale Autoindustrie, Telekommunikation ...
4	Beispiel Lokalisierung Betriebssystem Unix – Manuale ~ 1000 – 2000 SGML Dateien Etwa 10 – 1000 Segmente pro Datei Insgesamt etwa 200.000 Segmente ~ 5 – 10 % Änderungen Tw. minimal, etwa Versionsnummern, Monatsnamen, Umgruppierungen Konsistenz Dokumentenmanagement
5	Fragestellung Wie können alte Übersetzungen mit einem minimalen Aufwand wieder verwendet werden ? Wie kann man ähnliche Segmente (wieder)finden ?
6	Verwendete Abkürzungen und Begriffe TM Translation Memory Fuzzy Search Unscharfe Suche Match Treffer
7	Was bedeutet Ähnlichkeit ? Zeichenkettenorientiert abcde ~ a\|cde ~ bacde linguistisch (sprachlich) motiviert morphologisch orientiert Haus ~ Häuser / kaufen ~ kaufte syntaktisch orientiert Aktiv vs. Passiv Tempus (Präsens / Perfekt) Det NP ~ Indet NP semantisch orientiert Bank ~ Kreditinstitut, Programm ~ Anwendung Synonyme, Antonyme
8	Ähnlichkeitskriterium Anwendungsorientiert Übersetzer Zeichenkettenorientiert Für die Vorübersetzung = Grobübersetzung Zeitersparnis = Geld Formatbehandlung wichtig Suchen im Web, Textdatenbanken morphologisch / syntaktisch / semantisch
9	Wo liegen die Probleme ? Satz- und Übersetzungsdatenbanken können sehr groß werden Mehrere 10 Millionen Einträge Attribute Änderungsaufwand Satzanfänge sind oft unterschiedlich Formatbehandlung Mehrbenutzerbetrieb
10	Verfahren Brute-Force-Verfahren Ganze Datenbank durchsuchen Die ersten n Buchstaben müssen gleich sein Suche über Volltextindex Morphologische Varianten Ein stufenweises Suchverfahren Trigram-basierte Suche in Spezialindex Verallgemeinern durch Ersetzungsklassen Levenshtein-Vergleich
11	Datenbankerstellung Alignierung Zerlegung der Quell- und Zieltexte in Segmente (z.B. Sätze) Mittels struktureller und statistischer Verfahren werden die Segmente aus Quelle und Ziel miteinander verbunden Manuelle Korrektur Import in Datenbank
12	Trigram basierter Suchindex Satz (Zeichenkette) wird in eine Menge von Trigramen – drei aufeinander folgende Buchstaben - zerlegt. Grundidee ist nun die Häufigkeitsverteilung der Trigram-Menge mittels einer Transformation in einen Vektor fester Länge abzubilden und in dessen Vektorelementen abzuspeichern
13	Trigram-Transformation Transformation des Trigrams in eine Zahl 1. Sum = a[0]const² + a[1]const + a[2] Ermittlung des Index des zum Trigrams gehörenden Vektorelements 2. Index = Sum % VectorLength und Inkrementierung des Vektorelements 3. Vector[Index]++
14	Trigram Beispiel
15	Fuzzy Index Baum Verwendung eines nicht ausbalanzierten ternären Baumes
16	Suchalgorithmus
17	Datenbank-Aufbau Fuzzyindex + Relationale Datenbank Jeder Knoten enthält einen Verweis auf einen Eintrag in der Datenbank
18	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"
19	Eintragsselektion Für Kandidatenmenge werden alle Segmente aus der Datenbank gelesen Und auf ihre Ähnlichkeit geprüft Als Ergebnis liegt ein prozentuales Ähnlichkeitsmaß vor Raw Quality, Before ReplacementClass Quality
20	Ähnlichkeitsbewertung Ermitteln der Zeichenkettenähnlichkeit zwischen Suchsatz und Sätzen aus der Datenbank Levenshtein - Ähnlichkeitsmaß Berücksichtigt Einfügungen, Löschungen, Ersetzungen Ermöglicht diese unterschiedlich zu gewichten Trefferqualifizierung 100 % Perfect Match 100 % mit Ersetzungsklassen Full Match < 100 % Fuzzy Match
21	Ersetzungsklassen Verbesserung der Suchergebnisse durch Verallgemeinerung Zahlenklassen Begriffsklassen, Monatsnamen … Akronyme … Generalisieren des Segments und Suche damit Generalisierte Segmente in Datenbank abgespeichern Anschließend Neuberechnung der Ähnlichkeit After ReplacementClass Quality
22	Beispiel Treffer
23	Weitere Anwendungsbereiche Konkordanzanalyse Automatische Extraktion von Übersetzungen Ähnlichkeitsanalyse von Texten Plagiatserkennung basierend auf der Trigram-Struktur Textklassifikation Durch Vergleich mit Sätzen aus bekannten Sachgebieten Textbausteindatenbank Gen-Datenbanken