Unix spell：64KB RAMの奇跡

1970年代、Unixのスペルチェッカーは信じられないほどの課題に直面しました。PDP-11コンピュータのわずか64KBのRAMに250KBの辞書を収めることです。Douglas McIlroyの独創的な解決策は、複数段階のアプローチでした。最初はBloomフィルタが高速なルックアップを提供しましたが、辞書が大きくなるにつれて、彼は新しいハッシュ圧縮スキームを開発しました。ソートされたハッシュコード間の差が幾何分布に従うことを認識し、Golomb符号化を使用することで、彼はほぼ理論限界の圧縮率を達成しました。最後に、圧縮されたデータを分割することで、検索速度がさらに向上しました。この物語は、制約のある最適化におけるマスタークラスであり、巧妙なアルゴリズムがいかにして一見不可能な限界を克服できるかを示しています。