Die numerische Kodierung von Wörtern

Für die Übersetzung von Wörtern in Zahlenwerte kommen drei in der Informatik gebräuchliche Verfahren in Betracht, die in allgemeiner Form zum Beispiel von Knuth (1975), Wirth (1975) und von Sedgewick (1992) beschrieben werden: Die Binärsuche , Bäume  und die Hash-Kodierung . Bei der Binärsuche werden die zu kodierenden Wörter alphabetisch sortiert. Danach wird jedem Wort diejenige Nummer zugeordnet, die seiner jeweiligen Position in der Liste entspricht. Das Verfahren läßt sich gleichermaßen sowohl für den Fall realisieren, daß sich die sortierte Liste im Hauptspeicher befindet, als auch für den Fall, daß sie auf Platte ausgelagert wurde. Bei einer Anzahl von n Worteinträgen werden maximal ld(n) (Zweierlogarithmus) Speicherzugriffe benötigt, um die zu einem Wort gehörende Nummer zu finden. Der Hauptnachteil der Binärsuche besteht darin, daß bei einer Erweiterung des Vokabulars die hinzukommenden Wörter in die vorhandene Wortliste eingefügt werden müssen, und daß sich dabei die Nummern der jeweils nachfolgenden Wörter ändern.

Bei der Verwendung von Bäumen wird jedem Buchstaben eines Wortes eine Datenstruktur zugewiesen, die außer dem Buchstaben selbst einerseits einen Zeiger auf den nächsten Buchstaben des Wortes, andererseits einen weiteren Zeiger auf an der gleichen Position alternative Buchstaben anderer Wörter enthält. Identische Wortanfänge nutzen also dieselben Datenstrukturen. Bei Kodierung der Wörter auch, auf, da, das, der, deren und die sieht der Baum wie in Abbildung  dargestellt aus. Die Wörter werden in der Reihenfolge, in der sie in den Baum eingetragen werden, fortlaufend durchnummeriert.

  
Abbildung: Speicherung der Wörter auch, auf, da, das, der, deren und die in einem Baum. Die Endpunkte der Wörter sind mit einem Kreis markiert.

Durch die Mehrfachnutzung derselben Datenstrukturen für Wörter mit gleichen Anfängen ist dieses Verfahren trotz der benötigten Zeiger speicherplatzeffizient. Auch bei Vokabularergänzungen entstehen keine Probleme, da einem neu einzufügenden Wort einfach die nächste noch nicht verwendete Wortnummer zugeordnet wird. Für die Dekodierung, also die Umwandlung der Wortnummern in Wörter, genügt ein zusätzlicher Index, der jeder Nummer das zugehörige Wort bzw. - zur Speicherplatzersparnis - die Endposition im Suchbaum zuordnet. Ein Nachteil des Verfahrens ist, daß es viele wahlfreie Zugriffe erfordert und daher recht langsam wird, falls aus Mangel an Hauptspeicher die Datenstrukturen auf Platte ausgelagert werden müssen.

Demgegenüber kann das Hash-Verfahren so ausgelegt werden, daß es in erster Linie sequentiell zugreift. Beim Hashing (ßerhacken'') muß im Gegensatz zu den vorigen Verfahren zunächst eine Obergrenze für die Anzahl der Wörter im Vokabular festgelegt werden. Diese Obergrenze ist zwar frei wählbar, kann aber später nicht mehr ohne weiteres geändert werden. Aus Effizienzgründen wird eine Primzahl empfohlen. Jedem eingelesenen Wort wird mittels einer sogenannten Hash-Funktion, die die eingelesenen Zeichen numerisch interpretiert, ein eindeutiger (aber in der Regel nicht eineindeutiger) Zahlenwert zugewiesen, der sich durch Verwendung einer Modulo Funktion zwischen Null und der zuvor festgelegten Obergrenze bewegt.

  
Abbildung: Indexierung eines Vokabulares über eine Hash-Tabelle.

Die Hash-Funktion bildet damit die sehr große Anzahl möglicher Wörter auf eine sehr viel kleinere Anzahl von Positionen in der Hash-Tabelle ab. Die Hash-Funktion sollte so festgelegt werden, daß bei der zu erwartenden Menge von Wörtern der Bereich der Hash-Tabelle möglichst gleichmäßig mit Werten belegt wird.

Der für ein Wort berechnete Hash-Wert wird als Index für die sogenannte Hash-Tabelle verwendet. Stimmt das in der Hash-Tabelle an dieser Stelle eingetragene Wort nicht mit dem Ausgangswort überein (dieser Fall wird als Kollision  bezeichnet), so werden so lange die nachfolgenden Hash-Tabellenpositionen durchgegangen, bis entweder das Wort oder aber eine leere Tabellenposition gefunden wird. Im ersten Fall wird die Tabellenposition als Wortnummer verwendet, im zweiten Fall ist das Wort noch nicht im Vokabular enthalten und kann an der freien Tabellenposition neu aufgenommen werden.

Das Hash-Verfahren ist in der Praxis, solange die Hash-Tabelle zu weniger als 80% gefüllt ist, unter den drei vorgestellten Algorithmen der schnellste, insbesondere wenn die Platte als Speichermedium verwendet wird. Da an jeder belegten Position der Hash-Tabelle aber das längstmögliche Wort Platz finden muß, ist der Speicherplatzbedarf höher als bei der Baumsuche. Eine deutliche Ersparnis läßt sich jedoch erreichen, wenn die Hash-Tabelle nicht die Wörter selbst, sondern Zeiger auf die Einträge einer Worttabelle enthält. Eine solche Implementation liegt den im Rahmen dieser Arbeit verwendeten Algorithmen zugrunde (vergl. Abb. ). Die Größe der Hash-Tabelle wurde auf 1 000 001 festgelegt. Obwohl diese Tabelle in einigen Simulationen bis zu 98% belegt war, traten keine Geschwindigkeitsprobleme auf.