Unix spell lief in 64 KB RAM

• Das Unix-spell von AT&T aus den 1970er-Jahren musste ein 250-KB-Wörterbuch im 64-KB-RAM des PDP-11 schnell durchsuchen; Douglas McIlroy löste das nicht mit allgemeiner Kompression, sondern indem er die Eigenschaften der Daten ausnutzte
• Steve Johnsons früher Prototyp war plattenbasiert und daher langsam sowie wenig treffsicher, doch McIlroy reduzierte das Wörterbuch durch Stemming auf etwa 25.000 Wörter und verbesserte so Performance und Genauigkeit
• Die erste In-Memory-Struktur war ein von Dennis Ritchie implementierter Bloom filter; mit einer Tabelle von 400.000 Bit und 11 Hash-Funktionen erreichte er eine False-Positive-Rate von etwa 1/2000 und kam ohne zusätzliche Wörterbuchabfrage aus
• Als das Wörterbuch auf 30.000 Wörter wuchs, ließen sich die Speichergrenzen mit dem Bloom filter allein kaum noch einhalten; daher wurden 27-Bit-Hashes sortiert und die Hash-Differenzen mit Golomb-Codes komprimiert
• Die finale Implementierung teilte die komprimierte Differenztabelle für schnellere Lookups in mehrere Bins auf und ermöglichte mit etwa 14 Bit Speicherbedarf pro Wort eine schnelle Rechtschreibprüfung innerhalb von 64 KB

---

Die Speicherbeschränkung von Unix spell

• Das Kernproblem bestand darin, ein 250-KB-Wörterbuch in einer Umgebung mit 64 KB RAM schnell durchsuchen zu können
• Selbst mit moderner Kompression wie gzip -9 lässt sich diese Datei nicht unter 85 KB verkleinern
• Auf dem PDP-11 der 1970er-Jahre konnte das gesamte Wörterbuch nicht in den Speicher geladen werden, und plattenbasierte Lookups waren langsam
• McIlroy entwarf statt allgemeiner Kompression eine spezialisierte Datenstruktur, die die Struktur und Wahrscheinlichkeitsverteilung der Wörterbuchdaten ausnutzte

Frühes Unix spell und Wörterbuchverkleinerung durch Stemming

• Als AT&T Unix als Textverarbeitungssystem für die Patentabteilung vorschlug, wurde eine Rechtschreibprüfung benötigt
• Steve Johnson schrieb 1975 den ersten Prototyp von Unix spell; Jon Bentley berichtete, diese Arbeit sei an einem Nachmittag entstanden
• Die frühe Version zerlegte Eingabedateien in einen Wortstrom, entfernte Zahlen und Sonderzeichen, wandelte alles in Kleinbuchstaben um, sortierte, entfernte Duplikate und prüfte dann im Plattenwörterbuch, ob Wörter vorhanden waren
• Der einfache plattenbasierte Lookup war langsam und zudem wenig genau
• McIlroy entwarf zwei Teile neu, um Performance und Genauigkeit zu verbessern
  • einen Algorithmus, der Präfixe und Suffixe entfernt und Wörter auf ihren Stamm reduziert
  • eine komprimierte Datenstruktur, die das Wörterbuch für schnelle Lookups im Speicher hält

Algorithmus zum Entfernen von Präfixen und Suffixen

• McIlroys Stemming-Verfahren entfernte wiederholt häufige Präfixe und Suffixe aus einem Wort und prüfte anschließend, ob das reduzierte Wort im Wörterbuch stand
• Beispielsweise wird misrepresented durch Entfernen der Präfixe mis, re und des Suffixes ed zu present reduziert
• Wenn present im Wörterbuch steht, wird das ursprüngliche Wort nicht als Tippfehler markiert
• Dieses Verfahren war nicht zu 100 % korrekt und konnte manche Tippfehler durchlassen, galt damals aber als akzeptabel
• Zusätzlich wurden Ausnahmeregeln implementiert, um häufige Fehler zu vermeiden
• Das finale Wörterbuch schrumpfte auf 25.000 Wörter und hatte damit eine Größe, die mit einer gut entworfenen Datenstruktur im Speicher gehalten werden konnte

Lookup auf Basis eines Bloom filters

• Die erste von McIlroy verwendete In-Memory-Struktur war ein Bloom filter, der in damaligen Veröffentlichungen als „superimposed code scheme“ bezeichnet wurde
• Der Aufsatz zum Bloom filter erschien 1970, Unix spell wurde Mitte der 1970er-Jahre entwickelt
• Diese Implementierung stammte von Dennis Ritchie
• Ein Bloom filter initialisiert eine Bit-Tabelle mit 0 und wendet dann für jedes Element mehrere Hash-Funktionen an, um die entsprechenden Bits auf 1 zu setzen
• Beim Lookup werden dieselben Hash-Funktionen angewendet
  • Ist auch nur ein Bit 0, existiert das Element nicht
  • Sind alle Bits 1, kann das Element existieren, es bleibt aber die Möglichkeit eines False Positive
• Ein gewöhnlicher Bloom filter benötigt zur Behandlung von False Positives einen Lookup im echten Wörterbuch; bei einer Rechtschreibprüfung stehen jedoch die meisten Wörter im Wörterbuch, sodass solche vollständigen Wörterbuchabfragen häufig würden
• McIlroy senkte die False-Positive-Rate weit genug, um auf einen echten Wörterbuch-Lookup zu verzichten
  • Zulässige False-Positive-Rate: 1/2000
  • Anzahl der Wörter im Wörterbuch: 25.000
  • Größe der Bit-Tabelle: 400.000 Bit
  • Anzahl der Hash-Funktionen: 11
• Mit dieser Kombination wurde eine False-Positive-Rate von ungefähr 1/2000 erreicht

Grenzen des Bloom filters und komprimierte Hashes

• Der Bloom-filter-Ansatz wurde eine Zeit lang genutzt, doch mit fortlaufend neuen Wörtern wuchs das Wörterbuch von 25.000 auf 30.000 Wörter
• Um dieselbe False-Positive-Rate zu halten, wäre eine größere Bit-Tabelle nötig gewesen, was wegen der Speichergrenze schwierig war
• McIlroy wechselte zu einem Ansatz, bei dem statt einer vollständigen Hash-Tabelle nur die Hashwerte der Wörter gespeichert wurden
• Beim Lookup wird der Hash des Eingabeworts berechnet und anschließend geprüft, ob er in der gespeicherten Hash-Liste vorkommt
• Um Hash-Kollisionen hinreichend unwahrscheinlich zu machen, war ein ausreichend großer Hash-Code nötig
  • Die Wörterbuchgröße v beträgt etwa 30.000, also ungefähr 2^15
  • Die zulässige Kollisionswahrscheinlichkeit ist 1 / 2^12
  • Die erforderliche Hash-Größe beträgt 27 Bit
• 30.000 Hashes mit je 27 Bit passten nicht in die 64 KB RAM des PDP-11, weshalb Kompression zwingend nötig war

Theoretische Kompressionsgrenze

• McIlroy berechnete zunächst die theoretische minimale Bitzahl, die zum Speichern einer Menge von Hash-Codes nötig ist
• Wenn die Hash-Code-Größe b Bit beträgt, gibt es 2^b mögliche Hash-Codes; die Anzahl der Möglichkeiten, daraus v eindeutige Hash-Codes auszuwählen, wird in Informationsmenge umgerechnet
• Für die Berechnung wurden die Stirling-Näherung und die vereinfachende Annahme v « 2^b verwendet
• Setzt man v=30.000 und b=27 ein, ergibt sich als Minimum zum Speichern eines einzelnen Hash-Codes 13,57 Bit
• Das ist etwa 50 % kürzer als der ursprüngliche 27-Bit-Hash und liegt in einem Bereich, der in den Speicher des PDP-11 passen konnte

Speichern und Nachschlagen von Hash-Differenzen

• McIlroy komprimierte nicht die ursprünglichen Hash-Codes direkt, sondern speicherte die Differenzen zwischen sortierten Hash-Codes
• Ein Beispiel:

sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12

• Das Speichern von Differenzen hatte zwei Vorteile
  • Differenzwerte sind kleiner als die ursprünglichen Hash-Codes
  • Dieselben Differenzwerte können bei mehreren Paaren von Hash-Codes wiederholt auftreten
• Beim Lookup wird der Hash des Eingabeworts berechnet und die Differenzen werden von vorn aufsummiert
  • Entspricht die kumulierte Summe dem Eingabe-Hash, ist er vorhanden
  • Überschreitet die kumulierte Summe den Eingabe-Hash, ist er nicht vorhanden
• Der Speicherbedarf sinkt, doch da die komprimierten Werte von vorn dekodiert und aufsummiert werden müssen, kann der Lookup langsamer werden

Modellierung der Hash-Differenzen als geometrische Verteilung

• Verlustfreie Kompression ist besonders effizient, wenn häufige Werte kurze Codes und seltene Werte lange Codes erhalten
• Eine allgemeine Kompression auf Basis einer Wahrscheinlichkeitstabelle passte nicht zu McIlroys Randbedingungen
  • Eine Wahrscheinlichkeitstabelle für etwa 30.000 Symbole im Speicher zu halten, hätte den Kompressionsgewinn zunichtegemacht
  • Um Häufigkeiten und Wahrscheinlichkeiten der Differenzwerte zu berechnen, wäre eine aufwendige plattenbasierte Struktur nötig gewesen
• McIlroy nutzte aus, dass Hash-Differenzen einer geometrischen Verteilung folgen
• Der Hash-Raum umfasst 2^b Positionen, in denen v Hash-Codes verteilt sind
  • Die Wahrscheinlichkeit, dass an einer Position ein Hash liegt, ist q = v / 2^b
  • Die Wahrscheinlichkeit, dass sie leer ist, ist p = 1 - v / 2^b
• Eine Differenz k entsteht, wenn die k-1 Positionen nach einem Hash leer sind und an der k-ten Position der nächste Hash liegt
• Daher beträgt die Wahrscheinlichkeit der Differenz k p^(k-1)q, was der Form einer geometrischen Verteilung entspricht

Differenzkompression mit Golomb-Codes

• McIlroy komprimierte die Hash-Differenzen mit Golomb-Codes, die sich für geometrisch verteilte ganze Zahlen eignen
• Golombs Aufsatz von 1965 lieferte ein einfaches Lauflängencodierungsverfahren für Werte mit geometrischer Verteilung
• Da die Wahrscheinlichkeit in einer geometrischen Verteilung exponentiell abnimmt, lassen sich Werte in Blöcke der Größe m gruppieren, wobei die Codelänge mit jedem weiteren Block um 1 Bit steigt
• Die Implementierung von Unix spell verwendete einen anderen, etwas komplexeren, aber effizienten Encoding- und Decoding-Algorithmus als das Verfahren aus Golombs Aufsatz
• Die ursprüngliche SVR4-Implementierung ist an folgenden Stellen einsehbar
  • Encoding-Implementierung
  • Decoding-Implementierung
• Golomb-Codes komprimieren die Hash-Differenzen auf eine erwartete Codelänge von 13,60 Bit pro Wort
• Das liegt sehr nah am theoretischen Minimum von 13,57 Bit

Bin-Aufteilung für höhere Lookup-Geschwindigkeit

• Würde man nur die komprimierte Differenztabelle verwenden, müsste beim Lookup von Anfang an dekodiert und aufsummiert werden, was langsam wäre
• Die finale Implementierung von Unix spell teilte die Differenztabelle in M Bins auf
• Beim Lookup wird zuerst das passende Bin gefunden und nur darin gescannt
• Dieser Ansatz erhöht die Suchgeschwindigkeit um den Faktor M
• Dafür müssen allerdings Bin-Pointer gespeichert werden, was zusätzlichen Speicherbedarf von log₂M Bit pro Wort verursacht
• Der gesamte Speicherbedarf stieg auf etwa 14 Bit pro Wort, wurde damit aber zu einem Kompromiss, der innerhalb des Speicherbudgets deutlich schnellere Lookups bot

Was Unix spell über Design unter Beschränkungen zeigt

• Unix spell ist ein Designbeispiel, das Bloom filter, Informationstheorie, Wahrscheinlichkeitstheorie und Golomb-Kompression kombiniert
• Die Entwicklung verlief in folgenden Schritten
  • Mit einem Bloom filter wurde eine niedrige False-Positive-Rate erreicht
  • Als das Wörterbuch wuchs, erfolgte der Wechsel zu komprimierten Hashes
  • Die theoretische minimale Bitzahl für das Speichern von Hashes wurde berechnet
  • Die Verteilung der Hash-Differenzen wurde erkannt
  • Mit Golomb-Codes wurde eine nahezu optimale Kompression erreicht
  • Durch Bin-Aufteilung wurden Lookups mit nur geringem zusätzlichem Speicher-Overhead beschleunigt
• Moderne Rechtschreibprüfungen verwenden andere Techniken wie Edit Distance oder Sprachmodelle, doch Unix spell bleibt ein Beispiel dafür, wie theoretisches Verständnis und praktische Beschränkungen zu einem effizienten System kombiniert werden können

[GN⁺]

Meinungen auf Hacker News

• Man kann auch mit sehr wenig RAM einen Spellchecker mit externem Speicher bauen: Man sortiert die Wörter im Dokument, entfernt eindeutige Wörter und führt sie dann mit einem sortierten Wörterbuch zusammen, sodass nur die fehlenden Wörter übrig bleiben.
  Ich hatte diese Methode als BASIC-Beispiel in Creative Computing gesehen und sie auf einem TRS-80 Color Computer zum Laufen gebracht, auf dem deutlich weniger als 32 KB RAM verfügbar waren. Deshalb musste ich beim Titel sofort daran denken.
  Damals brachte Turbo Lightning die Leute zum Staunen: Ein komprimiertes Wörterbuch passte neben andere laufende Programme auf den PC und prüfte die Rechtschreibung während der Eingabe.
  PCs hatten zwar die 640-KB-Grenze, aber um andere Programme nicht zu stören, durfte man nur einen Teil davon verwenden; und in der frühen PC-Zeit war es auch aus Kostengründen nicht einfach, diesen Speicher voll auszubauen.

  • Im Artikel wird diese Alternative ebenfalls als erster Proof of Concept behandelt und ihre Nachteile werden genannt: „Wegen der einfachen Implementierung war die Genauigkeit nicht hoch, und weil Wörterbuch-Lookups von der Disk erfolgen mussten, war sie langsam.“
  • Offenbar nutzte man aus, dass viele Wörter wiederholt vorkommen, um die Byte-Zahl niedrig zu halten. Auf dem alten C=64 wurde es schon bei Texten von mehr als ein bis zwei Seiten problematisch, weil allein der Dokumenttext den Speicher sprengen konnte; eine sortierte zweite Kopie vorzuhalten wirkte wie ein ziemlicher Luxus.
    Man hätte zwar auch zuerst eine Arbeitskopie auf Disk speichern, sie sortieren, vergleichen und anschließend wieder laden können, aber C=64-Entwickler hätten eine solche Strategie vermutlich vermieden, weil das Disk-Interface viel zu langsam war.

• Es gibt eine Passage, wonach Bloom-Filter damals noch nicht Bloom-Filter hießen und Douglas sie in seinem Paper als „superimposed code scheme“ bezeichnete; ein Bloom-Filter ist jedoch ein bestimmter Typ eines superimposed code.
  Calvin Mooers entwickelte in seiner MIT-Masterarbeit in den 1940er-Jahren, direkt von Shannon beeinflusst, randomisiertes superimposed coding weiter.
  Bournes hervorragendes Buch „Methods of Information Handling“ von 1963 enthält die mathematischen Details.
  Ich bin überzeugt, dass Douglas die weiter gefasste Technik kannte. So bezeichnete etwa auch der Autor von „The Large Data Base File Structure Dilemma“ (1975) sie unter http://dx.doi.org/10.1021/ci60001a005 als „eine alte Technik namens super-imposed coding“.
  Die Einschränkung „randomisiert“ ist hier wichtig, denn superimposed codes gab es schon vor Mooers, aber sie waren weder mathematisch besonders interessant noch praktisch bedeutsam.

• Für „worse is better“ ist das zu clever. Man muss noch schlechter denken.
  Die Hauptspeicherbandbreite und die Disk-Bandbreite waren fast gleich und lagen beide bei etwas über 1 MB/s.
  Ich hätte es vermutlich mit mehreren Durchläufen gemacht, aber Bloom-Filter sind trotzdem cool, also hätte ich sie wohl verwendet.
  https://github.com/arnoldrobbins/v10spell
  https://code.google.com/archive/p/unix-spell/
  Auch das Originalpaper ist hervorragend: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
  Es steht auch auf seiner Webseite: https://www.cs.dartmouth.edu/~doug/
  https://en.wikipedia.org/wiki/Douglas_McIlroy
  Wer ein Wort-Nerd ist, wird bei der Suche nach „obovate“ auch auf dieses Diagramm der Blattformen stoßen:
  https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg

• Ich erinnere mich nicht mehr an den Produktnamen, aber in den 80ern gab es einen Hardware-Spellchecker für den IBM PC. Das war eine Box, die zwischen Tastatur und PC geschaltet wurde und piepste, wenn man eine Zeichenfolge eingab, die sie nicht als Wörterbucheintrag erkannte.

  • Das war Xerox PC Type Right.
    In https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf gibt es auf Seite 237 einen Testbericht. Vorsicht: großes PDF.

• Einer der Gründe, warum ich mich für Unix zu interessieren begann, war ein Byte-Artikel irgendwann Anfang der 1980er. Er zeigte, wie man mit einer split/sort/comm-Pipeline einen Spellchecker baut; es waren ungefähr sieben Befehle.
  Auf 8-Bit-PCs gab es so etwas überhaupt nicht, aber wenn man es sah, wirkte es auch nicht so, als brauche es dafür eine besonders große Komplexität.

  • Ähnlich gibt es ein Video aus der Zeit, in dem Brian Kernighan zeigt, wie man mit einer einzeiligen UNIX-Shell-Anweisung einen Spellchecker baut.
    https://youtu.be/tc4ROCJYbm0?t=4m56s

• Ich habe den Artikel erst jetzt ganz gelesen, und der Kern ist meiner Ansicht nach folgender: Es gibt ein „Wörterbuch“ mit 30.000 Wörtern, und wenn man eine False-Positive-Rate von etwa 1/4000 akzeptiert, kann man jedes Wort zu einem 27-Bit-String, also einer Ganzzahl, hashen, das Wörterbuch verwerfen und das Problem darauf reduzieren, eine Menge von 30.000 27-Bit-Strings zu speichern.
  Etwas überraschend ist: Laut Informationstheorie lassen sich 30.000 27-Bit-Strings nicht mit 27 Bit pro Wort speichern, sondern mit nur etwa 13,57 Bit. Die Mathematik verstehe ich (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), aber 30.000 ist im Vergleich zu 2^27, also etwa 134 Millionen, so klein, dass es wohl eine Weile dauert, bis ich intuitiv nachvollziehen kann, woher der Gewinn kommt.
  Um diese 30.000 Elemente umfassende Teilmenge von 27-Bit-Hashes zu codieren, wurden die Hash-Differenzen verwendet, und weil diese Differenzen einer geometrischen Verteilung folgen, erreichte man mit auf Eingaben mit geometrischer Verteilung zugeschnittener Golomb-Codierung in der Praxis etwa 13,6 Bit pro Wort.
  Ich habe darüber nachgedacht, ob man prinzipiell in Richtung „perfektes Hashing“ noch besser werden könnte. Vielleicht könnte es eine Funktion geben, die ein alphabetisches Wort entgegennimmt, irgendeine Transformation durchführt und anschließend leicht prüfen lässt, ob der resultierende Hash zu einer guten Menge gehört.
  Wenn man aber noch einmal darüber nachdenkt, braucht man wegen der False-Positive-Rate mindestens 27 Bit im Hash, damit ein Wort, das nicht im Wörterbuch steht, nicht auf die „gute“ Menge abgebildet wird. Diese Methode wirkt im Grunde theoretisch optimal. Oder könnte es eine Möglichkeit geben, jedes Wort auf eine 27-Bit-Ganzzahl abzubilden, die guten Strings aber beispielsweise genau zu den Werten unter 30000 zu machen?

• Zum Vergleich: Um 1983 herum lief Grammatik für CP/M mit weniger als 64 KB und führte auf 8-Bit-Systemen eine „Grammatikprüfung“ durch. In Wirklichkeit war es eine Rechtschreibprüfung plus Expertensystem-Regeln.
  Ich erinnere mich daran, weil ich in die interessanten Teile hineingestochert habe: Der Grund, warum es so klein sein konnte, war, dass es in Forth geschrieben war, und im Produkt steckte genug von einem externen Interpreter, dass man es mit ein wenig Hex-Editing wie einen Forth-Interpreter mit vorgeladenen Spezialfunktionen verwenden konnte.

  • Im WordStar-Editor, der auf meinem CP/M-System mit 64 KB RAM läuft, steckt eine SPELL.COM-Rechtschreibprüfung mit 2023 Byte Länge.
    Ich habe sie nicht dekompiliert, um zu sehen, wie sie funktioniert, aber sie ist klein, schnell und funktioniert gut.

• Ich frage mich, welche häufigen Tippfehler wegen des Hashings übersehen werden.
  Dazu gibt es auch einen Wettbewerb zur Komprimierung des Wordle-Wörterbuchs: http://golf.horse/wordle/

• Mitte der 80er habe ich etwas Ähnliches erlebt. „Schnell“ ist relativ.
  Es gab viele Daten, der RAM betrug 640 KB, der Heap 64 KB und der Stack 64 KB. Aus mehreren Hundert MB mussten Daten gesucht, extrahiert und teilweise kombiniert werden.
  Ich experimentierte damit, die Daten als Indexstruktur in Form eines ternären Baums aufzubauen. Konzeptionell ergab das Sinn, aber in der Implementierung waren allein die Beziehungs- und Pfadinformationen schon zu groß, um in 64 KB zu passen.
  Statt Kompression wählte ich Swapping. Ich schrieb Code als TSR, heutzutage in etwa ein Dienst, der Datenblöcke verarbeitete, Ergebnisse extrahierte und auf dem Stack speicherte, dann die Originaldaten verwarf und einen Interrupt-Call an den TSR schickte. Daraufhin löschte der TSR den Heap, las den nächsten Block vom Speichermedium und gab die Kontrolle an das Programm zurück; das Programm verarbeitete ihn, kombinierte ihn mit den Stack-Daten und wiederholte das, bis alles fertig war.
  Ursprünglich brauchten für diese Aufgabe drei Datenerfasser etwa eine Woche plus einen Experten, der die Informationen zusammenführte. Man kann sich ungefähr zwölf 3-Zoll-Ringordner voller Tabellen vorstellen. Das Programm war in ein paar Stunden fertig und erstaunlich „schnell“.
  Das lief auf einem Single-Thread-System.
  https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program

• Ich erinnere mich, dass ich bei UNIX spell die Option -b verwendet habe, um britische Schreibweisen zu nutzen. Es gab nur zwei Sprachoptionen, und ich frage mich, warum man sich so entschieden hat, wie der Code damit umging und woher die jeweiligen Wörterbücher stammten.
  Haben Australier und Neuseeländer britische oder amerikanische Schreibweisen verwendet?
  UNIX spell war im Bereich Rechtschreibung so etwas wie ZX81 1K Chess, und auf Heimcomputern gab es vor MS Word für Windows 3.1 nicht besonders viele Rechtschreibprüfungen. In den Büros davor tippten Sekretärinnen mit WordPerfect und fungierten als menschliche Rechtschreibprüferinnen für die jeweiligen Manager und Teams.
  Zu Hause hingegen kam ich während der frühen Computerzeit mit Nadeldrucker und flimmerndem Bildschirm mehr schlecht als recht mit einem Papierwörterbuch aus. Damals konnten alle schreiben, daher erinnere ich mich nicht, dass Rechtschreibprüfungen so wichtig gewesen wären. In einer Schule mit tausend Schülern gab es nur ein Kind, das behauptete, Legasthenie zu haben, und das war eine plausible Ausrede dafür, nicht schreiben zu können.
  Vielleicht waren die 1980er das goldene Zeitalter der Alphabetisierung, und der klar erkennbare Beginn des Niedergangs der Rechtschreibfähigkeit war der Tag, an dem UNIX spell geschrieben wurde.
  Ich mag Scrabble. Das ist ein ganz anderes Problem als Rechtschreibprüfung, aber die Verarbeitung teilt einige Schritte mit UNIX spell: Man findet häufige Wortpräfixe und -suffixe und fügt sie mit anderen Bestandteilen auf dem Rack oder dem Spielbrett zusammen.
  Auch das Scrabble-Wörterbuch ähnelt UNIX spell ein wenig, insofern es nur eine große Wortliste ohne Bedeutungsangaben ist. Entscheidend ist allein, ob ein gegebenes Wort im Buch steht. Es gibt auch einige spezielle Nachschlagetabellen, etwa für die 102 Zwei-Buchstaben-Wörter.

  • Ich erinnere mich, dass ich 1984 auf dem Commodore 64 mit Paperclip 64 Highschool-Aufsätze auf Rechtschreibung geprüft habe. Das war vor Microsoft Windows.
    Weil das Wörterbuch während der Prüfung von Diskette gelesen wurde, dauerte es ein paar Minuten, und danach konnte man die nicht übereinstimmenden Wörter durchgehen.