Unix Spellが64kB RAMで動作した方法
64kB RAMに辞書をどう収めるか？
- Unixのエンジニアたちは、データ構造と圧縮技法を活用して、250kBの辞書を64kB RAMに収める問題を解決した。
- 1970年代に、Douglas McIlroyはAT&TのUnixスペルチェッカーを実装する際にこの問題に直面した。
- 彼はデータの特性を活用し、理論的な圧縮限界に近い圧縮アルゴリズムを開発した。
TL;DR
- Unixスペルチェッカーは、1970年代にAT&TのSteve Johnsonがプロトタイプとして始めた。
- McIlroyは言語ベースのステミングアルゴリズムを開発し、辞書を25,000語に削減した。
- 高速な検索のためにBloomフィルタを使用し、Dennis Ritchieが実装を提供した。
- 辞書が30,000語に増えるとBloomフィルタのアプローチは非効率になり、ハッシュ圧縮技法が導入された。
- 27ビットのハッシュコードを使用して衝突確率を下げ、Golomb符号を使って13.60ビット/語の圧縮を達成した。
Unixスペルコマンドの起源
- UnixはAT&Tの特許部門にテキスト処理システムとして提案され、スペルチェッカーが必要だった。
- 初期バージョンはSteve Johnsonが1975年に書いたが、精度は低かった。
- Douglas McIlroyは精度と性能を改善するためにプロジェクトを書き直した。
接頭辞除去アルゴリズム
- McIlroyは、単語から共通の接頭辞と接尾辞を取り除いて辞書を検索するアルゴリズムを開発した。
- この方法は100%正確ではなかったが、当時としては受け入れ可能な水準だった。
Bloomフィルタベースの検索
- Bloomフィルタはメモリを節約し、高速な検索を可能にした。
- 25,000語の辞書を64kB RAMにロードするために使われた。
- Bloomフィルタは、低い誤検知率を維持するよう調整された。
辞書検索のための圧縮ハッシュ技法
- 辞書サイズが30,000語に増えると、よりメモリ効率の高いデータ構造が必要になった。
- McIlroyは、ハッシュコードの差分を保存してメモリを節約する方法を使った。
- Golomb符号を用いてハッシュ差分を圧縮した。
結論
- Unixスペルコマンドは、PDP-11のメモリ制約から生まれた興味深いエンジニアリングの歴史である。
- Bloomフィルタ、情報理論、確率論、圧縮アルゴリズムを組み合わせたエレガントな解決策を提供した。
- これは、リソース制約があるときでも深い問題解決が可能であることを示している。
1件のコメント
Hacker Newsのコメント
Bloomフィルタはもともと「superimposed code scheme」と呼ばれており、これは特定の種類の superimposed code である
外部メモリのスペルチェッカーは少ないRAMでも実装できる
メモリ帯域幅とディスク帯域幅は似たようなもので、複数回のパスで処理を進めることができた
1980年代にはIBM PC向けのハードウェアスペルチェッカーがあった
Unix はAT&Tに対してテキスト処理システムとして提案されており、スペルチェッカーが必要だった
1980年代初頭の Byte の記事で、Unix のスペルチェッカーを作る方法が説明されていた
ハッシュ化の影響で見逃される典型的なタイプミスがあり得る
1980年代半ばには、640KBのRAMと64KBのヒープおよびスタックを使ってデータを処理していた
1983年ごろ、CP/M上の Grammatik は64k未満で動作し、文法チェックとエキスパートシステムのルールを含んでいた
UNIX の最初のバージョンは24kBを必要とし、その半分をカーネルが占めていた