Unix Spell: Das 64 kB RAM Wunder
In den 1970er Jahren stand der Unix-Rechtschreibprüfer vor einer unglaublichen Herausforderung: ein 250 kB großes Wörterbuch in nur 64 kB RAM auf einem PDP-11-Computer unterzubringen. Douglas McIlroys geniale Lösung umfasste einen mehrstufigen Ansatz. Zunächst ermöglichte ein Bloom-Filter schnelle Suchen, doch mit wachsendem Wörterbuch entwickelte er ein neuartiges Hash-Komprimierungsschema. Durch die Erkenntnis, dass die Differenzen zwischen sortierten Hash-Codes einer geometrischen Verteilung folgten, und durch den Einsatz von Golomb-Codierung erreichte er nahezu theoretische Komprimierungsgrenzen. Schließlich verbesserte die Partitionierung der komprimierten Daten die Suchgeschwindigkeit weiter. Diese Geschichte ist eine Meisterklasse in der Optimierung unter Zwängen und zeigt, wie intelligente Algorithmen scheinbar unlösbare Probleme überwinden können.