連想配列の進化

キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。

特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。
この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。
例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。
そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。

ここではこのような連想配列の中でも、キーの情報を格納することすら難しい場合を考えます。

この場合は、最小完全ハッシュ関数(MPHF)を利用することにより、キー自体の情報を格納しなくても連想配列を実現することができます。最小完全ハッシュ関数はN個のキー集合が与えられた時、これらのキーに対するハッシュ値が衝突しないことが保障され、かつ、その値域が[0, N-1]であるような関数です。
近年の研究により、このようなMPHFを1.44N + o(n) bitsで現実的な時間で実現することが可能となっています（例えばbepなどの資料を参考にしてください）

MPHFは[0, N-1]中の値を返すだけなので、それに対し値を紐付ける必要があります。値の範囲が[0, σ-1]のとき、lg σ bitで各値を表すことができるので（lg x = log_2 x)、n lg σ bitsあれば、値を格納することができます。

これでN個のキーに対する連想配列は(1.44 + lgσ) N + o(n) bitsで格納でき、定数時間で値を参照することができることがわかりました。

実際このような連想配列はすでに言語モデルなどで利用されています[1][2]．

＃登録されていないキーが入力に来た場合、これに対しNOと常に正しく答えられるようにするためには、キーすべてを格納するのと同じ容量が必要になります。もしわずかな誤り（偽陽性）を許せるのであればブルームフィルターなどを使って大幅に作業容量を減らすことができるが、この辺の話は今回は割愛

さらに圧縮したいと思うのは人の性なのか。
これよりさらにコンパクトに格納する手法が提案されました[3]．

今のデータ構造では値の冗長性を利用していません。例えば、先ほどのN-gramの頻度情報（実際はその対数値を丸めたもの）などでは、値の出現分布は非常に偏った分布になります。

実際[3]の論文では1要素あたり
(1 + σ)H0 + min(p1 + 0.086, 1.82(1-p1)) bits
で保存可能な連想配列を提案しています。H0は値の分布の0次経験エントロピー、つまり値を格納するのに必要な最低限必要なbit数です。lgσ>=H0が成り立ち、値の出現分布が非常に偏っている場合はlgσ >> H0となります。また、p1は値の中で最も出現頻度が高かったものの確率です。

きちんとした議論は[3]を読んでもらうとして、ここでは非常に大雑把な解説を行います。

[3]では、MPHFを使わずに直接、格納する値をハッシュ関数を利用して記録します。MPHFを格納するのに必要な作業領域量の下限が1.44Nとわかっているため、これ以上小さくしようとするとMPHFは使えません。

まず連想配列の値はhuffman木の変形を利用した符号であらわします。
そして、主となるデータ構造はビット配列Aのみです。

キーxが与えられた時、どのように値が計算されるかを説明します。
まず、k>=3個のハッシュ関数h1, h2, ..hkを用意して、キーxに対して、h1(x), h2(x), ..., hk(x)を計算します。そしてこれらをA中のオフセット値だとし、そこから長さwのビット配列を取り出します。
つまり取り出される値はA[h1(x)...h1(x)+w-1], A[h(x)...h2(x)+w-1]...です。
最後にこれらのビット配列のxorをとります。これが求めたい値のhuffman符号になります。これを定数時間で元の値を復元すれば値がわかります。

これがうまくいくようにハッシュ関数、そしてA中の値をうまく求めるというのが連想配列の構築部分になります。これはGF2の連立方程式を解く必要があり、計算量が大きくなりそうですが、実は高確率で高速に求められることが保証されています[4]．

[1]"Randomized Language Models via Perfect Hash Functions", D. Talbot, T. Brants, ACL 08
[2]"Stream-based Randomized Language Models for SMT", A. Levenberg, M. Osborne, EMNLP 09
[3]"Storing a Compressed Function with Constant Time Access", J. B. Hreinsson, M. Kroyer, R. Pagh, ESA 2009 [pdf | slides]
[4]"Succinct data structures for retrieval and approximate membership", M. Dietzfelbinger, R. Pagh, ICALP 2008