Indizierung

Die Struktur der KoKS-Datenbank erlaubt einen sehr schnellen Zugriff auf alle Segmente, die ein bestimmtes Tokentupel (Token, POS-Tag, Grundform, Sprache) enthalten. Die Datenbank kann dabei auch Listen von Tokentupeln verarbeiten, von denen eines im Segment auftreten muss, damit das Segment gefunden wird. Auf diese Weise können alle Segmente zu z.B. einer Grundform und Sprache unabhängig von POS-Tag und Token mit einer Datenbank-Anweisung abgefragt werden.

Komplexere Anfragen bereiten jedoch Probleme. Beispielsweise möchte man alle Segmente erfragen können, die eine Kombination von Wörtern oder Grundformen enthalten. Im KoKS-Projekt wurde diese Anfrage umgesetzt, indem außerhalb der Datenbank die Segmentnummerlisten der einzelnen Wörter geschnitten werden. Dies ist keine gute Lösung, da die Einzellisten sehr lang sein können und deren Übertragung von der Datenbanksoftware zur Anwendung ineffizient ist. Eine vom Autor dieser Arbeit gefundenen Lösung, die innerhalb der Datenbank die Listen schneidet, läuft um ein Vielfaches, aber nicht um Größenordnungen schneller als die KoKS-Lösung.^3.28

Die für die Anwendungen wichtigen Anfragen müssen also auf andere Weise beschleunigt werden. Im KoKS-Projekt, im Anschluss an den Projekt und im Rahmen dieser Arbeit wurden vom Autor verschiedene Indizes erstellt, die in Folgendem kurz vorgestellt werden.

Grundlagen

Die Zeilen einer Tabelle werden in einer Datenbank ungeordnet abgelegt, um die Datenhaltung möglichst einfach und anwendungsunabhängig zu halten.^3.29Neue Zeilen können sehr schnell hinzugefügt werden, da nur der notwendige Platz geschaffen werden muss. Für Anwendungen, die hauptsächlich Informationen zusammentragen, beispielsweise Ereignisse protokollieren, kann dies wichtig sein. Würden die Zeilen sortiert gespeichert, müssten weitere Verwaltungsstrukturen für jede neue Zeile angepasst werden.

Sollen Zeilen mit vorgegebenen Spaltenwerten in einer unsortierten Tabelle ausgelesen, verändert oder gelöscht werden, muss die gesamte Tabelle durchsucht werden. Bei großen Tabellen kann dies sehr viel Zeit in Anspruch nehmen. Anwendung, die diese Operationen verwenden, würden also von zusätzlichen Datenstrukturen, die den Zugriff auf Zeilen mit vorgegebenen Spaltenwerten beschleunigen, profitieren. Indizes dienen genau diesem Zweck. Der Benutzer (oder der Verwalter der Datenbank) kann angeben, zu welchen Spalten oder Kombinationen von Spalten Strukturen aufgebaut und gepflegt werden sollen, die spätere Anfragen beschleunigen.

MySQL verwendet eine spezielle Baumstruktur, den B*-Baum, für Indizes. Diese Struktur erlaubt ein effizientes Suchen, Verändern, Einfügen und Löschen von Indexeinträgen. Blendet man den Aspekt der Effizienz aus, kann ein MySQL-Index als alphabetisch (oder numerisch) sortierte Liste aller Werte der indizierten Spalte mit einem Verweis auf die Zeilen, die den jeweiligen Wert aufweisen, verstanden werden.^3.30Auf dieser Betrachtungsebene ist ein MySQL-Index wie ein Index eines Buches aufgebaut. Die Stichwörter entsprechen den Werten, die in der indizierten Spalte auftreten, und die angegebenen Seitenzahlen den Verweisen auf die Zeilen der Tabelle.

Die alphabetische Reihenfolge der Indexeinträge ermöglicht nicht nur ein schnelles Auffinden von Tabellenzeilen mit vorgegebenen Spaltenwerten. Auch Bereichsanfragen können mit solchen Indizes effizient ausgeführt werden. Wenn beispielsweise alle Zeilen mit Werten zwischen ,,Imperium`` und ,,Import`` gesucht werden, muss nur ein zusammenhängender Bereich im Index gelesen werden.^3.31Ebenso können alle Werte, die mit einem Präfix, z.B. ,,Imp``, beginnen, schnell gefunden werden. Von dieser Möglichkeit wird bei den weiter unten beschriebenen Indizes Gebrauch gemacht.

Die Indizes einer Datenbank verhalten sich völlig transparent. Man muss nur einmal angeben, dass sie erstellt werden sollen, und schon verwendet die Datenbank sie automatisch, um die Bearbeitung von Anfragen zu beschleunigen. Für die im folgenden beschriebenen Indizes gilt dies nicht. Sie sind spezielle Tabellen, die zwar innerhalb der Datenbank gespeichert sind, aber explizit in einer SQL-Anweisung eingebunden werden müssen. Ebenso muss die Anwendungssoftware dafür Sorge tragen, dass diese Tabellen konsistent zum Korpus gehalten werden.^3.32Das Nachschlagen innerhalb der Tabellen der manuellen Indizes erledigt die Datenbank wie für andere Tabelle auch über eigene Indizes.

Satzindex

Der einfachste, manuelle Index im KoKS-System listet alle Segmente auf. Im Regelfall sind dies Sätze, sodass hier vereinfachend von Sätzen gesprochen werden kann. Für jeden Satz werden die Token durch ein spezielles Zeichen getrennt zu einer Zeichenkette zusammengesetzt und zusammen mit der Segmentnummer in einer Tabelle aufgeführt. Um Speicherplatz zu sparen, wurden nur die ersten 56 Zeichen gespeichert. Die meisten Sätze können trotzdem eindeutig identifiziert werden. Um auch in den Fällen, in denen verschiedene Sätze mit der gleichen Wendung beginnen, eine möglichst kleine Treffermenge erhalten zu können, wird zusätzlich die Satzlänge in Token und die Sprache vermerkt.

Prinzipiell wären auch andere Eigenschaften der Sätze zum Einschränken der Treffermenge geeignet. Wenn die Eigenschaften so gewählt sind, dass unterschiedliche Sätze sehr selten die gleichen Eigenschaften haben, dann ist die Spalte, die die Satzanfänge enthält, zum Auffinden von Sätzen nicht nötig. Werden darüber hinaus die Eigenschaften auf den Wertebereich eines kurzen Datentyps der Datenbank abgebildet, dann belegt der Index sehr wenig Speicherplatz.

Abbildung: Ausschnitt aus dem Index für Satzanfänge

Abbildung zeigt einen Ausschnitt aus der Tabelle zusammen mit einer SQL-Anfrage, die die Einträge von ,,Imperium`` bis ,,Import`` mit der Sprache ,,Deutsch`` (kodiert mit dem Wert 1) auswählt und die Spaltennamen für die Ausgabe umbenennt.^3.33Die Spalte für die Sprache wurde nicht abgebildet, da sie in den ausgewählten Zeilen nur den Wert 1 hat. Zwei Zeilen enthalten englischen Text. Dies ist weder ein Fehler des Moduls für die Indexerstellung noch der KoKS Datenbank. Die POS-Tags und Grundformen sind die, die sich einstellen, wenn der englische Text vom IMS TreeTagger für das Deutsche getaggt wird. Für das Segment 422412 hat eine Recherche in den beim Taggen erstellten Dateien ergeben, dass mindestens ein deutsches Dokument einen englischsprachigen Anhang enthält.

Das Auffinden eines Satzes erfolgt nun, indem er mit der gleichen Funktion wie bei der Erstellung des Indexes auf eine maximal 56 Zeichen lange Zeichenkette abgebildet und die Anzahl der Token bestimmt wird. Mit diesen Daten wird dann in der Index-Tabelle nachgeschlagen. Sofern die 56 Zeichen nicht den gesamten Anfragesatz abdecken, müssen die Sätze, auf die verwiesen wird, noch daraufhin überprüft werden, ob sie tatsächlich identisch mit dem Anfragesatz sind.

Satzanfänge und -enden

Im Rahmen dieser Arbeit wurde festgestellt, dass sich die erstellte Tabelle für den Satzindex auch eignet, um Sätze mit vorgegebenen Satzanfang abzurufen. Das Satzpräfix wird dazu genauso wie die Anfragesätze beim Satzindex in eine Zeichenkette umgewandelt. In der Tabelle zum Satzindex wird dann eine Präfixsuche ausgeführt. Diese wird von der Datenbank effizient durchgeführt. Die Treffermenge wird durch die Vorgabe einer minimalen Tokenanzahl und der Sprache weiter reduziert. Analog zur Satzsuche müssen bei zu langer Anfrage die Ergebnisse, die der Index liefert, noch überprüft werden.

Für die Suche nach Satzenden wurde eine zweite Tabelle aufgebaut, die darin von der Satzindex-Tabelle unterscheidet, dass die Reihenfolge der Token vor der Erzeugung einer maximal 56 Zeichen langen Zeichenkette umgekehrt wird.

Grundformen und POS-Tags

Mit dem Modul für die Satzindizes können nicht nur Token indiziert werden. Auch die annotierten Grundformen und POS-Tags eignen sich.

Abbildung: Ausschnitt aus dem Index für Grundformfolgen am Satzende

Abbildung zeigt einen Ausschnitt aus dem Index für die Grundformfolgen am Satzende. Mit ihm können Sätze abgefragt werden, die auf eine vorgegebene Abfolge von Grundformen enden.

Bei den Grundformen tritt das Problem auf, dass je Token mehr als eine Grundform annotiert sein kann. Damit ein Satz mit jeder in Frage kommenden Grundformenfolge gefunden werden kann, muss jede mögliche Kombination in den Index aufgenommen werden. Die Anzahl der Kombinationen ist das Produkt der Anzahlen der Grundformen, die für jedes einzelne Token annotiert sind. Zwar weisen von den 271907 deutschsprachigen Segmenten nur 1047 mehr als 16 Kombinationen auf. Aber einige Segmente weisen zwischen 12288 und 134217728 Kombinationen auf. Betroffen sind vor allem große Segmente aus $n:1$ Alignment-Beads und Segmente, die umfangreiches Tabellenmaterial enthalten.

Um die Indizes für Grundformenfolgen an Satzanfängen und -enden in vertretbarer Zeit aufbauen zu können, werden nur soviele Grundformenlisten aufgeteilt, dass eine voreingestellte Maximalanzahl von Kombinationen (erst 192, später auf 32 reduziert) nicht überschritten wird. Eine Verbesserungsmöglichkeit wäre, jeweils zu prüfen, ob sich die Grundformalternativen überhaupt in den 56 tatsächlich indizierten Zeichen niederschlagen.

Teilmengen der Token eines Segments

Zum Finden von Fuzzy-Matches kann ein Satzindex nicht verwendet werden. Selbst wenn sowohl der Satzanfang- als auch der Satzendenindex verwendet wird, können Sätze nicht gefunden werdem, die am Anfang und Ende Unterschiede zum Anfragesatz aufweisen. Gewünscht ist, dass alle Sätze gefunden werden, die eine vorgegebene Anzahl von Token (oder Grundformen) mit dem Anfragesatz gemeinsam haben. Dieses Suchproblem ist bereits aus dem Information-Retrieval bekannt. In einem Translation Memory werden statt Dokumenten Sätze gesucht.

Mit den datenbankseitig vorhandenen Indizes kann die Suche nach Sätzen, die $k$ Token von $n$ gegebenen Token $T_1, ..., T_n$ enthalten, bereits durchgeführt werden, ohne die Sätze selbst aus der Datenbank auslesen zu müssen. Dazu werden für jede $k$ elementige Teilmenge ${T_{i_1}, ... T_{i_k}}$ der Anfragetoken die Menge der Satznummern der Sätze ermittelt, die die jeweiligen $k$ Token enthalten. Die Vereinigung dieser $\binom{n}{k}$ Mengen gibt die gesuchten Sätze an. Diese einzelnen Mengenoperationen gibt folgender Ausdruck wieder:

$$% \bigvee_{{(i_1, ..., i_k) \in {\mathbb N}^k} \atop {1 \leq i_1 ... ...leq n} } \bigcup_{1 \leq i_1 < ... < i_k \leq n} \bigcap_{j=1}^{k} R(T_{i_j}),$$

wobei $R$ ein Token auf die Menge der Satznummern der Sätze abbildet, in denen das Token vorkommt. $R$ kann mit einer einfachen SQL-Anfrage implementiert werden. Die Mengenoperationen können prinzipiell auch von der Datenbank ausgeführt werden. Im Rahmen dieser Arbeit^3.34wurde jedoch darauf verzichtet, da der Autor keine Erfahrungen darin hat, ob die verwendete MySQL-Datenbank erkennt, dass hier viele Zwischenergebnisse wiederverwendetet werden können. Die Mengenoperationen werden anwendungsseitig im Fuzzy-Matching Modul ausgeführt.

Das Laufzeitverhalten ist sehr schlecht, wenn die Mengenoperationen wie oben notiert ausgeführt werden, da dann $\binom{n}{k}$ Schnittmengen bestimmt werden müssen. Liegen die Mengen $R(T_i)$ als sortierte Listen vor, dann kann in O($n^2 m$) ($m$ sei die Länge der längsten Liste, d.h. $m=\max{\vert R(T_i)\vert}$) bestimmt werden, welche Satznummern mindestens $k$ mal auftreten. Dies wurde aber nicht implementiert, da eine Beschränkung von $k$ auf $k \leq 3$ vertretbar erschien.

Anpassungen sind notwendig, wenn in der Anfrage Token mehrfach auftreten dürfen. Man kann weiterhin mit obigen Mengenoperationen arbeiten, wenn statt mit Token mit Paaren bestehend aus Token und Nummer des Auftretens im Satz gearbeitet wird. Ein entsprechender Index müsste dazu aufgebaut werden.

Ein anderer Ansatz wurde in der Zeit zwischen KoKS-Projekt und der Erstellung dieser Arbeit verfolgt. Es wurden alle zwei- und dreielementigen Teilmengen von Token indiziert, die in Sätzen des Korpus vorkommen. Motivation ist, dass die Mengen $R(T_i)$ sehr groß sein können. Mit dem zusätzlichen Index können Mengen $R(T_i) \cap R(T_j)$ und $R(T_i) \cap R(T_j) \cap R(T_o)$ direkt abgerufen werden.^3.35Der Zeitbedarf für den Indexaufbau stellte sich jedoch als Problem heraus. Im Nachhinein kann vermutet werden, dass dies an den sehr langen Segmenten liegt, die beim Ausmultiplizieren der Grundformen bereits Probleme bereiteten. Alle beschriebenen Indizes wurden auch für die Suche mit Grundformen implementiert.

Anpassung für Grundformen und POS-Tags

Mit Grundformen oder POS-Tags kann auf gleiche Weise gesucht werden. Die notwendige Anpassung der Retrieval-Funktion $R$ erfordert nur einen Rückgriff auf andere Tabellen. Zur Erinnerung: Die Token sind nicht direkt mit der Korpustabelle verknüpft, sondern stehen in einer Tokentupel-Tabelle bestehend aus Token, Grundform, POS-Tag und Sprache. Wenn die Zeichenketten der Token, Grundformen und POS-Tags auf genau gleiche Weise mit der Tokentupel-Tabelle verknüpft wären, müsste nur der Name einer Tabelle in den Datenbankanfragen ersetzt werden. Leider ist dies nicht der Fall. Die Token stehen direkt in der Tokentupel-Tabelle, die Grundformen in einer Extratabelle und die POS-Tags in mehreren Tabellen (je Tagset eine Tabelle).

Suche nach POS-Tagfolgen

Die Suche nach POS-Tagfolgen wurde vorbereitet, da erwartet wurde, dass sie für diese Arbeit interessant werden könnte. Soweit ist es aber nicht gekommen, sodass sie nicht implementiert wurde.

Ein spezieller Index ist sinnvoll, da ein einfacher Ansatz, der das Retrieval aus dem vorangehenden Unterabschnitt nutzt und dann die Ergebnisse danach filtert, ob die POS-Tags in der richtigen Reihenfolge und zusammenhängend auftreten, zwei Probleme aufwirft. Zum einen sind die Zwischenergebisse sehr umfangreich. Beispielsweise dürfte $R_{POS}('$NN$')$ fast alle Satznummern des Korpus enthalten. Zum anderen dürfte auch das Endergebnis des Retrievals viele Sätze enthalten, die beim anschließenden Filtern verworfen werden müssen.

Aus dem Information-Retrieval ist der Ansatz bekannt, dass im Index zusätzlich zur Satznummer auch die Position des indizierten POS-Tags im Satz vermerkt wird. Die Reihenfolge und Kontinuität der POS-Tags kann dann ohne Auslesen der gesamten Sätze geprüft werden. Die Zahl der Überprüfung ändert sich damit aber nicht.

Wenn nicht einzelne POS-Tags, sondern alle Folgen von POS-Tags indiziert würden, könnte direkt im Index nachgeschlagen werden. Dies ist aber nicht praktikabel, da die Zahl der Sequenzen in einem Satz quadratisch von der Satzlänge abhängt. Mit einer Beschränkung auf kurze POS-Tagfolgen im Index kann dieses Problem gelöst werden. Die Anfrage kann weiterhin aus langen POS-Tagfolgen bestehen, wenn weiterhin nachgefiltert wird. Dazu muss die Anfragefolge in indexgerechte Stücke zerteilt werden. Freiheiten bei der Zerlegung könnten genutzt werden, um möglichst seltene POS-Tagfolgen für die Indexanfrage zu nutzen.

Fußnoten

... KoKS-Lösung.^3.28

Realisiert ist dies über eine $n$-malige Verknüpfung der Korpustabelle mit sich selbst, wobei $n$ die Anzahl der vorgegebenen Tokentupel ist, die im Segment auftreten sollen. Im KoKS-Projekt wurde davon ausgegangen, dass eine anwendungsseitige Lösung notwendig sei, vermutlich weil die von der eingesetzten Version der MySQL-Datenbanksoftware unterstützten Elemente der Abfragesprache SQL für unzureichend gehalten wurden. (Die Version unterstützt beispielsweise keine Subselects.)

... halten.^3.29

Der in MySQL verwendete Tabellentyp ,,MyISAM`` enthält zwar die Bezeichnung ISAM (index sequential access method, eine Methode, bei der die Daten sortiert abgelegt werden und ein dünn besetzter Index verwendet wird). MySQL setzt aber ohne Anweisung keine Indizes ein und erzeugt voll besetzte Indizes, wenn der Benutzer einen Index wünscht.

... werden.^3.30

MySQL unterstützt auch Indizes zu Kombinationen von Spalten. Die Sortierreihenfolge richtet sich dann nach der ersten in den Index einbezogenen Spalte. Bei gleichen Werten wird die nächste Spalte herangezogen. Typisches Beispiel ist die Kombination von den Spalten ,,Nachname`` und ,,Vorname`` in einer Tabelle mit Personendaten. Mehrdimensionale Suchbäume, z.B. $k$-d-Bäume, die beispielsweise für kartesische Koordinaten sinnvoll sind, werden von MySQL nicht unterstützt.

... werden.^3.31

Wenn die Blätter des B*-Baums nicht verkettet sind, dann stehen die Indexeinträge nicht explizit zusammen. Mit einer Traversierung des Baums startend mit dem Pfad zum ersten relevanten Eintrag und endend, sobald ein nicht relevanter Eintrag erreicht wird, kann der Indexbereich trotzdem effizient ermittelt werden.

... werden.^3.32

MySQL unterstützt keine Stored Procedures und Triggers.

... umbenennt.^3.33

Es wurden anwendungsunabhängige Spaltennamen gewählt, da erwartet wurde, dass das Modul für diesen Index auch in anderen Zusammenhängen benutzt werden könnte, in denen die ganzzahligen Beschränkungen andere Bedeutungen haben.

... Arbeit^3.34

Im KoKS-Projekt wurde nur der Sonderfall $k=n$ implementiert, bei dem die Vereinigung entfällt.

... werden.^3.35

Durch eine geschickte Verteilung der $k$ Anfragetoken auf $\lceil \frac{k}{3} \rceil$ Indexanfragen, die die Häufigkeit der Token gemessen am Gesamtkorpus berücksichtigt, kann man sehr kleine Ergebnismengen erhalten.