Information Retrieval and Web Search まとめ(7): 辞書の圧縮
前回は、MapReduce を使った分散インデキシングと、ログマージによる動的インデキシングについて説明した。今回は、インデックス圧縮技術の1つである辞書の圧縮について解説する。
この記事は Information Retrieval and Web Search Advent Calendar 2020 の7日目の記事です。
転置インデックスの圧縮
- 一般的な圧縮のメリット
- ディスクスペースの節約
- メモリ内により多くのものを入れられる
- ディスクからメモリへの転送速度を上げられる
- 圧縮済みデータを転送して展開するのは、展開済みデータを読み込むよりも速い
- これから説明する展開アルゴリズムは展開が速いので
- 転置インデックスの圧縮
- 辞書
- メインメモリ内に置きたいので小さくしておきたい
- ポスティングファイル
- 必要なディスクスペースを削減したい
- ディスクからポスティングリストを読み込む時間を減らしたい
- 大規模な検索エンジンは、ポスティングの重要な部分はメインメモリに持っている
- 圧縮するとより多くのポスティングをメモリに置ける
- 辞書
- このあと、様々な情報検索特有の圧縮手法について説明する
タームの統計的性質
- タームの語彙数 = ユニークな単語の数
- 上限を仮定できない(文字が Unicode ならなおさら)
Heap の法則
- Heap の法則 (Heap's law)
M = kT^b
M
: 語彙数T
: コレクション中のトークン総数- 典型的には
30 <= k <= 100
かつb ~ 0.5
M
とT
の両対数プロット (log-log plot) は傾きが約1/2
の直線になる- Heap の法則の推定
log M = log k + b log T
という線形の関係- Heap の法則は経験則
- 点線は Heap の法則によるフィッティングで、
log_10 M = 0.49 log_10 T + 1.64
の直線M = 10^1.64 T^0.49
k = 10^1.64 ~ 44
、b = 0.49
- Reuters-RCV1 ではよくフィットしている
Zipf の法則
- Heap の法則は、コレクション中の語彙数を予測した
- (相対的な)ターム頻度についても議論する
- 自然言語では、いくつかの非常に高頻度な単語と、非常に多いとてもレアな単語とがある
- Zipf の法則 (Zipf's law)
- 「頻度が i 番目に多い単語の頻度は
1/i
に比例する」 cf_i ∝ 1/i = K/i
K
: 正規化の定数cf_i
: コレクション頻度(コレクション中のタームt_i
の出現回数)
- 「頻度が i 番目に多い単語の頻度は
- 最も頻度(出現回数)の多い単語 (the) の出現回数が
cf_i
だとすると- 2番目の単語 (of) は
cf_1 / 2
回 - 3番目の単語 (of) は
cf_1 / 3
回 - ...
- 2番目の単語 (of) は
cf_i = K/i
(K
は正規化の定数)とするとlog cf_i = log K - log i
log cf_i
とlog i
のあいだに線形の関係がある
辞書の圧縮
- 辞書は検索のたびに使われるのでメモリ上に置きたい
- そのため、辞書の圧縮は非常に重要
固定長配列による辞書
- 固定長の配列で辞書を表現する
- 辞書のナイーブなバージョン
- 40 万タームあった場合、タームあたり 28 バイトなので全体で 11.2 MB 必要
- しかもこれはタームがアルファベットで、かつ最大 20 文字の場合
term
カラムは、1文字のタームでも 20 バイト消費する- 英語の単語は平均して ~4.5 文字
- 辞書内の単語は ~8 文字
- しかも、20 文字以上のタームは扱えない
タームリストの圧縮: 文字列としての辞書
- 文字列としての辞書 (dictionary as a string)
- 辞書を(非常に長い)文字列として保存する
- 最大で 40% のスペースを節約できると期待できる
- ターム頻度の保存に 4 バイト
- ポスティングへのポインタに 4 バイト
- タームへのポインタに 3 バイト
- タームの文字列は平均 8 バイト
- 400K ターム * (4 + 4 + 3 + 8) = 7.6 MB
- 固定長配列では 11.2 MB
ブロック化
- タームへのポインタを、
k
タームごとに保存する- たとえば
k = 4
- たとえば
- タームの長さを、ターム文字列とターム文字列の間に保存する必要がある(+ 1バイト必要)
- ブロックサイズ
k = 4
のとき、ターム4つごとにポインタのために必要なスペースは- ブロック化なし:ポインタごとに 3 バイト必要だったので 3 * 4 = 12 バイト
- ブロック化あり:3 + 4 = 7 バイト
- 辞書全体では 7.6 MB --> 7.1 MB
k
を大きくするとさらに小さくなる
辞書検索
- ブロック化なしでの辞書検索 (Figure 5.6a)
- 各タームが同じ確率で検索されると仮定すると(実際には異なるが)、平均的な比較回数は
(1 + 2 * 2 + 4 * 3 + 4) / 8 ~ 2.6
- 各タームが同じ確率で検索されると仮定すると(実際には異なるが)、平均的な比較回数は
- ブロック化ありでの辞書検索 (Figure 5.6b)
- 二分探索は 4 タームのブロックごとになる
- そのあと、ブロック内を線形探索
- 比較回数は平均で
(1 + 2 * 2 + 2 * 3 + 2 * 4 + 5) / 8 = 3
- 二分探索は 4 タームのブロックごとになる
Front coding
- ソート済みの単語は長い共通接頭辞をもつことが多い
- 差分のみを保存する
- 辞書に "automata", "automate", "automatic", "automation" の4つのタームがある(ブロック化済み)
- "automat" が共通接頭辞
- 共通接頭辞あとには特殊記号
*
を置く
- 共通接頭辞あとには特殊記号
- そのあと、差分の文字列と、その長さを置く
- そのあとにはそれぞれ特殊記号
⋄
を置く
- そのあとにはそれぞれ特殊記号
辞書圧縮の効果
- ブロック化と Front coding による圧縮で 5.9 MB まで小さくなる
講義資料
- Index Compression (pdf)
- Dictionary Compression
参考資料
- IIR chapter 5
- MG sections 3.3-3.4