Approximativer Stringvergleich in selbstorganisierenden Trie-Strukturen

Meine Masterarbeit behandelt String-Anfragen an Lexika mit schiefer Verteilung, wie sie etwa beim Parsen von Texten vorliegt, d.h. einige Strings werden häufiger angefragt als andere und die interne Struktur der Strings ist ebenfalls schief, d.h. auf ein Zeichen im String folgen einige Zeichen häufiger als andere.

Betrachtet werden Lexika-Implementationen in Trie-Form nach Fredkin, de la Briandais und Clampett (Kapitel 2).

In Folgekapitel werden die beiden letzten Strukturen mit Mechanismen der Selbstorganisation (Move-to-Front, Transpose und Frequency Count für Listen-Tries, Simple Exchange, Move-To-Root und Splaying für TSTs) versehen, um sie für schiefe Anfragen zu optimieren. In Experimenten wird ihre Effizienz für reale Daten untersucht.

In einem weiteren Kapitel (4) werden verschiedene Mechanismen zum unscharfen Vergleich von Strings vorgestellt, wobei die Levenshtein-Damerau-Distanz sich als bestgeeignet unscharfe Anfragen an Lexika in Trie-Struktur erweist.

In einem abschließenden 5. Kapitel wird der unscharfe Stringvergleich in die selbstorganisierenden Trie-Strukturen implementiert und mit Experimenten untersucht, ob aufgrund der Selbstorganisation die Trefferqualität und die Geschwindigkeit der Antworten positiv beeinflusst wird.

Es zeigt sich, dass Selbstorganisation einen positiven Effekt auf unscharfe Stringanfragen an Lexika haben kann (Kapitel 6). Eine mögliche Anwendung hierfür wären Orthographie-Programme, die für Korrekturvorschläge alle bisherigen Anfragen an das Lexikon, also alle Anfragen des Textes bis zum gesuchten Wort, berücksichtigen und somit auch seltene Wörter, wenn sie Gegenstand des Textes sind, höher bewerten. Dem gegenüber steht der rechnerische Aufwand, der bei einer Selbstorganisation mit einkalkuliert werden muss.

Die im Rahmen der Arbeit entstandenen Perl-Programme sind als Prototypen zu betrachten. Sie sind keineswegs optimiert. Ziel war eher eine möglichst gut wartbare und "durchschaubare" Programmstruktur. Über eine Lizenz habe ich mir noch keine Gedanken gemacht ...

Weiteres ...

In einem weiteren Kapitel hatte ich den approximativen Stringvergleich in Finite State Transducern behandelt. Dieses Kapitel entfiel letztlich, Teile davon (wenn auch nicht der approximative Stringvergleich) sind in einer Hausarbeit zur Finite State Morphology zu finden.

Ein Programm zur Ermittlung von ähnlichen und unähnlichen Wörtern in einem Korpus gemäß der Levenshtein-Damerau-Distanz findet Ihr ebenfalls auf diesen Seiten.

Zuletzt aktualisiert am 15. November 2012