- 1970年代のAT&TのUnix spellは、PDP-11の64KB RAM内で250KBの辞書を高速に検索する必要があり、Douglas McIlroyは汎用圧縮ではなくデータの特性を利用して解決した
- Steve Johnsonの初期プロトタイプはディスクベースだったため遅く、精度も低かったが、McIlroyは語幹抽出で辞書を25,000語程度まで削減し、性能と精度を改善した
- 最初のインメモリ構造はDennis Ritchieが実装したBloom filterで、400,000ビットのテーブルと11個のハッシュ関数により、約1/2000の偽陽性率を実現して別途の辞書検索を省略した
- 辞書が30,000語に増えるとBloom filterだけではメモリ制約を満たすのが難しくなり、27ビットのハッシュをソートしたうえでハッシュ差分をGolomb codeで圧縮した
- 最終実装では、圧縮された差分テーブルを複数のbinに分割して検索速度を高め、1語あたり約14ビットの保存量で64KB内で高速なスペルチェックを可能にした
Unix spellが直面したメモリ制約
- 中核となる問題は、250KBの辞書を64KB RAM環境で高速に検索することだった
gzip -9のような現代的な圧縮を適用しても、このファイルは85KB未満にはならない- 1970年代のPDP-11では辞書全体をメモリに載せることはできず、ディスクベースの検索は低速だった
- McIlroyは汎用圧縮ではなく、辞書データの構造と確率分布を活用する専用データ構造を設計した
初期のUnix spellと語幹ベースの辞書縮小
- AT&TでUnixを特許部門向けのテキスト処理システムとして提案する中で、スペルチェッカーが必要になった
- Steve Johnsonは1975年に最初のUnix spellプロトタイプを書き、Jon Bentleyはこの作業がある午後に作られたものだと伝えている
- 初期版は入力ファイルを単語ストリームに分割し、数字・特殊文字の除去、小文字化、ソート、重複排除を経て、ディスク上の辞書で単語の存在有無を確認した
- 単純なディスク検索方式は遅く、精度も低かった
- McIlroyは性能と精度を高めるため、2つの部分を再設計した
- 接頭辞・接尾辞を取り除いて単語を語幹に縮約するアルゴリズム
- 辞書をメモリに載せて高速に検索する圧縮データ構造
接頭辞・接尾辞除去アルゴリズム
- McIlroyの語幹抽出方式は、単語から一般的な接頭辞と接尾辞を繰り返し取り除いた後、縮約された単語が辞書にあるかを確認するものだった
- 例えば
misrepresentedは接頭辞mis、reと接尾辞edを取り除き、presentに縮約される
presentが辞書にあれば、元の単語を誤字として表示しない- この方式は100%正確ではなく、一部の誤字を通過させる可能性があったが、当時は許容できる水準と判断された
- よくある誤りを避けるための例外ルールも併せて実装された
- 最終的な辞書は25,000語に減り、よく設計されたデータ構造であればメモリに載せられる規模になった
Bloom filterベースの検索
- McIlroyが最初に使ったインメモリ構造は、当時の論文で「superimposed code scheme」と呼ばれたBloom filterだった
- Bloom filterの論文は1970年に発表され、Unix spellは1970年代半ばに開発された
- この実装はDennis Ritchieが提供した
- Bloom filterはビットテーブルを0で初期化し、項目ごとに複数のハッシュ関数を適用して、対応するビットを1に設定する
- 検索時にも同じハッシュ関数を適用する
- 1つでも0のビットがあれば、その項目は存在しない
- すべてのビットが1なら存在する可能性があるが、**偽陽性(false positive)**の可能性が残る
- 一般的なBloom filterでは偽陽性を処理するために実際の辞書検索が必要だが、スペルチェッカーでは大半の単語が辞書に存在するため、辞書全体の検索が頻発し得る
- McIlroyは偽陽性率を十分に低くし、実際の辞書検索を省略した
- 許容偽陽性率は1/2000
- 辞書の単語数は25,000語
- ビットテーブルサイズは400,000ビット
- ハッシュ関数は11個
- この組み合わせで偽陽性率を約1/2000の水準に合わせた
Bloom filterの限界と圧縮ハッシュ方式
- Bloom filter方式はしばらく使われたが、新しい単語が追加され続け、辞書は25,000語から30,000語に増えた
- 同じ偽陽性率を維持するにはより大きなビットテーブルが必要だったが、メモリ制約のため難しかった
- McIlroyはハッシュテーブル全体ではなく、単語のハッシュ値だけを保存する方式へ切り替えた
- 検索は入力単語のハッシュを計算し、保存済みハッシュ一覧で存在有無を確認する方式で動作する
- ハッシュ衝突の可能性を下げるには、十分に大きなハッシュコードが必要だった
- 辞書サイズ
vは約30,000、つまり約2^15
- 許容衝突確率は
1 / 2^12
- 必要なハッシュサイズは27ビット
- 27ビットのハッシュを30,000個保存するとPDP-11の64KB RAMに収まらないため、圧縮が必須だった
理論上の圧縮限界
- McIlroyはまず、ハッシュコード集合を保存するのに必要な理論上の最小ビット数を計算した
- ハッシュコードのサイズが
bビットなら、可能なハッシュコードは2^b個であり、その中からv個の一意なハッシュコードを選ぶ場合の数を情報量に換算した
- 計算にはStirling近似と、
v « 2^bという単純化した仮定が使われた
v=30,000、b=27を代入すると、単一のハッシュコード保存に必要な最小値は13.57ビットになる- これは元の27ビットハッシュより約50%短く、PDP-11のメモリ容量内に収まる水準だった
ハッシュ差分の保存と検索
- McIlroyは元のハッシュコードをそのまま圧縮するのではなく、ソートされたハッシュコード間の差分を保存した
- 例は次のとおり
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- 差分保存には2つの利点があった
- 差分値は元のハッシュコードより小さい
- 複数のハッシュコード対で同じ差分値が繰り返される可能性がある
- 検索は入力単語のハッシュを計算した後、差分を先頭から累積する
- 累積和が入力ハッシュと同じなら存在する
- 累積和が入力ハッシュを超えれば存在しない
- 保存空間は減るが、圧縮された値を先頭からデコードして累積する必要があるため、検索が遅くなり得る
ハッシュ差分の幾何分布モデリング
- 可逆圧縮は、頻繁に現れる値に短いコードを、まれな値に長いコードを割り当てると効率が高い
- 一般的な確率分布表ベースの圧縮は、McIlroyの制約には合わなかった
- 約30,000個のシンボルの確率分布表をメモリに保持すると、圧縮の利得が失われる
- 差分値の頻度と確率を計算するには、コストの大きいディスクベースの構造が必要になる
- McIlroyはハッシュ差分が幾何分布に従う点を利用した
- ハッシュ空間は
2^b個の地点で、その中にv個のハッシュコードが分布する
- ある地点にハッシュがある確率は
q = v / 2^b
- 空である確率は
p = 1 - v / 2^b
- 差分
kは、あるハッシュの後ろのk-1個の位置が空で、k番目の位置に次のハッシュがあるときに発生する
- したがって差分
kの確率はp^(k-1)qとなり、幾何分布の形と一致する
Golomb codeによる差分圧縮
- McIlroyは幾何分布の整数に適したGolomb codeでハッシュ差分を圧縮した
- Golombの1965年の論文は、幾何分布値のための単純なランレングス符号化方式を提供した
- 幾何分布では確率が指数関数的に減少するため、値をサイズ
mのブロックにまとめ、次のブロックへ進むほどコード長を1ビットずつ増やす構造を作れる
- Unix spellの実装はGolombの論文の方式とは異なる、少し複雑だが効率的なエンコード・デコードアルゴリズムを使用した
- 元のSVR4実装は次の場所で確認できる
- Golomb codeはハッシュ差分を1語あたり13.60ビットの期待符号長に圧縮する
- これは理論上の最小値である13.57ビットに非常に近い結果だった
検索速度のためのbin分割
- 圧縮された差分テーブルだけを使うと、検索時に最初からデコードして累積する必要があるため遅い
- 最終的なUnix spell実装では、差分テーブルを
M個のbinに分割した
- 検索時にはまず該当するbinを見つけ、その中だけをスキャンする
- この方式は検索速度を
M倍高める
- その代わりbinポインタを保存する必要があるため、1語あたり
log₂Mビットの追加保存空間が必要になる
- 全体の保存量は1語あたり約14ビットに増えたが、メモリ予算内ではるかに高速な検索を提供するトレードオフになった
Unix spellが示した制約ベースの設計
- Unix spellはBloom filter、情報理論、確率論、Golomb圧縮を組み合わせた設計事例である
- 開発過程は次の流れで進んだ
- Bloom filterで低い偽陽性率を達成した
- 辞書が大きくなると圧縮ハッシュ方式へ切り替えた
- ハッシュ保存の理論上の最小ビット数を計算した
- ハッシュ差分の分布を認識した
- Golomb codeでほぼ最適に近い圧縮を達成した
- bin分割で小さな空間オーバーヘッドだけを追加し、検索を高速にした
- 現代のスペルチェッカーはedit distanceや言語モデルのような別の手法を使うが、Unix spellは理論的理解と実際の制約を組み合わせ、効率的なシステムを作った事例として残っている
1件のコメント
Hacker Newsのコメント
ごく少ないRAMでも外部メモリ型のスペルチェッカーは作れる。文書内の単語をソートし、重複しない単語に絞ったうえで、ソート済みの辞書とマージして、存在しない単語だけを残す、というやり方だ。
この方式をCreative ComputingのBASICの例で見たことがあり、利用可能なRAMが32KBよりずっと少なかったTRS-80 Color Computerで動くようにしたので、タイトルを見た瞬間にまずそれを思い出した。
当時のTurbo Lightningは人々を驚かせた。圧縮辞書がPC上で実行中の他のプログラムと同居しつつ、入力中にスペルチェックを行っていたからだ。
PCには640KBの制限があったが、他のプログラムの邪魔をしないためにはその一部だけを使う必要があり、PC初期にはそのメモリを満杯まで搭載するのもコスト的に簡単ではなかった。
作業用コピーをいったんディスクに保存し、ソートし、比較してから再び読み込む方式も可能だっただろうが、C=64の開発者たちはディスクインターフェイスがあまりに遅かったため、そうした戦略は避けたのではないかと思う。
当時はBloomフィルタはまだBloomフィルタとは呼ばれておらず、Douglasは論文で「superimposed code scheme」と呼んでいた、というくだりがあるが、Bloomフィルタはsuperimposed codeの特定の種類だ。
Calvin Mooersは1940年代のMIT修士論文で、Shannonの影響を直接受けてランダムなsuperimposed codingを発展させた。
Bourneによる1963年の優れた本『Methods of Information Handling』には数学的な詳細が載っている。
Douglasはより広い手法を知っていたはずだと確信している。たとえば「The Large Data Base File Structure Dilemma」（1975）の著者も、http://dx.doi.org/10.1021/ci60001a005でこれを「super-imposed codingという古い手法」と表現していた。
ここで「ランダム」という限定語が重要だ。Mooers以前にもsuperimposed codeは存在したが、数学的に興味深いものでも、実用上重要なものでもなかったからだ。
「worse is better」にしては賢すぎる。もっと悪い方向で考えるべきだ。
主記憶の帯域幅とディスク帯域幅がほぼ同じで、どちらも1MB/sを少し超える程度だった。
自分なら複数パス方式にしたと思うが、それでもBloomフィルタは格好いいので使っただろう。
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
元論文も素晴らしい: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
彼のWebページにも掲載されている: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
単語オタクなら「obovate」を調べるうちに、この葉の形態チャートも見ることになるだろう。
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
製品名は覚えていないが、80年代にIBM PC用のハードウェア・スペルチェッカーがあった。キーボードとPCの間に接続する箱で、辞書語として認識できない文字列を入力するとビープ音で知らせてくれた。
https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf の237ページにレビューがある。大きなPDFなので注意。
Unixに興味を持つきっかけの一つが、1980年代初めごろのByteの記事だった。split/sort/commのパイプラインでスペルチェッカーを作る過程を示していて、たしか7個ほどのコマンドだった。
8ビットPCにはそんなものはまったくなかったが、実際に見てみると、それほど大した複雑さが必要なわけでもなさそうだった。
https://youtu.be/tc4ROCJYbm0?t=4m56s
いまようやく記事を全部読み終えたが、要点はこうだと思う。30,000語の「辞書」があり、約1/4000の偽陽性率を受け入れるなら、各単語を27ビット文字列、つまり整数にハッシュ化して、辞書は捨て、30,000個の27ビット文字列の集合を保存する問題に変換できる。
やや驚くことに、情報理論によれば、30,000個の27ビット文字列は、1単語あたり27ビットではなく約13.57ビットだけで保存できる。数学は理解できるが（https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000）、30,000が2^27、つまり約1億3400万に比べてあまりに小さいので、どこから得をしているのか直感的に受け入れるには時間がかかりそうだ。
この30,000個からなる27ビットハッシュの部分集合をエンコードするためにハッシュの差分を使い、この差分が幾何分布に従うため、幾何分布の入力に合わせたGolomb符号化で、実際に1語あたり約13.6ビットを達成していた。
「完全ハッシュ」のような方向で、原理的にもっと良くできるのか考えてみた。アルファベットの単語を受け取り、何らかの変換を経たあと、結果のハッシュが良い集合に属しているかを簡単に検証できる関数があるのではないかと思った。
しかし考え直すと、偽陽性率が必要なので、辞書にない単語が「良い」集合にマッピングされないようにするには、ハッシュに少なくとも27ビットが必要だ。この方式は基本的に理論上最適に見える。あるいは各単語を27ビット整数にマッピングしつつ、良い文字列をたとえば値が30000未満のものにできる方法が存在するのだろうか？
参考までに、1983年ごろのCP/M向けGrammatikは64KB未満で動作し、8ビットシステム上で「文法チェック」を行っていた。実際にはスペルチェックにエキスパートシステムのルールを加えた形だった。
記憶に残っているのは、面白い部分を掘り下げたからで、それほど小さくできた理由はForthで書かれていたためであり、製品の中に外部インタプリタが十分入っていたので、少し16進編集するだけで、専用関数があらかじめロードされたForthインタプリタのように使えた。
どう動くのか見るために逆コンパイルはしていないが、小さく、高速で、うまく動く。
ハッシュ化のせいで、どんなよくあるタイプミスを見逃すのか気になる。
関連して、Wordle辞書圧縮コンテストもある: http://golf.horse/wordle/
80年代半ばに似たようなことを経験した。速いというのは相対的な言葉だ。
データは大量にあり、RAMは640KB、ヒープは64KB、スタックは64KBだった。数百MBからデータを検索して抽出し、一部を結合する必要があった。
データを三分探索木形式のインデックス構造にする実験をした。概念的には筋が通っていたが、実装してみると、関係と経路情報だけでも64KBに収めるには大きすぎた。
圧縮の代わりにスワッピングを選んだ。TSR、今で言えばサービスのようなコードを書き、データの塊を処理して結果を抽出し、スタックに保存してから元データを捨て、TSRに割り込み呼び出しを送った。するとTSRがヒープを破棄し、ストレージから次の塊を読み込んで制御をプログラムに戻し、プログラムは処理してスタック上のデータと結合し、全体が終わるまで繰り返した。
もともとこの作業には、データ入力担当者3人が約1週間と、情報を結合する専門家が必要だった。3インチのリングバインダー12冊ほどの表を思い浮かべればいい。プログラムは数時間で終わらせ、驚くほど「速かった」。
シングルスレッドのシステムでやったことだった。
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
UNIX spellでイギリス式の綴りを使うために
-bオプションを使っていた記憶がある。言語オプションは2つしかなかったが、なぜそう決めたのか、コードがそれをどう扱っていたのか、それぞれの辞書がどこから来たのかが気になる。オーストラリアやニュージーランドの人たちはイギリス式の綴りを使っていたのだろうか、それともアメリカ式の綴りを使っていたのだろうか？
UNIX spellはスペル分野におけるZX81 1Kチェスのような存在で、家庭用コンピュータではWindows 3.1向けMS Wordが出るまで、スペルチェックはそれほど多くなかった。その前のオフィスでは、秘書たちがWordPerfectでタイピングし、各管理職やチームにとって人間のスペルチェッカーの役割を果たしていた。
一方、家ではドットマトリクスプリンタとちらつく画面を使い、初期コンピューティングの時代を通じて紙の辞書に頼りながら何とかやっていた。当時はみんな綴りを書くことができたので、スペルチェックがそれほど重要だった記憶はない。生徒1000人の学校で、ディスレクシアだと主張していた子は1人だけで、綴りが書けないことへのもっともらしい言い訳になっていた。
もしかすると1980年代こそがリテラシーの黄金期で、綴り能力衰退の明確な開始日はUNIX spellが書かれた日だったのかもしれない。
Scrabbleが好きだ。スペルチェックとはかなり異なる問題だが、処理過程はUNIX spellといくつかの段階を共有している。よくある単語の接頭辞や接尾辞を探し、ラックやボード上の他の構成要素とつなげる。
Scrabble辞書も、意味を提供しない大きな単語リストにすぎないという点で、UNIX spellに少し似ている。重要なのは、与えられた単語が本に載っているかどうかだけだ。102個の2文字単語のような特殊な参照表もいくつかある。
辞書をディスクから読みながらチェックしていたので数分かかり、その後、一致しなかった単語を確認できた。