HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

How Unix spell ran in 64 kB of RAM (blog.codingconfessions.com)

60 pointsby donw4 コメント

要約

1970年代、UnixのspellコマンドはPDP-11の64KBという極めて限られたメモリ制約の中で動作する必要がありました。Douglas McIlroyは、単語の語幹を抽出する言語学的なアルゴリズムと、ハッシュコードの差分をGolomb符号で圧縮する革新的なデータ構造を開発し、理論的限界に近い圧縮率を達成しました。この技術は、リソースが限られた環境でのエンジニアリングの優れた事例として、現代にも通じる教訓を与えています。

全文翻訳

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

250kBの辞書を64kBのRAMに収め、高速な検索をどのように実現したのでしょうか?参考までに、gzip -9のような最新の圧縮技術を使っても、このファイルを85kB以下に圧縮することはできません。

1970年代、Douglas McIlroyはAT&TでUnixのスペルチェッカーを実装する際に、まさにこの課題に直面しました。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]

Unix Spellコマンドの起源

Unixの資金を確保するため、Ken ThompsonとDennis RitchieはAT&Tの特許部門にUnixをテキスト処理システムとして売り込みました。当然、テキスト処理システムにはスペルチェッカーも必要でした。

Unix spellの最初のバージョンは、1975年にSteve Johnsonによってプロトタイプとして書かれました。Jon Bentleyによると、Steveはそれを午後に書き上げたそうです。機能はしましたが、精度は高くありませんでした。

それは非常にシンプルでした。入力ファイルを単語のストリームに分割し、数字や特殊文字の削除、小文字への変換などの軽い前処理を行い、ソート、ユニーク化してからspellプログラムに渡していました。spellプログラムは、ディスク上の辞書にそれらの単語が存在するかどうかを単純にチェックしていました。

その単純な実装のため、精度が低く、ディスク上の辞書検索のために遅かったのです。

初期バージョンの採用を見た後、Douglas McIlroyは精度とパフォーマンスを向上させることを目標に、プロジェクトを引き継いで書き直しました。彼は非常に巧妙なエンジニアリングを伴う2つの別々の側面で作業しました。

  • 単語をステミングに削減するための接辞除去アルゴリズムと、ステミング単語で構成されるコンパクトな辞書の構築
  • 辞書をメモリにロードして高速な検索を行うためのコンパクトなデータ構造

この記事はデータ構造設計の部分に焦点を当てますが、接辞除去アルゴリズムの概要を理解するためにセクションを割きましょう。

接辞除去アルゴリズム

検索のために完全な辞書を使用するのは遅かったです。当時のコンピュータは数キロバイトのメインメモリしか持たず、ディスクベースの検索はさらに遅かったからです。

Douglas McIlroyは、単語から一般的な接頭辞と接尾辞を繰り返し削除し、削減された単語が辞書に存在するかどうかを調べるアルゴリズムのアイデアを思いつきました。アルゴリズムは、削除する接辞がなくなるまで接辞除去プロセスを続行し、それでも単語が見つからない場合は、スペルミスとしてフラグが立てられました。

例えば、アルゴリズムは「misrepresented」という単語を「mis」「re」という接頭辞と「ed」という接尾辞を削除して「present」に削減します。そして「present」が辞書内の有効な単語であるため、スペルミスとしてフラグは立てられませんでした。

この接辞除去技術は100%正確ではなく、スペルミスを通過させてしまうこともありました。しかし、当時の許容範囲内と見なされていました。彼はまた、一般的なエラーを回避するために、これらのルールに多くの例外を実装しました。

全体として、このアルゴリズムは非常にコンパクトな辞書をもたらしました。最終的な辞書は25,000語で構成され、うまく設計されたデータ構造でメモリにロード可能でした。

わずか64kBのメモリでインメモリ辞書検索をどのように実装したかについて議論を進めましょう。

ブルームフィルタベースの検索

ブルームは1970年にブルームフィルタに関する研究を発表しましたが、Unix spellは1970年代半ばに開発されました。この時点では、ブルームフィルタはまだその名前で呼ばれていませんでした。論文の中で、Douglasはそれを「重ね合わせコードスキーム」と呼んでいます。

興味深いことに、彼が使用したブルームフィルタの実装はDennis Ritchieから提供されたものでした。

辞書のサイズは25,000語でしたが、そのままでは64kBのRAMに収めることはまだ不可能でした。さらに、高速な検索も必要でした。

Douglasが最初に使ったデータ構造はブルームフィルタでした。論文ではブルームフィルタとは呼んでおらず、「重ね合わせコードスキーム」と呼んでおり、Bloomの1970年の論文に帰属させています。興味深いことに、彼が使用したブルームフィルタの実装の功績はDennis Ritchieに帰しています。

ブルームフィルタは、すべてゼロに初期化されたビットテーブルで構成されます。アイテムをブルームフィルタに追加するには、アイテムに複数のハッシュ関数を適用します。各ハッシュ関数はテーブル内のインデックスを生成し、そのビットインデックスは1に設定されます。k個のハッシュ関数が使用される場合、k個の異なるビットインデックスがテーブル内でオンになります。

ブルームフィルタの詳細については、私のブルームフィルタに関する記事をご覧ください。

アイテムを検索する場合、それがテーブルに存在するかどうかを確認するには同じ手順が必要です。k個のハッシュ関数を適用し、それぞれについて、対応するビットがテーブルで1に設定されているかどうかを確認する必要があります。ビットのいずれかがオンになっていない場合、そのアイテムはデータセットに存在しないことを意味します。しかし、すべてのビットが設定されている場合、アイテムが存在する可能性があることを示しますが、これは偽陽性である可能性もあります。

ハッシュ衝突により偽陽性が発生することがあります。アイテムをクエリするとき、ビットがクエリアイテムのためにオンになっているのか、それとも別のアイテムとのハッシュ衝突のためにオンになっているのかを100%確信することはできません。

ブルームフィルタを使用する場合、偽陽性に対処するための戦略を実装する必要があります。例えば、このケースでは完全な辞書検索を行うことになります。しかし、それはメモリを節約し、高速な辞書検索を行うというブルームフィルタを使用する目的全体を無効にしてしまいます。スペルチェッカーの場合、ほとんどの単語は辞書に存在し、スペルミスはごく一部であるため、完全な辞書を頻繁にチェックすることになります。

しかし、ブルームフィルタは望ましい偽陽性率を達成するように調整できます。以下の式は、指定されたサイズm、挿入されたアイテム数n、ハッシュ関数数kを持つブルームフィルタの偽陽性確率を計算します。

(\begin{align*}\text{q} \approx \left( 1 - e^{-\frac{kn}{m}} \right) \ &\text{ここで:} \ &\text{q}: \text{ビットが1である確率} \ &m: \text{ブルームフィルタのビット数} \ &k: \text{使用されるハッシュ関数の数} \ &n: \text{挿入された要素の数} \end{align*})

Douglasは論文で、2000分の1の偽陽性率で十分であり、そのような低い偽陽性率であれば辞書を参照する必要がなかったと述べています。

25,000個のアイテムの辞書があったため、アイテム数は固定されていました。メモリの制限のため、ビットテーブルサイズを400,000ビットに固定しました。これらの要因に基づき、11個のハッシュ関数を使用することで、偽陽性率を約1/2000に抑えることができました。

ブルームフィルタ使用の結果

彼らはブルームフィルタベースのスペル実装をしばらく使用しました。論文の中で、Douglasは偽陽性率は許容範囲内であったものの、実際の使用では、辞書に追加する必要のある新しい単語に頻繁に遭遇したと述べています。これにより、辞書サイズは25,000から30,000に増加しました。

しかし、このサイズの辞書では、彼らのブルームフィルタはより大きなビットテーブルサイズを必要とし、それは彼らにとって不可能でした。その結果、Douglasは、30,000語の辞書を同等の検索パフォーマンスと精度でメモリに収めることができる代替データ構造設計を探しました。

辞書検索のための圧縮ハッシュスキーム

辞書サイズが25,000から30,000に急増したため、Douglasは辞書をメモリに保持するための、よりメモリ効率の良いデータ構造を必要としていました。

ハッシュテーブルは魅力的な解決策でしたが、衝突を処理するためにハッシュと実際の単語の両方を格納する必要があるため、ブルームフィルタよりもはるかに多くのメモリを消費していました。

完全なハッシュテーブルの代わりに、Douglasはハッシュのみを格納することにしました。検索では、入力単語のハッシュを計算し、スキャンを使用してハッシュの存在を確認する必要がありました。

これを行う直感の一つは、個々の単語は可変長である可能性があるが、ハッシュ関数はそれらを自然に固定ビット数に圧縮するため、ハッシュをメモリに収めることができる可能性があるということかもしれません。

しかし、ハッシュは衝突する可能性があるため、許容できる低い衝突確率を持つために十分な大きさのハッシュコードが必要でした。

最適なハッシュコードサイズの計算

辞書の各単語がbビットのハッシュコードにハッシュされる場合、その空間には合計2^b個の可能なハッシュコードがあります。そのうち、v個のユニークなハッシュコードのセットを選択します。ハッシュ衝突の確率は次のように計算できます。

(\begin{align*}\text{P(hash collision)} = \frac{v}{2^b} \end{align*})

彼らは30,000語の辞書を持っていました。これは約2^15語です。さらに、彼は衝突確率が1 in 2^12で十分だったと述べています。これにより、ハッシュコードサイズは27ビットになりました。

しかし、27ビットのハッシュコードは大きすぎました。2^15語の場合、2^15 * 27ビットのメモリが必要でしたが、PDP-11には2^15 * 16ビット(64kB)のRAMしかありませんでした。圧縮が不可欠でした。

ハッシュコード圧縮の理論的最小限界

圧縮アルゴリズムを実装する前に、このデータセットを圧縮できる理論的な最小ビット数を知る必要があります。これは、データの圧縮をどれだけうまく行えたかを示すベンチマークとして機能します。

この理論的最小値は、圧縮しようとしているデータを生成したイベントの情報量から計算されます。これは、すべてのデータ圧縮技術の基礎となる情報理論の概念です。

イベントの情報量

情報量の基本的な考え方は、イベントの確率を使用して、情報損失なしでエンコードするために必要なビット数を決定することです。

発生確率の高いイベントは情報量が少ない(例えば、100%確率のイベントは情報がなく、エンコードに0ビット必要)のに対し、発生確率の低いイベントはより多くの情報を含み、より多くのビットを必要とします。イベントの確率と情報量の間には逆の関係があり、次の式につながります。

(\begin{align*}\text{I(E)} = \log_2\left(\frac{1}{P(E)}\right) \ &\text{または、I(E) = } -\log_2{P(E)} \ &\text{ここで P(E) はイベント E の確率} \end{align*})

次に、ハッシュコードのセットの情報量を計算するには、それらを生成する確率を特定する必要があります。

ハッシュコードのサイズがbビットの場合、その空間には合計2^b個の可能なハッシュコードがあります。そのうち、v個のユニークなハッシュコードのセットを選択します。

( \begin{align*}\text{そのようなセットを選択する総数 = }\binom{2^b}{v} \end{align*})

したがって、これらのセットのいずれかが生成される確率は次のようになります。

(\begin{align*}\text{P} = \frac{1}{\binom{2^b}{v}} \end{align*})

したがって、これらのハッシュコードの情報量は次のようになります。

(\begin{align*}&I(E) = - \log_2\left(\frac{1}{\binom{2^b}{v}}\right) \ &= \log_2\left(\binom{2^b}{v}\right) \ &= \log_2\left(\frac{(2^b)!}{v! , (2^b - v)!}\right) \end{align*})

物事を単純化するために、スターリングの近似を使用できます。

(\begin{align*}&\text{スターリングの近似: } \quad \log_2(n!) \approx n \log_2(n) - n \log_2(e), \ \end{align*})

論文では、辞書の単語数(30,000)がハッシュコードの総数(2^27)よりもはるかに小さい(v « 2^b)という別の単純化された仮定を使用しており、これにより上記の計算で(2^b - v)を2^bとして単純化できます。

これらの2つの近似を使用すると、情報量に対して次の式が得られます。

(\begin{align*}&I(E) \approx v\left[b - \log_2\left(\frac{v}{e}\right)\right] \end{align*})

v=30,000とb=27を代入すると、1つのハッシュコードをエンコードするために必要な最小ビット数は13.57となり、元のハッシュコードよりも約50%短く、PDP-11のメモリ容量内に収まりました。

差分ベースの圧縮スキーム

この時点で、どれだけの圧縮が可能かを知っていましたが、それをどのように達成するかがより大きな問題でした。生のハッシュコードを圧縮する代わりに、ソートされた順序で successive なハッシュコード間の差分を計算して格納したらどうなるでしょうか?これはデルタエンコーディングの仕組みに似ていますが、まったく同じではありません。

ハッシュ差分を扱うことには、いくつかの利点がありました。

  • 定義上、差分は生のハッシュコードよりも小さかった
  • 多くの差分値は、いくつかのハッシュコードの差が同じになる可能性があるため、繰り返されました。

これは、ハッシュコードよりもこれらの差分を圧縮する方が容易であることを意味しました。

ハッシュ差分の計算

ハッシュ差分は、ハッシュコードをソートし、連続する値の差を取ることで計算されました。

例:

単語の検索が、ハッシュ差分を実際の値の代わりに格納した場合にどのように機能したかを見てみましょう。

存在確認のための単語検索

単語が辞書に存在するかどうかを確認するために、単語のハッシュを計算し、単純なアルゴリズムでハッシュの存在を確認しました。

次に、このデータに対する圧縮スキームをどのように考案したかについて説明します。

ハッシュコード差分の数学的モデリング

ロスレス圧縮の基本原則は、確率の高いシンボルには短いコードを、確率の低いシンボルには長いコードを割り当てることです。確率の高いシンボルはデータ内でより頻繁に発生する傾向があり、それらに短いコードを割り当てることは高い圧縮率を意味するため、これは理にかなっています。

しかし、これにはデータのすべてのシンボルの確率分布を計算し、それを使用して圧縮コードを生成する必要があります。デコード時にも確率分布テーブルが必要になります。

これはDouglasにとって2つの問題がありました。

  • 約30,000個のシンボルの確率分布テーブルをメモリに保持すると、圧縮自体から得られる圧縮の利点がすべて失われてしまいます。そのため、この要件から解放されるスキームが必要でした。
  • ハッシュ差分の確率を計算するのは時間がかかるでしょう。30,000個の可能なハッシュ差分値、それらの合計とカウントをメモリに保持して確率を計算することは不可能でした。そのため、それらの確率を計算するには、高価なディスクベースのデータ構造が必要になります。

しかし、McIlroyはハッシュ差分が幾何分布に従うことを認識することで、エレガントな解決策を思いつき、効率的な圧縮スキームを可能にしました。まず、これらのハッシュ差分値がどのように幾何分布に従うかを理解しましょう。

ハッシュ差分の幾何分布モデリング

幾何分布は、成功が得られるまで実験を繰り返すシナリオをモデル化するために使用される離散確率分布です。例えば、サイコロを「1」が出るまで振ることは、成功確率が1/6の幾何分布を形成します。より簡単な例は、コインを裏が出るまで投げることです。

失敗確率がp、成功確率がqで、k回目の試行で成功した場合、幾何分布の確率質量関数は次の式で与えられます。

(\begin{align*}\text{P} = p^kq \end{align*})

次に、ハッシュ差分値がこの分布にどのようにマッピングされるかを理解しましょう。

各ハッシュコードはbビット幅であるため、2^b個のポイントの空間があります。そして、この空間にはv個のハッシュコードが散らばっています。この空間の任意のポイントにハッシュコードが含まれる確率はq=v/2^bであり、ポイントが空である確率はp=1-(v/2^b)です。

(\begin{align*}\text{P(a point containing a hash code)} = q = \frac{v}{2^b} \ &\text{P(an empty point)} = p = 1 - \left(\frac{v}{2^b}\right) \end{align*})

しかし、私たちはハッシュコード自体ではなく、ハッシュ差分値の分布をモデル化することに関心があります。ハッシュ差分kは、ソートされたシーケンス内の2つの連続するハッシュ値がkの位置だけ離れている場合に発生します。例えば、2つの連続するハッシュ値が20と25の場合、ハッシュ差分は5です。

kのハッシュ差分を見る確率は何でしょうか?任意のハッシュ値hについて:

  • hの後のk-1個の位置が空である必要があります。
  • そして、h+kの位置にハッシュ値が必要です。
  • k-1個の空の位置の確率はp^(k-1)です。
  • h+kの位置にハッシュ値がある確率はqです。

したがって、ハッシュ差分がkである確率は次のようになります。

(\begin{align*}\text{P(difference=k) =} p^\left(k-1\right)q \end{align*})

これはまさに幾何分布の形式に従っています!

spellの論文を読むと、著者がこの結論に至るまで異なるルートを取っていることがわかります。彼はハッシュコードの生成をポアソンプロセスとしてモデル化し、そこから進めています。

しかし、これを幾何分布としてモデル化する意味は何でしょうか?その結果、Golombが1965年の論文で与えた、幾何分布整数に対する非常にシンプルで効率的なランレングスエンコーディングスキームがあります。それがどのように機能するかを見てみましょう。

幾何分布整数用の圧縮スキーム(Golombコード)

Golombコードは、幾何分布整数用のシンプルなランレングスエンコーディングスキームであり、Douglasがハッシュ差分を圧縮するために使用しました。これは、幾何分布値が成功の確率が指数関数的に減衰するという事実を利用しており、圧縮を実行するために活用できます。

それはどういう意味でしょうか?幾何分布の場合、k回の試行後の成功確率は次のように与えられることを思い出してください。

(P = p^kq)

p^m = 1/2となる整数mを見つけたとしましょう。これは、k + m回の試行後の成功確率が次であることを意味します。

(\begin{align*}&\text{P(success after k + m trials)} = p^\left(k + m\right)q = \frac{1}{2}p^kq \end{align*})

言い換えれば、k + m回の試行で成功する確率は、k回の試行で成功する確率の半分です。そして、この確率はm回の連続する試行ごとに半分になります。これは指数関数的に減衰する確率分布です。

指数関数的に減衰する確率の例による理解

表が出るまでコインを投げるという公平なコイン投げの例を考えてみましょう。公平なコインの場合、p = q = 1/2です。

ここではm = 1です。なぜならp^1 = 1/2だからです。これは、確率が試行ごとに半分になることを意味します。

(\begin{align*}&P(k=1) = \frac{1}{2} \ &P(k=2) = \frac{1}{4} \ &P(k=3) = \frac{1}{8} \ &P(k=4) = \frac{1}{16} \end{align*})

偏ったコインの例をもう一つ取りましょう。p=1/sqrt(2) = 0.707、q=0.293とします。

ここではm=2です。なぜならp^2 = 1/2だからです。この場合、確率は2のブロックごとに減衰します。

(\begin{align*}&P(k=1) = 0.293 \ &P(k=2) = 0.207 \ &P(k=3) = 0.116 \ &P(k=4) = 0.104 \ &P(k=5) = 0.073 \ &P(k=6) = 0.051 \end{align*})

偶数のkごとに確率は半分に減衰していることがわかります。例えば:

(\frac{P(k=2)}{P(k=4)} = \frac{P(K=4)}{P(k=6)} \approx 0.5)

指数関数的に減衰する確率の意義

この指数関数的な減衰のパターンにより、m個のブロックにハッシュ差分値をグループ化できます。ブロック内の各値はkビットのコードを受け取り、次のブロックはk + 1ビットのコードを受け取ります。その理由は情報理論に根ざしています。

イベントの結果をエンコードするために必要な最小ビット数は、情報量、つまり-log₂(p)(pはそのイベントの確率)によって与えられます。

これは、確率が1/2のイベントには1ビットのコードが必要であり、確率が1/4のイベントには2ビット、確率が1/8のイベントには3ビットのコードが必要であることを意味します。

これを幾何分布値に活用するために、m個のブロックにグループ化できます。特定のブロック内の値には同じ長さのコードを割り当てることができ、後続ブロックの値にはm個の値ごとに1ビット幅のコードが追加されます。

[画像: Arranging hash code differences in blocks of sizes m, where each block’s probability is half of that of its predecessor. If the predecessor block gets k bit wide codes, the next block gets k+1 bit wide codes.]

この自己相似パターンは、コードの非常に簡単な生成を可能にする特性を持つ、美しい自己相似ビットパターンを形成します。この自己相似パターンがどのように形成されるかを見てみましょう。

自己相似パターン

自己相似パターンとは、本質的に、ブロック内の特定のインデックスにあるコードが、左に1つのパディングビットを追加して、次のブロックの同じインデックスで繰り返されることを意味します。

例えば、最初のブロックの2番目のコードが0001の場合、2番目のブロックの2番目のコードは10001になります。同様に、3番目のブロックの2番目のコードは110001などになります。

この自己相似パターンは、各連続ブロックでコードを1ビット長く強制することによって自然に発生します。具体的な例を見てみましょう。

自己相似コードの例

ブロックサイズがm=5で、最初のブロックのコードがk=4ビット幅だとしましょう。

最初のブロックの最初のコードが0110の場合、前のコード値に1を加えることで、ブロック内の残りのコードを生成できます。最初のブロックのコードは次のようになります。

ご覧のとおり、最初のブロックはコード1010で終わります。次のコードの自然な値は1011になるはずですが、このコードは次のブロックに属するため、1ビット長くなる必要があります。その結果、1ビット左にシフトする必要があり、10110になります。このコードの最後の4ビットが最初のブロックの最初のコードと同じであることに気づくかもしれません。次の図はこれを視覚的に強調しています。

[画像: An example of self-similar codes. The first code in the first block are same as least 4 bits of the first code in the 2nd block]

ここで注目すべきもう一つの点は、2番目のブロックの最初の値は1ビット左にシフトして取得していることです。つまり、その最下位ビット(LSB)は常に0です。
自己相似パターンを形成するためには、最初のブロックの最初のコードのLSBも常に0である必要があります。これは、この最初のコードが常に偶数であり、2xの形式であることを意味します。

自己相似コードには、最初のブロックのコードの最小ビット幅kを決定する直感的な方法を提供する追加のプロパティがいくつかあります。見てみましょう。

コードのビット幅

最初のブロックをエンコードするために必要な最小ビット数を特定するために、最初のブロックの最初のエンコード値が2xであると仮定しましょう。

次に、2番目のブロックの最初のコードは2x + mであるべきです。しかし、次のブロックのコードは1ビット幅が広くなる必要があるため、この値は左に1ビットシフトされ、2(2x + m)になります。

値を1ビット左にシフトすると、値は2倍になります。

自己相似パターンは、これらのコードを別の方法で考えることを可能にします。最初のブロックの最初のコードが2xの場合、次のブロックでは:

  • 同じパターン(2x)を望みます。
  • 左に余分なビットを追加します。
  • 左にビットを追加することは、2^kを追加することと同等です。
  • したがって、コードは2^k + 2xになります。

これらの2つの関係を組み合わせると、次の式が得られます。

(\begin{align*}&2^k + 2x = 2(2x + m) \ &\text{または、} 2^k = 2m + 2x \ &\text{ここで、xは非負整数なので、上記を次のように単純化できます。} \ &2^k \ge 2m \end{align*})

kの最小整数値について解くことで、最初のブロックのコード幅を得ることができます。

同じ方程式はxの値も与えます。

(\begin{align*}\text{x} = 2^{(k-1)} - m = 2^{\lceil \log_2 m \rceil} - m \end{align*})

m、k、xの値がわかると、シンプルなエンコーディングアルゴリズムが得られます。

エンコーディングアルゴリズム

Golombの論文はエンコードとデコードのための異なるアルゴリズムを提供しましたが、Unix spellコードは、より複雑ですがより効率的なアルゴリズムを使用しました。Unix spellに実装されているアルゴリズムを説明します。

値のエンコード方法を理解しましょう。以下を思い出してください。

  • 初期ビット幅k
  • ブロックサイズm
  • 最初のブロックの最初のコードは2xで、x = 2^(k-1) - mです。

エンコーディングアルゴリズムは次のとおりです。

次の図は、値2と8に対してアルゴリズムが実際にどのように機能するかを示す2つの例です。

[画像: Examples of how the encoding algorithm works for values 2 and 8]

元のUnix svr4の実装はこちらで見つけることができます。

デコーディングアルゴリズム

デコードプロセスもそれほど複雑ではありません。コードが与えられたら、次のことを行う必要があります。

  1. まず、上位k-1ビット(wと呼びます)を確認します。
    • wがx未満の場合、これは短いコードです。
    • デコードされた値は単純にw自体です。
  2. w ≥ xの場合、次のことを行う必要があります。
    • wにさらに1ビット含めます。
    • wの最下位kビットを確認します。これをuと呼びます。
    • u < 2x + mの場合:
      • value = x + u + (s - 1)m
      • ここでsはwに含まれる追加ビット数です。
    • それ以外の場合:
      • u < 2x + mになるまで、wにさらにビットを含め続けます。

元のUnix svr4のデコードアルゴリズムの実装はこちらで見つけることができます。

Golombコードの圧縮効率

では、この手法はハッシュ差分をどれほどうまく圧縮できたのでしょうか?

理論的限界の圧縮は1語あたり13.57ビットであったことを思い出してください。Golombコードは、期待コード長13.60ビットを達成し、この理論的最小値に驚くほど近くなりました。

しかし、この圧縮された辞書で値を検索するのは非常に遅かったです。最初から開始し、デコードして値を合計し、目的のハッシュコードを見つけるか超えるまで繰り返す必要がありました。

これを高速化するために、最終的なUnix spell実装では、差分テーブルをM個のビンにパーティション化しました。これにより、まず正しいビンを特定し、そのビン内のみをスキャンすることで、検索をM倍高速化することができました。

このパーティション化スキームでは、ビンへの追加ポインタを格納する必要があり、ストレージ要件に1語あたりlog₂Mビットが追加されました。総ストレージは約1語あたり14ビットに増加しましたが、これは許容できるトレードオフでした。メモリ予算内に収まりながら、大幅に高速な検索を提供しました。

Share

結論

Unix spellコマンドは、PDP-11の厳しいメモリ制約から生まれた、魅力的なエンジニアリングの歴史の一部です。特に興味深いのは、単純なディスクベースの辞書検索から、複数のコンピュータサイエンスの概念を組み合わせたエレガントなソリューションへと進化した点です。

  • 確率的データ構造(ブルームフィルタ)
  • 情報理論(最適なビット幅計算)
  • 確率論(幾何分布)
  • 圧縮アルゴリズム(Golombコーディング)

エンジニアリングの旅は特に教育的です。

  1. 許容できる偽陽性率を達成したブルームフィルタから開始。
  2. 辞書サイズが増加した際、圧縮ハッシュに切り替えました。
    • 理論的最小ビット数を計算。
    • ハッシュ差分のパターンを認識。
    • Golombコードを使用してほぼ最適な圧縮を達成。
    • 最小限のスペースオーバーヘッドで高速検索のためにビンを追加。

現代のスペルチェッカーは異なる技術(編集距離や言語モデルなど)を使用していますが、Unix spellからのエンジニアリングの洞察は依然として価値があります。理論的概念の深い理解と実践的な制約の組み合わせが、効率的でエレガントなソリューションにつながることを示しています。

最も重要なのは、リソースが制約されているときに、より多くのハードウェアを投入するのではなく、問題についてより深く考えることを強制されることで、最高のイノベーションが生まれることを示している点です。

参考文献

Confessions of a Code Addictをサポート

私の仕事が興味深く価値があると感じた場合は、有料サブスクリプション(月額$6.40/年額$58)を選択してサポートできます。特典として、毎月のライブセッションへのアクセスと、過去のすべての録画にアクセスできます。

登録済み

多くの人が支払い失敗を報告したり、定期購読を希望しない場合があります。そのため、buymeacoffeeページもあります。コーヒーを買ったり、メンバーになることができます。同等の期間で有料サブスクリプションにアップグレードします。

Buy me a coffee

GitHubスポンサーページもあります。スポンサーバッジが表示され、ここでの有料サブスクリプションも無料で提供されます。

Sponsor me on GitHub