stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(7): 辞書の圧縮

前回は、MapReduce を使った分散インデキシングと、ログマージによる動的インデキシングについて説明した。今回は、インデックス圧縮技術の1つである辞書の圧縮について解説する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の7日目の記事です。

adventar.org

転置インデックスの圧縮

  • 一般的な圧縮のメリット
    • ディスクスペースの節約
    • メモリ内により多くのものを入れられる
    • ディスクからメモリへの転送速度を上げられる
      • 圧縮済みデータを転送して展開するのは、展開済みデータを読み込むよりも速い
      • これから説明する展開アルゴリズムは展開が速いので
  • 転置インデックスの圧縮
    • 辞書
      • メインメモリ内に置きたいので小さくしておきたい
    • ポスティングファイル
      • 必要なディスクスペースを削減したい
      • ディスクからポスティングリストを読み込む時間を減らしたい
      • 大規模な検索エンジンは、ポスティングの重要な部分はメインメモリに持っている
        • 圧縮するとより多くのポスティングをメモリに置ける
  • このあと、様々な情報検索特有の圧縮手法について説明する

タームの統計的性質

  • タームの語彙数 = ユニークな単語の数
    • 上限を仮定できない(文字が Unicode ならなおさら)

Heap の法則

  • Heap の法則 (Heap's law)
    • M = kT^b
      • M: 語彙数
      • T: コレクション中のトークン総数
      • 典型的には 30 <= k <= 100 かつ b ~ 0.5
  • MT の両対数プロット (log-log plot) は傾きが約 1/2 の直線になる
    • Heap の法則の推定
    • log M = log k + b log T という線形の関係
    • Heap の法則は経験則

f:id:takuya-a:20201207235819p:plain
(IIR p.88 Figure 5.1) Reuters-RCV1 での M と T の両対数プロット

  • 点線は Heap の法則によるフィッティングで、 log_10 M = 0.49 log_10 T + 1.64 の直線
    • M = 10^1.64 T^0.49
    • k = 10^1.64 ~ 44b = 0.49
  • Reuters-RCV1 ではよくフィットしている

Zipf の法則

  • Heap の法則は、コレクション中の語彙数を予測した
  • (相対的な)ターム頻度についても議論する
  • 自然言語では、いくつかの非常に高頻度な単語と、非常に多いとてもレアな単語とがある
  • Zipf の法則 (Zipf's law)
    • 「頻度が i 番目に多い単語の頻度は 1/i に比例する」
    • cf_i ∝ 1/i = K/i
      • K: 正規化の定数
      • cf_i: コレクション頻度(コレクション中のターム t_i の出現回数)
  • 最も頻度(出現回数)の多い単語 (the) の出現回数が cf_i だとすると
    • 2番目の単語 (of) は cf_1 / 2
    • 3番目の単語 (of) は cf_1 / 3
    • ...
  • cf_i = K/i (K は正規化の定数)とすると
    • log cf_i = log K - log i
    • log cf_ilog i のあいだに線形の関係がある

f:id:takuya-a:20201207235858p:plain
(IIR p.90 Figure 5.2) Reuters-RCV1 での Zipf の法則

辞書の圧縮

  • 辞書は検索のたびに使われるのでメモリ上に置きたい
  • そのため、辞書の圧縮は非常に重要

固定長配列による辞書

  • 固定長の配列で辞書を表現する
    • 辞書のナイーブなバージョン
    • 40 万タームあった場合、タームあたり 28 バイトなので全体で 11.2 MB 必要
      • しかもこれはタームがアルファベットで、かつ最大 20 文字の場合

f:id:takuya-a:20201207235939p:plain
(IIR p.91 Figure 5.3) 辞書を固定長配列として保存

  • 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

f:id:takuya-a:20201208000011p:plain
(IIR p.92 Figure 5.4) Dictionary-as-a-string

ブロック化

  • タームへのポインタを、k タームごとに保存する
    • たとえば k = 4
  • タームの長さを、ターム文字列とターム文字列の間に保存する必要がある(+ 1バイト必要)

f:id:takuya-a:20201208000219p:plain
(IIR p.93 Figure 5.5) ブロック化

  • ブロックサイズ k = 4 のとき、ターム4つごとにポインタのために必要なスペースは
    • ブロック化なし:ポインタごとに 3 バイト必要だったので 3 * 4 = 12 バイト
    • ブロック化あり:3 + 4 = 7 バイト
  • 辞書全体では 7.6 MB --> 7.1 MB
    • k を大きくするとさらに小さくなる

辞書検索

f:id:takuya-a:20201208002729p:plain
(IIR p.94 Figure 5.6) 無圧縮の辞書検索 (a) と ブロック化で圧縮した場合の辞書検索 (b)

  • ブロック化なしでの辞書検索 (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

Front coding

  • ソート済みの単語は長い共通接頭辞をもつことが多い
    • 差分のみを保存する

f:id:takuya-a:20201208002808p:plain
(IIR p.94 Figure 5.7) Front coding による辞書圧縮

  • 辞書に "automata", "automate", "automatic", "automation" の4つのタームがある(ブロック化済み)
  • "automat" が共通接頭辞
    • 共通接頭辞あとには特殊記号 * を置く
  • そのあと、差分の文字列と、その長さを置く
    • そのあとにはそれぞれ特殊記号 を置く

辞書圧縮の効果

f:id:takuya-a:20201208002837p:plain
(IIR p.95 Table 5.2) Reuters-RCV1 での辞書圧縮

  • ブロック化と Front coding による圧縮で 5.9 MB まで小さくなる

講義資料

参考資料