Ermittlung der Fuzzy-Matches

Zu jedem der 510 Sätze der Stichprobe werden 11 Fuzzy-Matches aus der Datenbank abgefragt. Da der Anfragesatz selbst in der Datenbank vorhanden ist, sind unter den Treffern zehn neue Fundstellen.^3.42

In Folgendem wird beschrieben, wie die Fuzzy-Matches ermittelt werden. Wie bereits in Abschnitt erwähnt, habe ich keine Literatur zu diesem Spezialthema gesucht. Eine Implementation des im Abschnitt skizzierten Ansatzes schien mit den im KoKS-System vorhandenen Komponenten leicht umsetzbar zu sein. Wie in der nachfolgenden Darstellung deutlich wird, mussten jedoch mehrere Detailprobleme gelöst werden.

Einschränkung der Kandidaten

Im ersten Teil der Fuzzy-Match-Suche wird die Kandidatenmenge soweit eingeschränkt, dass nur ein kleiner Teil des Gesamtkorpus genauer geprüft werden muss. Im wesentlichen wird dazu die im Abschnitt Methode zum Zugriff auf Sätze, die eine Teilmenge der Token des Anfragesatzes enthalten, verwendet.

Expansion der Anfragetoken

Verwendet man nur die Token des Anfragesatzes für die Suche im Korpus, dann werden Abweichungen in der Flexion genauso behandelt wie Ersetzungen durch andere Wörter. Hat der Satz sonst nicht genug Wörter mit dem Anfragsatz gemeinsam, wird er nicht in die Menge der Kandidat aufgenommen. Ein solcher Fall kann beispielsweise eintreten, wenn das Subjekt eines kurzen Satzes den Numerus wechselt. Verb, Nomen, Artikel und Adjektive, die zum Subjekt gehören, können sich dann geringfügig verändern, sodass die Sätze auf Tokenebene wenig oder nichts gemeinsam haben.

Das Problem könnte leicht mit einer Suche mittels der annotierten Grundformen gelöst werden, wenn die Annotation eindeutig und vollständig wäre. Der Tagger annotiert jedoch Grundformlisten, wenn die Grundform nicht eindeutig aus dem Lexikon des Taggers hervorgeht, oder gar keine Grundform, wenn die Vollform unbekannt ist. (Siehe auch Abschnitt .) Im letzteren Fall kann nur mit dem Token gesucht werden. Der erste Fall kann sowohl im Anfragesatz als auch im Korpus auftreten. Für die Suche werden daher sämtliche Grundformlisten zusammengestellt, die eine Grundform enthalten, die in der Liste der Grundformen des Anfragetokens vorkommen. (Eindeutige Grundformannotationen werden dabei als einelementige Listen behandelt.) Beispielsweise werden zum Token ,,fiel`` die drei Grundformlisten ,,fallen``, ,,fallen, gefallen`` und ,,fallen, fällen`` gebildet. Diese Aufgabe wird mit der im Abschnitt beschriebenen Grundformentabelle effizient durchgeführt.

Da bei der Abfrage von Fundstellen zu Grundformlisten grundsätzlich die Tokentupeltabelle verwendet wird, übersetzt die Datenbank implizit jede Grundformliste in die Menge der Token, die mit ihr annotiert wurden. Es wird also für jedes Anfragetoken mit einer Menge von Token nach Fundstellen gesucht. Im Fall, dass direkt mit dem Anfragetoken gesucht wird, ist die Menge einelementig. Die Menge enthält aber auch im anderen Fall immer das Anfragetoken.^3.43Daher wird dieser Schritt hier als Expansion der Anfragetoken bezeichnet.

Ermittlung der Häufigkeiten

Als nächstes wird für jedes expandierte Anfragetoken die ungefähre Häufigkeit im Korpus ermittelt, um zu entscheiden, welche Token für die Suche im Korpus benutzt werden. Die Häufigkeit des Anfragetokens und der zusammengestellten Grundformen wird in Tabellen der häufigsten tausend Token bzw. Grundformen nachgeschlagen. (Die Werte sind nicht exakt, da die Tabellen nicht auf dem aktuellen Stand des Korpus sind.) Ist keine der Formen in den Häufigkeitstabellen gelistet, wird die Häufigkeit null unterstellt. Sie wird hier verwendet, um seltene Token zu kennzeichnen, und bedeutet nicht etwa, dass das Token nicht im Korpus aufträte.

Auswahl der Anfragetoken

Ein expandiertes Token wird für die Suche im Korpus herangezogen, wenn dessen Häufigkeit unter einem Schwellwert liegt, der in etwa die häufigsten 200 Token ausschließt. Wenn weniger als acht Token ausgewählt werden, wird die Schwelle abhängig von der bisherigen Anzahl der selektierten Token moderat erhöht. Nur wenn die Anzahl trotzdem unter zwei bleibt, wird die Schwelle so weit erhöht, dass selbst Formen von ,,sein``, ,,werden`` (Deutsch) und ,,have`` (Englisch) ausgewählt werden.

Die Beschränkung auf nicht zu häufige Token hat große Ähnlichkeit mit der Verwendung von so genannten Stoppwortlisten, die nicht zu berücksichtigende Wörter benennen. Hier würde eine solche Liste alle Wörter enthalten, die keinen Beitrag zur Einschränkung der Kandidatenmenge erwarten lassen. Der Unterschied des hier gewählten Auswahlverfahrens zu Stoppwortlisten ist die Anpassung der Häufigkeitsschwelle an die Zahl der bisher aufgenommenen Token. Beispielsweise werden zu der Anfrage ,,Sein oder nicht sein.`` die Anfragetoken ,,oder`` und ,,nicht`` verwendet, obwohl sie auf den Häufigkeitsrängen 109 und 47 stehen.<sup>3.44</sup>Der beste Fuzzy-Match ,,Sein oder Nichtsein`` wird in den Wörterbüchern des KoKS Systems gefunden. (Zur Berwertung der Güte eines Treffers siehe weiter unten.) Der zweitbeste Treffer ,,Oder nicht¿` stammt aus dem Harry Potter Korpus (Band 4, Kapitel ,,Der Todesser``). Mit einer Stoppwortliste hätte kein expandiertes Token für den Korpuszugriff zur Verfügung gestanden, sodass die Treffermenge leer gewesen wäre.

Wahl der Mindestanzahl der Übereinstimmungen

Die Zahl $k$, die angibt, wie viele der $n$ ausgewählten Anfragetoken in einem Satz vorkommen müssen, damit er in die Kandidatenmenge für die Fuzzy-Matches aufgenommen wird, ist der zweite Faktor, der die Auswahl der Kandidaten steuert. Je kleiner $k$ gewählt wird, desto mehr Sätze werden als Fuzzy-Match in Betracht gezogen.

Für ein Translation Memory, das nur ganze Sätze mit geringem Korrekturbedarf als Übersetzungsvorschläge anbieten will, würde es Sinn machen, nur eine feste Anzahl von Abweichungen zu erlauben. Wenn beispielsweise maximal zwei Wörter unterschiedlich sein dürfen, könnte man $k=n-2$ wählen. Dagegen muss ein kleiner Wert für $k$ eingesetzt werden, wenn auch Sätze mit wenigen Übereinstimmungen gefunden werden sollen. Ein sehr kleiner Wert, z.B. $k=3$, könnte zum Auffinden von kurzen Satzfragmenten, so genannte Subsegment-Matches, dienen. Hierbei ist wichtig, dass häufige Token zuvor von der Suche ausgeschlossen wurden, da sonst viele irrelevante Sätze gefunden werden, die nur in Artikeln, Präpositionen, Konjunktionen oder anderen häufigen Wörtern mit dem Anfragesatz übereinstimmen.^3.45

Für die Fuzzy-Matches der Stichprobe wurde $k =$   min$(3, \lceil \frac{n}{2} \rceil)$ gesetzt, um die Anzahl der auszuführenden Korpusanfragen klein zu halten. Sie liegt in O($n^3$), da $n$ in der Anzahl $\binom{n}{k}$ mit $k \leq 3$ höchstens in der dritten Potenz auftreten kann. Mit dieser Wahl von $k$ werden viele Sätze als Kandidaten zugelassen. Nur selten sollten also relevante Sätze nicht enthalten sein. Die zusätzliche Zeit, die die Verarbeitung der großen Kandidatenmenge erfordert, ist hier anders als in einer interaktiven TM-Anwendung kein Hindernis.

Korpuszugriff

Zu jedem ausgewählten Anfragetoken werden zuerst die Satznummern der Sätze bestimmt, in denen eine Form des expandierten Tokens auftritt. Jeweils $k$ Satznummerlisten werden dann geschnitten, um die Sätze zu ermitteln, in denen mindestens $k$ Anfragetoken vorkommen. Die Vereinigung aller $\binom{n}{k}$ Schnitte ergibt schließlich die Kandidatenmenge. Auf Seite im Abschnitt sind diese Operationen als Formel notiert. Im Abschnitt ist der Spezialfall mit $k = 1$ beschrieben.

Bewertung mit Ähnlichkeitsmaß

Aus der Kandidatenmenge können die Sätze, die als Fuzzy-Matches gelten sollen, mit aufwendigeren Methoden ausgewählt werden, da diese Menge wesentlich kleiner ist als das Gesamtkorpus. Im Abschnitt werden Möglichkeiten angedeutet, wie linguistisches Wissen in die Bewertung der Relevanz der Kandidaten einbezogen werden kann, und auf () verwiesen, die mehrere Ähnlichkeitsmaße daraufhin untersuchen, wie sie die Qualität der Übersetzungsvorschläge in einer TM-Anwendung beeinflussen.

Auch hier wird ein Ähnlichkeitsmaß, das den Grad der Übereinstimmung von Anfragesatz und Kandidat bestimmt, als Maß der Relevanz verwendet. Es handelt sich um ein einfaches, zeichenbasiertes Maß, das im KoKS-Projekt entwickelt wurde. Das Ähnlichkeitsmaß stützt sich nicht auf einzelne Zeichen, sondern auf alle Sequenzen von drei Zeichen, die im Satz auftreten. Diese Sequenzen nennt man Trigramme. Seien $c_1(t)$ und $c_2(t)$ die Häufigkeiten der Trigramme $t$ in den zu vergleichenden Zeichenfolgen. Dann wird als Ähnlichkeit der Wert

$$a = \frac{ \sum_t \text{min}(c_1(t), c_2(t)) }{ \sum_t \text{max}(c_1(t), c_2(t)) }$$

eingesetzt.^3.46Der Wert liegt zwischen null und eins. Für identische Zeichenfolgen ist die Ähnlichkeit eins, d.h. 100 %.

Zu den nachfolgend angegebenen Zahlen sollte erwähnt werden, dass Leerzeichen am Anfang und Ende der Zeichfolgen hinzugefügt und die Klein-/Großschreibung und Satzzeichen ignoriert werden. Im KoKS-Abschlussbericht auf Seite 57 bis 62 beschreiben () das Ähnlichkeitsmaß detailiert und geben viele Beispiele für den bilingualen Anwendungsfall an.^3.47Hier sind neue Beispiele nötig, da die zu vergleichenden Sätze bei der Fuzzy-Match Suche einsprachig sind. Tabelle zeigt für sieben Zeichenfolgen die Ähnlichkeitswerte aller Paare. Beispielsweise wird den Zeichenfolgen ,,Baumes`` und ,,Baumschatten`` eine Ähnlichkeit von $\frac{3}{15} = 20 \%$ zugeschrieben. (Drei von 15 Trigrammen, nämlich ,, ba``, ,,bau`` und ,,aum``, treten in beiden Zeichenfolgen auf.) Die Tabelle ist symmetrisch um die Diagonale, da das Maß symmetrisch ist.

Tabelle: Ähnlichkeitswerte für einige kurze Zeichenfolgen

	1	2	3	4	5	6	7
1	100 %	20 %	10 %	24 %	3 %	4 %	3 %
2	20 %	100 %	0 %	37 %	21 %	27 %	21 %
3	10 %	0 %	100 %	3 %	18 %	24 %	18 %
4	24 %	37 %	3 %	100 %	29 %	35 %	29 %
5	3 %	21 %	18 %	29 %	100 %	58 %	44 %
6	4 %	27 %	24 %	35 %	58 %	100 %	69 %
7	3 %	21 %	18 %	29 %	44 %	69 %	100 %

1: Baumes, 2: Baumschatten, 3: Bäume, 4: der Schatten eines Baumes, 5: der lange Schatten der Bäume, 6: im Schatten der Bäume, 7: im Schatten der großen Bäume

Beispiel

Der konstruierte Satz

soll hier als Beispiel dienen. Er wurde so gewählt, dass unterschiedliche Kombinationen von Anfragetoken zu Fuzzy-Match-Kandidaten führen. Folgende acht Token werden ausgewählt: 0: Schatten, 1: Baumes, 2: Spinnen, 3: fangen, 4: langen, 5: sehr, 6: man, 7: gut. Angegeben sind Indexnummern, die im Folgenden verwendet werden. Die Reihenfolge der Token ist aufsteigend mit der festgestellten Häufigkeit. Es wird $k =$   min$(3,8/2) = 3$ gesetzt. Nur neun der $\binom{8}{3} = 56$ möglichen Kombinationen von Anfragetoken ergeben Kandidaten:

Schnitt [0, 1, 2]: 2 Kandidaten
Schnitt [0, 1, 4]: 2 Kandidaten
Schnitt [0, 4, 6]: 1 Kandidat
Schnitt [1, 4, 7]: 1 Kandidat
Schnitt [2, 3, 4]: 2 Kandidaten
Schnitt [4, 5, 6]: 1 Kandidat
Schnitt [4, 5, 7]: 2 Kandidaten
Schnitt [4, 6, 7]: 1 Kandidat
Schnitt [5, 6, 7]: 4 Kandidaten
Vereinigung: 16 Kandidaten

Hier ist die Summe der Anzahlen in den einzelnen Schnitten gleich der Mächtigkeit der Vereinigung. Dies ist ungewöhnlich und bedeutet, dass die Schnitte paarweise disjunkt sind. Mit $k=4$ hätte man zu dem Beispielsatz folglich keine Kandidaten erhalten.

Tabelle: Fuzzy-Matches zum Beispielsatz

$a$	Fuzzy-Match	Quelle
18 %	Zwei einzelne Spinnen entflohen dem Licht des Zauberstabs in den Schatten der Bäume.	H.P. Bd 2
16 %	Und so folgten sie den huschenden Schatten der Spinnen in das Dickicht der Bäume.	H.P. Bd 2
14 %	Zwanzig Minuten lang gingen sie durch den Wald, laut redend und scherzend, bis sie endlich auf der anderen Seite zwischen den Bäumen hervortraten und sich im Schatten eines gigantischen Stadions fanden.	H.P Bd 4
14 %	Die letzten Strahlen der untergehenden Sonne tauchten das Land und die langen Schatten der Bäume in blutrotes Licht.	H.P. Bd 3
14 %	Man sieht, auch in der Wettbewerbspolitik wirft die WWU ihren langen und wohltünden Schatten voraus.	EU 1991
12 %	Dann verstecken wir uns am besten hinter einem Baum und halten Ausschau. # # Gut, aber hinter den Gewächshäusern lang!	H.P. Bd 3
12 %	Ron hatte ihm den ganzen Abend lang Ratschläge erteilt, zum Beispiel: # Wenn er versucht, dir einen Fluch anzuhängen, dann weich ihm besser aus, ich weiß nämlich nicht, wie man sie abblocken kann.	H.P. Bd 1
12 %	Moody langte in das Glas, fing eine Spinne ein und legte sie auf seinen Handballen, so daß alle sie sehen konnten.	H.P. Bd 4
10 %	Außerdem will sie auch ihre Bemühungen für eine bessere Ausbildung des Personals verstärken. Da in der Gemeinschaft bereits sehr lange Kernkraftwerke bestehen, wurden umfangreiche Betriebserfahrungen gesammelt, die ein beträchtliches Kapital darstellen.	EU 1990
8 %	# Der Kobold las den Brief sorgfältig durch. # Sehr gut #, sagte er und gab ihn Hagrid zurück. # Ich werde veranlassen, daß man Sie in beide Verliese führt.	H.P. Bd 1
7 %	Und dann fing er an, ihnen alles zu erzählen. Fast eine Viertelstunde lang sprach er in das gespannte Schweigen hinein: Er erzählte von der körperlosen Stimme und wie Her- mine schließlich begriffen hatte, daß er einen Basilisken in den Rohren gehört hatte; wie er und Ron den Spinnen in den Wald gefolgt waren, wo Aragog ihnen sagte, wo das letzte Opfer des Basilisken gestorben war; wie er auf den Gedanken kam, daß die Maulende Myrte dieses Opfer gewesen war und daß der Eingang zur Kammer des Schreckens in ihrer Toilette sein könnte...	H.P. Bd 2

Wie für die Stichprobe werden die elf Kandidaten mit der größten Ähnlichkeit zum Anfragesatz als Fuzzy-Matches übernommen. Tabelle zeigt die Fuzzy-Matches geordnet nach Relevanz. Von den fünf übrigen nicht aufgeführten Kandidaten sind vier wesentlich länger als der schon lange elfte Fuzzy-Match und stammen aus dem EU Korpus. Der 16. Kandidat ist zwar kurz, hat aber nur ,,sehr``, ,,gut`` und ,,man`` mit dem Anfragesatz gemeinsam.

Die Fuzzy-Matches (und auch die übrigen Kandidaten) zu diesem Beispielsatz sind nur sehr eingeschränkt oder gar nicht für die Übersetzung des Anfragesatzes nützlich. Lediglich die Phrasen ,,Schatten der Bäume`` und ,,die langen Schatten der Bäume`` lassen irgendeine Hilfe erwarten, die über eine reine Einzelwortübersetzung hinausgeht. Da selbst solche Kandidaten noch von der entwickelten Fuzzy-Match-Suche ermittelt werden, kann man hoffen, dass nur sehr wenige relevante Korpusstellen übersehen werden.^3.48

Fußnoten

... Fundstellen.^3.42

Der Anfragesatz muss nicht unter den ersten elf Treffern sein, wenn mindestens zwölf Exact-Matches vorhanden sind. Bei der Stichprobe trat dieser Fall aber nicht auf.

... Anfragetoken.^3.43

Genau genommen müsste man hier von den Tokentupel-IDs sprechen. Unter der Annahme, dass der IMS TreeTagger ein Token, das er einmal lemmatisieren konnte, nie mit ,,<unknown>`` annotiert, deckt die erstellte Grundformliste alle Tokentupel ab, in denen das Token auftritt. Im Bezug auf das Anfragetoken ist die Darstellung also korrekt. Jedoch ist die Vorstellung falsch, die Token, die mit einer Grundformliste aus der Liste der Grundformenlisten annotiert wurden, würden für die Suche im Korpus verwendet. Im Beispiel zu ,,fiel`` wird dies deutlich: Obwohl im Korpus das Token ,,Gefallen`` achtmal mit der Grundformliste ,,fallen, gefallen`` annotiert wurde, werden die anderen 29 Auftreten von ,,Gefallen`` bei einer Suche mit der Grundformliste ignoriert, da hier das Nomen vorliegt.

... stehen.^3.44

Diese Rangzahlen müssen in etwa halbiert werden, wenn sie mit einsprachigen Häufigkeitstabellen verglichen werden, da in KoKS die Häufigkeiten sprachübergreifend ausgezählt wurden. Die Auszählung und Verwendung der Tabelle ist auf diese Weise einfacher. Ein Problem sei aber nicht verschwiegen: Bei Token, die in beiden Sprachen auftreten, ist die so bestimmte Häufigkeit die Summe der Häufigkeiten in den Einzelsprachen. Unter den häufigsten 200 Token sind hier besonders Satzzeichen und die drei Token ,,Union``, ,,national`` und ,,international`` betroffen. Sie stehen auf zu hohen Rangplätzen. (Token wie ,,Land`` sind nur geringfügig betroffen, da sie im Englischen selten groß geschrieben werden.)

... übereinstimmen.^3.45

Alternativ könnte man nach der Bildung der $k$ elementigen Teilmengen der Anfragetoken diejenigen ausfiltern, die zu wenig seltene Wörter enthalten, um eine kleine Kandidatenmenge erwarten zu können. Zusätzlich könnte man verlangen, dass die Token im Anfragesatz eng zusammenstehen. (Die gleiche Bedingung könnte man auch an die zu findenen Sätze knüpfen. Mit den vorhandenen Indizes kann dies aber nicht effizient durchgeführt werden.) So wäre es möglich, nach Sequenzen von Wörtern offener und geschlossener Wortklassen, wie z.B. ,,im Schatten der Bäume``, zu suchen.

... eingesetzt.^3.46

() geben ein zeichenbasiertes Maß ,,Token Intersection`` an, dass im Nenner anstatt des Maximums das arithmetische Mittel verwendet (Formel 2 auf Seite 38). Im Nenner steht der Mittelwert der Längen der Zeichenfolgen. Der Bruch wurde mit zwei erweitert. Das sei die übliche Form. Wenn man für die Längen $\sum c_i(t)$ einsetzt und die Summen zusammenfasst, wird die Ähnlichkeit zum KoKS-Maß offensichtlich. erlauben zusätzlich, dass der Einfluss jedes Tokens unterschiedlich gewichtet wird.

... an.^3.47

Dort wird das Abstandsmaß $1-a$ betrachtet.

... werden.^3.48

Überprüfen könnte man dies, indem man $k$ weiter absenkt. Mit $k=2$ kommen im Beispiel 331 neue Kandidaten hinzu. Es tritt ein neuer Fuzzy-Match auf, der eine Ähnlichkeit von 23 % zum Anfragesatz hat und die Phrase ,,im Schatten eines Baumes`` enthält. Es werden also tatsächlich Stellen im Korpus übersehen. Man darf aber weiter hoffen, dass es nicht viele sind.