Unix spell, das mit 64 kB RAM lief

Wie Unix Spell mit 64 kB RAM lief

Wie passt ein Wörterbuch in 64 kB RAM?

• Unix-Ingenieure lösten das Problem, ein 250-kB-Wörterbuch in 64 kB RAM unterzubringen, mithilfe von Datenstrukturen und Komprimierungstechniken.
• In den 1970er Jahren stand Douglas McIlroy vor diesem Problem, als er die Unix-Rechtschreibprüfung bei AT&T implementierte.
• Er entwickelte einen Komprimierungsalgorithmus, der die Eigenschaften der Daten ausnutzte und sich der theoretischen Komprimierungsgrenze annäherte.

TL;DR

• Die Unix-Rechtschreibprüfung begann in den 1970er Jahren als Prototyp von Steve Johnson bei AT&T.
• McIlroy entwickelte einen sprachbasierten Stemming-Algorithmus, der das Wörterbuch auf 25.000 Wörter reduzierte.
• Für schnelle Abfragen wurde ein Bloom-Filter verwendet, dessen Implementierung von Dennis Ritchie bereitgestellt wurde.
• Als das Wörterbuch auf 30.000 Wörter anwuchs, wurde der Bloom-Filter-Ansatz ineffizient, sodass eine Hash-Komprimierungstechnik eingeführt wurde.
• Mit 27-Bit-Hashcodes wurde die Kollisionswahrscheinlichkeit gesenkt, und mit dem Golomb-Code wurde eine Komprimierung von 13,60 Bit pro Wort erreicht.

Der Ursprung des Unix-Befehls spell

• Unix wurde der Patentabteilung von AT&T als Textverarbeitungssystem vorgeschlagen, und dafür wurde eine Rechtschreibprüfung benötigt.
• Die erste Version wurde 1975 von Steve Johnson geschrieben, hatte jedoch eine geringe Genauigkeit.
• Douglas McIlroy schrieb das Projekt neu, um Genauigkeit und Leistung zu verbessern.

Algorithmus zum Entfernen von Präfixen

• McIlroy entwickelte einen Algorithmus, der gemeinsame Präfixe und Suffixe aus Wörtern entfernt, um im Wörterbuch nachzuschlagen.
• Diese Methode war nicht zu 100 % genau, galt damals aber als akzeptabel.

Bloom-Filter-basierte Abfrage

• Ein Bloom-Filter spart Speicher und ermöglicht schnelle Abfragen.
• Er wurde eingesetzt, um ein Wörterbuch mit 25.000 Wörtern in 64 kB RAM zu laden.
• Der Bloom-Filter wurde so abgestimmt, dass eine niedrige Falsch-Positiv-Rate erhalten blieb.

Komprimierte Hashing-Technik für Wörterbuchabfragen

• Als die Größe des Wörterbuchs auf 30.000 Wörter anwuchs, wurde eine speichereffizientere Datenstruktur nötig.
• McIlroy nutzte eine Methode, die die Unterschiede zwischen Hashcodes speichert, um Speicher zu sparen.
• Diese Hash-Differenzen wurden mit dem Golomb-Code komprimiert.

Fazit

• Der Unix-Befehl zur Rechtschreibprüfung ist ein faszinierendes Stück Ingenieursgeschichte, das aus den Speicherbeschränkungen des PDP-11 entstand.
• Er bot eine elegante Lösung, die Bloom-Filter, Informationstheorie, Wahrscheinlichkeitstheorie und Komprimierungsalgorithmen kombinierte.
• Er zeigt, dass auch unter Ressourcenbeschränkungen tiefgehende Problemlösungen möglich sind.

[GN⁺]

Hacker-News-Kommentare

• Der Bloom-Filter wurde ursprünglich als „superimposed code scheme“ bezeichnet und ist eine bestimmte Art von superimposed code

  • Calvin Mooers entwickelte in den 1940er Jahren am MIT, beeinflusst von Shannons Arbeit, randomisierte superimposed coding
  • Bournes Buch Methods of Information Handling von 1963 liefert die mathematischen Details
  • Douglas kannte diese Technik wahrscheinlich

• Externe Rechtschreibprüfung konnte mit wenig RAM implementiert werden

  • Dabei werden die Wörter eines Dokuments sortiert, doppelte Einträge entfernt und dann mit einem Wörterbuch zusammengeführt, sodass nur die fehlenden Wörter übrig bleiben
  • Lief auf dem TRS-80 Color Computer mit weniger als 32k RAM
  • Turbo Lightning führte beim Tippen auf dem PC eine Rechtschreibprüfung mit einem komprimierten Wörterbuch durch

• Speicherbandbreite und Festplattenbandbreite waren ähnlich, und die Aufgabe konnte in mehreren Durchläufen erledigt werden

  • Dafür ist ein Bloom-Filter gut geeignet

• In den 1980er Jahren gab es Hardware-Rechtschreibprüfer für IBM-PCs

  • Sie wurden zwischen Tastatur und PC angeschlossen und gaben einen Signalton aus, wenn man ein unbekanntes Wort eingab

• Unix wurde AT&T als Textverarbeitungssystem vorgeschlagen, daher wurde eine Rechtschreibprüfung benötigt

  • UNIX wurde hauptsächlich für Textverarbeitung verwendet

• Ein Byte-Artikel aus den frühen 1980er Jahren erklärte, wie man die Unix-Rechtschreibprüfung baut

  • Auf 8-Bit-PCs gab es solche Funktionen nicht

• Durch Hashing konnten häufige Tippfehler übersehen werden

  • Es gibt einen Wettbewerb zur Komprimierung von Wordle-Wörterbüchern

• Mitte der 1980er Jahre wurden Daten mit 640 KB RAM sowie 64 KB Heap und Stack verarbeitet

  • Das Extrahieren und Zusammenführen der Daten dauerte mehrere Stunden und lief auf einem Single-Thread-System

• Um 1983 lief Grammatik unter CP/M mit weniger als 64k und enthielt Grammatikprüfung sowie Expertensystem-Regeln

  • Es war in Forth geschrieben und sehr kompakt

• Die erste Version von UNIX benötigte 24 kB, wovon die Hälfte vom Kernel belegt wurde