1           @L        MSJ.DFV                                                             PS300      R     C	MicrosoftSystem JournalMrz/April 1991	
Grundlagen der Rechtschreibprfung, Teil 1:
Die effektive Speicherung von Wrterlisten
Sicher haben Sie es schon benutzt, ein Programm mit der deutschen Bezeichnung Rechtschreibkorrekturprogramm. In den meisten Textverarbeitungsprogrammen ist mittlerweile ein solches Programm, ein Spellingchecker, enthalten. Falls Sie noch keine Erfahrungen mit solchen Programmen gesammelt haben, sollten Sie bei nchster Gelegenheit einmal eines ausprobieren. Sie werden sicher feststellen, da die Qualitt des Programms oder Programmteils nicht immer allen Ihren Wnschen gerecht wird. Ich mchte Ihnen deshalb in diesem und einem Artikel in der folgenden Ausgabe des Microsoft System Journals die Grundlagen fr einen funktionsfhigen Spellingchecker vorstellen. Sie knnen die darin vorgestellten C-Module dann dazu verwenden, sich einen eigenen Spellingchecker zu schreiben.
S
pellingchecker sind in den Vereinigten Staaten schon seit mehreren Jahren in durchaus annehmbarer Qualitt auf dem Markt. Diese Spellingchecker wurden und werden auf dem deutschen Markt zum Teil mit einem angeblich deutschen Wrterbuch ausgestattet und hier mit Textverarbeitungsprogrammen angeboten. Der Spellingchecker in Word 3.0 war zum Beispiel ein solcher Versuch. Mittlerweile haben die Entwicklern in den USA erkannt, da ein Spellingchecker auf die lnderspezifischen Gegebenheiten angepat werden mu. Der Spellingchekker von Word 5.0 ist deshalb bereits recht brauchbar.
Die ersten amerikanischen Spellingchecker mit deutschen Wrtern wurden mit einem Wrterbuch von 40.000 bis 50.000 Wrtern ausgeliefert. Diese Zahl erscheint hoch, aber in der Praxis ist diese Anzahl von Wrtern im Gegensatz zum Amerikanischen in der deutschen Sprache viel zuwenig. Solche Spellingchecker verdienen nicht, da Sie damit Ihre Zeit vergeuden; denn genau das werden Sie damit, weil Sie dem Programm selbst noch Unmengen von Wrtern beibringen mssen.
Das Konzept
Ich mchte Ihnen ein Konzept vorstellen wie Sie selbst einen Spellingchecker aufbauen knnen. Dieses Konzept hat in ausgefeilterer Form seine Bewhrungsproben bereits bestanden. Der darauf aufbauende Spellingchecker wurde bereits mehrere tausendmal in deutschen Textverarbeitungsprogrammen wie zum Beispiel im Textmaker und anderen in der Praxis eingesetzt. Die Verarbeitung erfolgt hier entweder im Batchbetrieb oder auch whrend der Eingabe eines Textes in der jeweiligen Textverarbeitung. Zustzlich wurde der Spellingchecker als selbstndiges Programm Korrekt! vertrieben.
Bevor ich auf die eigentliche Konzeption eingehe, mchte ich Ihnen unsere Gedanken vor der endgltigen Konzeption des Spellingchecker-Moduls vorstellen. Unser Spellingchecker sollte folgende Funktionen enthalten:
	Es mu die Mglichkeit bestehen, ein Wort gegen das Wrterbuch zu prfen.
	Der Spellingchecker mu die Mglichkeit bieten, fr ein nicht gefundenes und mglicherweise falsches Wort Vorschlge fr Wrter auszugeben. Dabei sollten mgliche Schreibfehler und Buchstabendreher so erkannt werden, da die Vorschlge mglichst eindeutig erfolgen.
	Der Spellingchecker sollte die Mglichkeit bieten, Wrter nachzuschlagen. Bei dieser Eingabe sollten Wildcards (* und ?) zulssig sein.
	Das Wrterbuch des Spellingcheckers sollte auch dazu verwendet werden knnen, um Trennungen von Wrter zu berprfen oder Vorschlge fr Trennungen durchzufhren.
Wir haben uns als erstes natrlich auf dem deutschen und amerikanischen Markt umgesehen und mit verschiedenen Spellingcheckern gearbeitet. Dabei stellten wir fest, da es mindestens zwei grundstzliche Anstze gibt. Beim ersten Ansatz wird mit einem relativ kleinen Wrterbuch versucht, die mglichen Wrter algorithmisch zu erzeugen und diese dann zu prfen. Stellen Sie sich bitte vor, Ihr Wrterbuch enthlt folgende Wrter: Tisch, Tuch, Kante, Stuhl. Mit diesen Wrtern knnen Sie nun neben den gespeicherten Wrtern auch folgende Wrter geprft werden: Tischtuch, Tischkante, Tuchkante und Stuhltisch. Wie Sie am letzten Beispiel sehen knnen, knnen durch einfache Zusammensetzung auch unsinnige Wrter kombiniert werden. Ein Spellingchecker, so wie wir uns Ihn vorstellen, sollte solche unsinnigen Wrter erkennen knnen. Durch entsprechende intelligente Algorithmen ist es sicher mglich, einen gewissen Teil dieser unsinnigen Wrter zu erkennen.
Der zweite Ansatz geht davon aus, da wichtigen deutschen Wrter auch tatschlich im Wrterbuch vorhanden sind. Dieser Ansatz schien uns der sinnvollere zu sein. Ein Wrterbuch fr die deutsche Sprache enthlt dann mindestens 150.000 bis 200.000 Wrter.
Die effiziente Speicherung
Wie kann man nun eine so groe Anzahl von Wrter so speichern, da Sie nicht mehrere Megabyte Platz auf Ihrer Festplatte beanspruchen und Sie trotzdem auf die Wrter mglichst schnell zugreifen knnen?
Natrlich haben wir mit Hilfe von Testprogrammen verschiedene Mglichkeiten und Varianten getestet. Eine Mglichkeit, um auf die Wrter schnell zuzugreifen, ist zum Beispiel ein binrer Baum. Dieses Verfahren hat leider den Nachteil, da der Index relativ gro werden kann. Der Zugriff auf bestimmte Wrter erfordert in der Regel mehrere Plattenzugriffe. Die Trennstellen in den Wrtern bereiten groe Schwierigkeiten. Wir haben diese Variante schlielich nicht weiter verfolgt.
Eine sehr interessante Mglichkeit besteht darin, auf die Wrter mittels eines Hash-Verfahrens zuzugreifen. Dieses Verfahren ist sehr schnell, bereitet aber die Schwierigkeit, eindeutige Schlssel fr 150.000 bis 200.000 Wrter zu erzeugen. Eine Datei, auf die mittels Hash-Algorithmus zugegriffen werden soll, kann hchstens zu 50 bis 60 Prozent gefllt werden. Wird dieser Fllgrad berschritten, kommt es zu vielen Kollisionen und der Vorteil des Hash-Zugriffs wird zum groen Teil wieder verbraucht.
Wir haben uns schlielich fr ein anderes Verfahren entschieden. Die Wrter, die ja in sortierter Form vorliegen, mssen in komprimierter Form gespeichert werden. Wenn Sie sich diesen Ausschnitt aus einer sortieren Wrterliste ansehen, werden Sie sicher eine Kompressionsmglichkeit erkennen.
Aachen
Aachener
Aal
Aale
aalen
aalglatt
Aaltierchen
Aar
Aarau
Aare
Aargau
Aargauer
aargauisch
Aaron
Die Wrter haben alle einen gleichen Anfang. Wenn man nun jeweils nur die Differenz zum vorhergehenden Wort und die Lnge der bereinstimmung zu diesem Wort speichert, kann man einen beachtlichen Teil der Zeichen einsparen. Aus den 86 Byte in diesem Beispiel werden nach der Kompression nur noch 36 Byte, was eine Einsparung von ungefhr 59 Prozent entspricht. Jedes dieser Wrter kann also mit ungefhr 2,57 Byte pro Wort gespeichert werden.
	
bereinstimmung	Wortrest
	
2	Aa		chen
6	Aachen		er
2	Aa		l
3	Aal		e
4	aale		n
3	aal		glatt
3	Aal		tierchen
2	Aa		r
3	Aar		au
3	Aar		e
3	Aar		gau
6	Aargau		er
6	aargau		isch
3	Aar		on
	

Wenn grundstzlich die ersten beiden Buchstaben einer Buchstabengruppe nicht gespeichert werden, da sie implizit ber einen Index (s.u.) vorhanden sind, knnen wir noch einige Bytes einsparen. Um die Lnge der bereinstimmung effektiv speichern zu knnen, haben wir uns folgendes Verfahren ausgedacht:
Vor jedes Wort wird ein Kontrollbyte gestellt, da den Wortanfang markiert, die Gro-/Kleinschreibung beschreibt und die bereinstimmungslnge enthlt.
Man kann nahezu alle deutschen Wrter mit den 26 Buchstaben und den Umlauten , ,  und dem  bilden. Wir speichern die Wrter im Wrterbuch nur in Kleinbuchstaben und legen die Grafie des Worts gesondert ab. Zustzlich lassen wir das Zeichen ' zu. Das Zeichen hexadezimal 0 wird reserviert. Wenn man nun einen Index fr das Wrterbuch erzeugt, der die ersten beiden Buchstaben als Schlssel verwendet, werden 32 * 32 oder 1024 Indexeintrge bentigt. Die Pointer im Index sind so organisiert, da jeder Pointer auf den Beginn einer Gruppe von zwei Buchstaben zeigt, also AA, AB, AC, AD ... WF, WG, WH ... Das Ende einer Buchstabengruppe wird durch ein Null-Byte gekennzeichnet, ebenso das Dateiende. Wenn ein Pointer Null enthlt, existiert kein Wort mit diesen beiden Buchstaben am Wortanfang, wie zum Beispiel bei .
Die Lngenangabe des ersten Worts einer Buchstabengruppe lautet immer 2, da diese beiden Buchstaben bereits durch den Index bekannt sind.
Es ist mglich, 32 Zeichen in nur 5 Bit darzustellen, es bleiben also 3 Bits fr andere Informationen erhalten.
Das Kontrollbyte ist wie folgt aufgebaut:

  7  6  5  4  3  2  1  0                                        Groschreibung = 1                   Trennstelle = 0                 Wortanfang = 1                    Beim Kontrollbyte die Anzahl der vom             vorherigen Wort zu bernehmenden             Buchstaben,             bei den Folgebytes die Buchstaben selbst              codiert wie folgt:             00           reserviert             01-26        a - z             27                        28                        29                        30                        31           '

Es ist durchaus mglich und sinnvoll, die Wrter weiter zu komprimieren. Die verbleibenden Wortreste eignen sich dafr ausgezeichnet. Bitte glauben Sie nicht, da hier die blichen Endsilben wie lich, keit oder ung die beste Wahl sind. Um diese Wortendekompression zu optimieren, mssen Sie Statistiken ber Ihre Wrterlisten per Programm erstellen. Denkbar aber hier aus Platzgrnden nicht dargestellt, ist die Verwendung der 127 Wortendungen, die die grte Ersparnis bei der Kompression bringen.
Der Erfolg der Kompression zeigt sich nicht nur in einem drastisch reduzierten Wrterbuch auf der Festplatte, sondern auch die Verarbeitunggeschwindigkeit bei der Wortprfung profitiert davon.
Das Wrterbuch
Ich habe Ihnen jetzt ein mgliches Grundgerst fr den Aufbau eine Wrterbuchs fr einen Spellingchecker vorgestellt. Mit dieser Version des System Journals erhalten Sie die Wrterliste TEST.DIC mit ungefhr 14.000 Wrtern, die Sie als Basis Ihres eigenen Wrterbuchs verwenden und erweitern knnen. Bitte denken Sie daran, da die Wrterliste gem der oben beschriebenen Sortierreihenfolge sortiert sein mu. Das DOS-Programm SORT knnen Sie dafr nicht verwenden, da SORT keine eigene Sortierreihenfolge zult. Auerdem kann der DOS Sort auch nur Dateien mit einer Gre von 64 Kbyte verarbeiten.
Wir haben natrlich fr unsere groen Prfprogramme deutsche Wrterbcher erstellt, die bis zu 250.000 verschiedene deutsche Wrter enthalten. Aus diesem Wortschatz ist es leicht mglich, auch Wrterbcher zu erstellen, die nur 50.000, 100.000, 150.000 Wrter enthalten.
Das Erstellen und Prfen der Wrterbcher ist eine enorm groe Arbeit und hat sich bei uns ber einen sehr langen Zeitraum hingestreckt. Dabei haben wir darauf geachtet, da nicht nur Wrter aus Zeitungsartikel erfat wurden, sondern da ein mglichst groes Spektrum der deutschen Sprache abgedeckt wurde.
Es gibt deutsche Spellingchecker, bei denen man beim genaueren Ansehen sofort bemerkt, da nur Megabytes von Zeitungsartikeln gescannt wurden. Andere haben Ihre Wrterbcher dadurch aufgeblasen, da sie Beugungen von Wrtern maschinell erzeugt und diese Wrter dann ins Wrterbuch aufgenommen haben, mit allen mglichen Fehlern. Hier ist jedoch mehr Einsatz erforderlich, denn das wesentliche Qualittskriterium fr einen deutschen Spellingchekker ist nun einmal das verwendete Wrterbuch.
Das Programm zur Erstellung einer Wrterbuchdatei
Im folgenden werde ich Ihnen das Programm CreateWB erlutern, da zum Aufbau des Wrterbuchs vorgesehen ist (Listings 1 und 2).
Zuerst wird in CreateWB die bliche Identifizierungsmeldung auf dem Bildschirm ausgegeben. Mit der Funktion onexit wird eine Routine fr das Programmende vereinbart. Diese Routine hat die Aufgabe, die verwendeten Dateien zu schlieen. Eigentlich wre es nicht notwendig, die Dateien ordnungsmig zu schlieen, da der Standardprogrammrahmen in C-Programmen dies ohnehin durchfhrt. Aber im Sinne von sauberen Programmen werden die Dateien, die erffnet worden sind, auch wieder geschlossen. Die Funktion onexit bietet fr alle Programme eine sehr saubere Mglichkeit, zum Programmende Aufrumarbeiten durchzufhren, auch wenn die Beendigung von verschiedenen Stellen im Programm erfolgt.
Willfried:Prfen: Organisation der Festplatte!!!!!!
Nach dem ffnen der Ein- und Ausgabedateien wird mit der Funktion setvbuf der interne Buffer fr die High-Level-File-Funktionen auf einen wesentlich greren Buffer gesetzt. blicherweise ist eine Festplatte mit Sektoren zu je 512 Byte organisiert. Diese Vernderung bringt ganz besonders bei sequentieller Verarbeitung durchaus bemerkbare Performance-Steigerungen, vorausgesetzt man kann den Speicherplatz fr die notwendigen Buffer dafr entbehren.
Mit der Funktion access wird sehr effizient festgestellt, ob die Ausgabedatei bereits besteht. Falls dies der Fall ist, wird eine entsprechende Meldung ausgegeben und unter Umstnden das Programm beendet. Anschlieend wird der Datei-Header geschrieben, das eigentliche Wrterbuch aufgebaut, der Header mit den Indexinformationen komplettiert und eine Statistik ber die gesamte Verarbeitung ausgegeben.
Die Funktion SchreibInitHeader hat die primre Aufgabe, den Platz fr die Indexinformationen zu reservieren.
In AufbauWoerterBuch wird die komplette Eingabedatei eingelesen. Da mit fgets gelesen wird, mu das nachfolgende \n am Wortende berschrieben werden. Nach einigen Prfungen und Wandlungen wird das einzelne Wort in die Ausgabedatei geschrieben. Ist die gesamte Datei abgearbeitet, wird zustzlich eine hexadezimale 0 als Dateiendekennzeichen geschrieben. Die Anzahl der Wrter wird in das entsprechende Feld in der Header-Struktur bertragen.
In der Funktion UpdateHeader wird wieder auf den Anfang des Wrterbuchs positioniert. Dort wurde am Anfang der Verarbeitung ein Dummybereich geschrieben. Dieser Dummybereich wird nun mit realen Daten berschrieben.
Zum Ende der Verarbeitung werden mit der Funktion AusgabeStatistik Statistiken ber das gesamte Wrterbuch auf dem Bildschirm ausgegeben.
Die Funktion TestSortfolge wird verwendet, um zu berprfen, ob die Wrter in der korrekten Sortierreihenfolge eingelesen werden. Das aktuelle und das vorherige Wort werden in das interne Format konvertiert und mit strcmp verglichen. Alle Vergleiche innerhalb des Programms werden mit den Stringvergleichsfunktionen der Standard-Library durchgefhrt. Da in der internen Darstellung der Code 0 nicht verwendet wird, knnen diese Funktionen verwendet werden, obwohl es sich nicht mehr um lesbare ASCII-Zeichen handelt.
Die interne Darstellung der Wrter, die letztendlich auch ins Wrterbuch bernommen wird, wird von der Routine KonvertWort durchgefhrt. In dieser Funktion ist als statische Variable eine bersetzungstabelle definiert. Mit der Funktion bsearch wird mittels binren Suchen fr jedes Zeichen des Eingabeworts der entsprechende interne Code ermittelt. Das Wort in der internen Darstellung wird an den Aufrufer zurckgegeben. Ich habe das Umwandeln der ASCII-Zeichen hier mit bsearch realisiert, da diese Routine auch bei anderen Gelegenheiten ntzlich verwendet werden kann.
Die Routine Vergl ist die Vergleichsroutine, die die Vergleiche fr bsearch durchfhrt. Diese und die Routine main sind explizit mit _cdecl deklariert, damit man mit dem Microsoft C-Compiler 6.0 die Option -Gr (_fastcall) verwenden kann. Bei Verwendung dieser Aufrufkonvention versucht der Compiler einige der Parameter der Funktion ber Register und nicht ber den Stack zu bergeben, zustzlich bereinigt die gerufene Funktion den Stack, falls das notwendig sein sollte. Die Grafie des Funktionsnamens bleibt erhalten, es wird nur statt des bei Microsoft blichen Unterstrichs, das Zeichen @ vor den Funktionsnamen gesetzt. Diese neue Aufrufkonvention kann bei Routinen mit wenigen Parametern, die aber hufig aufgerufen werden, deutliche Performancesteigerungen bringen.
InserWort schreibt das Wort in der verdichteten Form in das Wrterbuch. Zuerst wird das neue Wort mit Hilfe der Funktion KonvertWort in die interne Form gebracht. Danach wird geprft, ob eine neue Buchstabengruppe beginnt, das heit, die ersten beiden Buchstaben sind zum vorhergehenden Wort unterschiedlich. Beginnt mit dem Wort eine neue Buchstabengruppe, wird gem der aufgestellten Konvention eine hexadezimale Null als Trennzeichen in das Wrterbuch eingetragen. Dann mu die aktuelle Position im Wrterbuch gelesen und in das entsprechende Indexfeld eingetragen werden. Die bereinstimmungslnge wird ermittelt, sie ist immer mindestens zwei Zeichen lang. Diese Informationen werden mit der Funktion SchreibFlag als Wort-Header und anschlieend der Wortrest mit der Funktion SchreibWort in das Wrterbuch geschrieben.
Nur aus einem return mit der Adresse auf das entsprechende Indexfeld besteht die Funktion CalcPos. Die entsprechende Position im Index wird errechnet, indem der Wert des ersten Buchstaben minus 1 mit 32 multipiziert wird. Zu diesem Wert wird der Wert des zweiten Buchstaben minus 1 addiert. In C lt sich dieser Ausdruck sehr einfach niederschreiben.
Die Funktion SchreibFlag hat die Aufgabe, das Kopfbyte vor jedem Wort im Wrterbuch zu erzeugen. Das Kopfbyte enthlt die Restlnge * 8, oder um 3 Bit nach links geshiftet, plus das Bit, das den Wortanfang markiert. Zustzlich kann das Bit fr die Groschreibung gesetzt sein. Dieses Byte wird vor jedem Wort im Wrterbuch geschrieben.
Die letzte Routine, die ich beschreiben mchte, ist die Funktion SchreibWort. Sie hat die Aufgabe, den Wortrest in das Wrterbuch einzutragen. Zustzlich werden noch folgende Daten fr die Statistik gewonnen: Es wird die Lnge das lngsten und des krzesten Wort in entsprechende Felder gespeichert, der lngste und der krzeste Wortrest wird fr die Statistik festgehalten.
In dieser Routine ist Debugcode enthalten, der durch bedingte Compilerung (mit dem Schalter -DTesten) aktiviert werden kann. Bei Programmen, die intern eine andere Reprsentation ihrer Daten verwenden, sind die Debugger, wie zum Beispiel Codeview, nur noch zum Teil geeignet. Die gute alte Methode mit printf, wobei die Aufgabe in eine Datei umgeleitet wird, hat hier seine Berechtigung und ist zum Teil zwingend erforderlich.
Bis zum nchsten Mal
In der nchsten Ausgabe, werde ich Ihnen eine Funktion vorstellen, die eingegebene Wrter mit Ihrem Wrterbuch abgleicht. Zustzlich stelle ich Ihnen ein Programm vor, das Anagramme lsen kann. Bei der Zentralroutine, dem Finden von Wrtern im Wrterbuch, werde ich auf interessante Aspekte beim sequentiellen Suchen eingehen, die auch fr andere Aufgaben ntzlich sein knnen.
Willfried Frber

Willfried Frber ist Geschftsfhrer der ISAR Software GmbH. Er war bereits an der Entwicklung mehrerer Rechtschreibprfer beteiligt, die in verschiedenen deutschen Textverarbeitungen eingesetzt werden. Darber hat die Firma ein ausgefeiltes dBase-kompatibles Datenbanksystem entwikkelt.

Bild 1:Die Bildschirmausgabe beim Lauf von CreateWB.
Listing 1:SPELL.H
Listing 2:CREATEWB.C

܀      y    w       s    q       l W  p  h 
  
  f   -  d "  $  ` '    F E@	 D	'  '  y .  .  w /  /  u 0  0  s `1  1  o 1  1  m p3  v3  k 5  5  i h5  y5  g  Gy5  5  5  y 5  5  w 57  A7  u 08  @8  s 8  8  q b9  h9  o ;  ;  m ;  ;  k q<  q<  x<  y <  <  w =  !=  u D=  H=  s [=  a=  q =  =  o =  =  m ?  ?  k _@  j@  i j@  B  B  y B  C  w 5C  ;C  u C  C  s D  D  q F  'F  o G  G  m H  H  k @L        i    g   b +  ` /  ^   \ Y         !@ ! !@             ! H  H?g Q             Y  f  v 
  t     r   r p
  r   r      !@ 
!  !  !  !  !        !  !      C? 	    v   t         r   r   r   r  !@ !  !  !  !  !  !  !  !      E? 	    y   y   y   y %  y +  y 3  y =  y I  y P  y  !  !  !  !  !  !  !  !  !  !  E
P      y -  w 0  u <  s J  s S  s ]  s h  s  
!  !<  !  !<  !  !  !  !  !  !  ?e?e	h  v  y   y   y   y   y   y   y   y   y  !  !  !  !  !  !  !  !  !  !  ?e??	    y   w        x!  !  "  "  u  !<  !x  !  !  !  !  !  !  !x  !  ?IIe	"  $  e $  c &  K'  ['  ^ )  \ *   !  !x  !  !  !@ !  !  !  ? I G              
  *  ,  -  $.  k .  i `1  1  d _3  4   !  !  !@ !  !  @  !  	!   ?Y      @@4  e5  %7  7  8  :  <  ?  'C  D  E   !  
!  !  !  !                               @
E  WG  I  I  v J  t J  r J  r K  r K  r L  m                                                         G? 	L  %L  v =L  v ?L  @L  AL                                                                                  G?  
     l
    1  G  K        *       \                         K   <   K   K   9 @ A B C D L T Grundlagen fr die Rechtschreibprfung Frber     01.22.9112.22.90K  