Unixのspellコマンドは64KBのRAMでどのように動作したか

64KBのRAMに250KBの辞書を収め、高速な検索をどのように実現するか？参考までに、gzip -9のような現代の圧縮技術を使っても、このファイルを85kB以下に圧縮することはできません。 1970年代、AT&TでUnixのスペルチェッカーを実装していたDouglas McIlroyは、まさにこの課題に直面しました。PDP-11コンピュータの制約により、辞書全体をわずか64KBのRAMに収める必要がありました。それは一見不可能に思えるタスクでした。 彼は汎用的な圧縮技術に頼るのではなく、データの特性を利用し、可能な圧縮の理論的限界に0.03ビットまで迫る圧縮アルゴリズムを開発しました。今日に至るまで、これは破られていません。Unix spellの物語は、単なる歴史的な好奇心以上のものです。それは制約下でのエンジニアリングのマスタークラスであり、問題を第一原理から分析し、数学的洞察を活用し、厳格なリソース制限内で機能するエレガントなソリューションを設計する方法を示しています。 TL;DR 時間がなければ、ここに主要なエンジニアリングの物語があります： Unix spellは1970年代にAT&Tのスティーブ・ジョンソンによる午後のプロトタイプとして始まり、その後Douglas McIlroyがパフォーマンスと精度を向上させるために書き直しました。 McIlroyの最初の革新は、辞書をわずか25,000語に減らしながら精度を向上させた、巧妙な言語学に基づいたステミングアルゴリズムでした。 高速検索のために、彼は当初ブルームフィルタ（おそらくその初期の製品利用の一つ）を使用しました。興味深いことに、Dennis Ritchieが実装を提供しました。彼らは誤検出率を非常に低くチューニングしたため、実際の辞書検索をスキップすることができました。 辞書が30,000語に増えると、ブルームフィルタのアプローチは実用的ではなくなり、革新的なハッシュ圧縮技術につながりました。 彼らは、衝突確率を許容範囲内に低く保つためには27ビットのハッシュコードが必要であると計算しましたが、圧縮が必要でした。 McIlroyの解決策は、ソートされたハッシュコード間の差分を格納することでした。これらの差分が幾何分布に従うことを発見した後です。 幾何分布用に設計された圧縮スキームであるGolombコードを使用して、彼は1ワードあたり13.60ビットを達成しました。これは、理論的最小値である13.57ビットに驚くほど近い値です。 最後に、彼は検索を高速化するために圧縮データをパーティション化しました。これにより、パフォーマンスが大幅に向上する代わりに、メモリ使用量がわずかに増加しました（最終サイズは1ワードあたり約14ビット）。 記事の残りの部分では、これらの各ポイントを拡張し、すべての数学と論理の背後にある詳細な説明を提供します。 A PDP-11 machine, source: Wikipedia この記事の執筆には数日かかりました。私の活動をサポートするために、有料購読者になることができます。Substackでの支払いに問題がある場合は、buymeacoffeeやGitHubスポンサーシップでもサポートできます。有料購読者は、Linux Context Switching Internalsに関する私の執筆中の書籍の割引も受けられます。 購読する Unix Spellコマンドの起源 Unixの資金を確保するため、Ken ThompsonとDennis RitchieはAT&Tの特許部門向けのテキスト処理システムとしてUnixを提案しました。当然、テキスト処理システムにはスペルチェッカーも必要でした。Unix spellの最初のバージョンは1975年にSteve Johnsonによって書かれましたが、これはプロトタイプでした。Jon Bentleyによると、Steveはそれをある午後に書きました。機能はしましたが、精度はあまり高くありませんでした。非常にシンプルでした。入力ファイルを単語のストリームに分割し、数字や特殊文字の削除、小文字への変換などの軽い前処理を行い、ソートしてユニークにし、最後にリストをspellプログラムに渡すというもので、プログラムは単にディスク上の辞書に単語が存在するかどうかをチェックするだけでした。 その単純な実装のため、精度が低く、ディスク上の辞書検索のために遅くもありました。 初期バージョンの採用を見た後、Douglas McIlroyはツールの精度とパフォーマンスを向上させることを目標に、プロジェクトを引き継いで書き直しました。彼は非常に巧妙なエンジニアリングを伴う2つの別々の側面に取り組みました： 単語をその語幹に削減するためのアフィックス除去アルゴリズムと、語幹単語で構成されるコンパクトな辞書の構築 高速検索のために辞書をメモリにロードするためのコンパクトなデータ構造 この記事はデータ構造設計の部分に焦点を当てますが、アフィックス除去アルゴリズムの概要を見て、それがどのように機能したかを見てみましょう。 アフィックス除去アルゴリズム 完全な辞書を使用して検索を行うのは遅かったです。当時のコンピュータはメインメモリが数キロバイトしかなく、ディスクベースの検索はさらに遅かったからです。Douglas McIlroyは、単語から一般的な接頭辞と接尾辞を繰り返し削除し、削減された単語が辞書に存在するかどうかをチェックするアルゴリズムのアイデアを思いつきました。アルゴリズムは、削除するアフィックスがなくなるまでアフィックス除去プロセスを続け、それでも単語が辞書に存在しない場合は、スペルミスとしてフラグが立てられました。 例えば、アルゴリズムは「misrepresented」という単語から接頭辞「mis」、「re」、接尾辞「ed」を削除して「present」に削減します。そして、「present」は辞書に有効な単語であるため、スペルミスとしてフラグは立てられません。 このアフィックス除去技術は100％正確ではなく、誤ってスペルミスでない単語を通過させてしまうこともありました。しかし、そのような発生は当時許容できると見なされていました。彼はまた、一般的なエラーを回避するために、これらのルールに多くの例外を実装しました。全体として、このアルゴリズムは非常にコンパクトな辞書をもたらしました。最終的な辞書は25,000語で構成されており、うまく設計されたデータ構造でメモリにロード可能であるように見えました。 わずか64KBのメモリでインメモリ辞書検索をどのように実装できたかについて議論に移りましょう。 ブルームフィルタベースの検索 Bloomは1970年にブルームフィルタに関する研究を発表しましたが、Unix spellは1970年代半ばに開発されました。この時点では、ブルームフィルタはまだブルームフィルタと呼ばれていませんでした。論文の中で、Douglasはそれを「重ね合わせコードスキーム」と呼んでいます。興味深いことに、彼が使用したブルームフィルタの実装はDennis Ritchieから提供されたものでした。 辞書のサイズは25,000語でしたが、それをそのまま64KBのRAMにロードすることはまだ不可能でした。さらに、高速な検索も必要でした。Douglasが最初に使ったデータ構造はブルームフィルタでした。論文ではブルームフィルタとは呼ばず、1970年のBloomの論文に帰せられる「重ね合わせコードスキーム」と参照しています。興味深いことに、彼が使用したブルームフィルタの実装の功績はDennis Ritchieに帰しています。 ブルームフィルタはすべてゼロに初期化されたビットテーブルで構成されています。ブルームフィルタにアイテムを追加するには、アイテムに複数のハッシュ関数を適用します。各ハッシュ関数はテーブル内のインデックスを生成し、そのビットインデックスは1に設定されます。k個のハッシュ関数が使用されている場合、k個の異なるビットインデックスがテーブル内でオンになります。 ブルームフィルタの詳細については、私のブルームフィルタに関する記事をご覧ください。 アイテムの検索は、それがテーブルに存在するかどうかに関わらず、同じ手順が必要です。k個のハッシュ関数を適用し、それぞれについて、対応するビットがテーブルでオンになっているかどうかを確認する必要があります。ビットの1つでもオンになっていない場合、そのアイテムはデータセットに存在しないことを意味します。しかし、すべてのビットがオンになっている場合、アイテムが存在する可能性があることを示しますが、これは偽陽性である可能性もあります。ハッシュ衝突により、偽陽性が発生する可能性があります。アイテムをクエリするとき、ビットがクエリアイテムのため、または別のアイテムとのハッシュ衝突のためにオンになっているのかを100％確信することはできません。ブルームフィルタを使用する場合、偽陽性を処理するための戦略を実装する必要があります。例えば、このケースでは完全な辞書検索を行うことを意味するかもしれません。しかし、それは目的全体を損なうでしょう。