marisa-0.2.0-beta3 の公開と技術的なお話

先日の記事（検索時間が短くなりました - やた＠はてな日記）で述べたように，キャッシュの導入によって検索の高速化を実現しました．思い付いた時点ではブレイクスルーになると考えていたものですが，今となっては当たり前のアイデアのように感じてしまいます．

marisa-0.2.0-beta3 では，キャッシュへのマップ方法とキャッシュのサイズを調整したことにより，先日の段階と比べて辞書が小さくなり，検索は速くなっています．

• プロジェクト
  • http://code.google.com/p/marisa-trie/
• ソースコード
  • http://marisa-trie.googlecode.com/files/marisa-0.2.0-beta3.tar.gz

概要

基本的な考え方は，辿る確率の高い遷移に関する情報をキャッシュに保存しておくというものです．具体的には，遷移元と遷移先のノード番号，さらにラベルもしくは次の Trie へのリンク情報をキャッシュとして持つことにより，rank() や select() の計算を省略できるようにしました．

キャッシュの導入を考えた理由としては，Trie に特有の局所性が挙げられます．すなわち，根付近はアクセスが集中しやすいことであるとか，文字によって出現頻度が大きく偏るといったことです．日本語 Wikipedia のタイトル一覧を用いた実験では，わずか 0.1% のノードにアクセスの 40% 前後が集中するという結果になりました*1．

もう一つの理由としては，遷移にかかる計算コストの大きさが挙げられます．現在の実装では，先頭の子を求めるために select() が必要であり，リンク情報を取り出すために rank() が必要です．さらに，クエリと同じラベルを持つノードを探すために，線形探索をおこないます．つまり，遷移の度に，select() に 60-70 サイクル，rank() に 20-30 サイクル*2，おまけに線形探索のコストがかかります．

以上のことから，小さいキャッシュでも高いヒット率が期待できること，キャッシュにヒットしたときの効果が高いことが分かります．そして，英語版 Wikipedia のタイトル一覧を用いた実験では，サイズの増加を 1% 以下に抑えても，ノードの順序が重み順では 15-30% の高速化になり，ラベル順では 50-120% の高速化という劇的な成果が得られました．

キャッシュの構成

組み込むキャッシュは，辞書を構成する Trie に対して 1 つずつ用意しています．いずれもノード間の移動にかかる時間を短縮するために利用しますが，1 段目の Trie に対するキャッシュと 2 段目以降の Trie に対するキャッシュには違いがあります．

• 1 段目の Trie に対するキャッシュ
  • Reverse Lookup 以外は根から葉へと向かう探索になるため，葉方向への移動に対するキャッシュになっています．
• 2 段目以降の Trie に対するキャッシュ
  • 根方向への移動に対するキャッシュになっています．

ただし，キャッシュの構成は同じであり，以下に示すクラスの配列を使います*3．

class Cache {
 public:
  std::size_t parent() const { return parent_; }
  std::size_t child() const { return child_; }

  // link_ の上位 24 bits がすべて 1 の場合にのみ label() は有効になります．
  char label() const { return (char)(link_ & 0xFFU); }
  std::size_t link() const { return link_; }

 private:
  UInt32 parent_;
  UInt32 child_;
  UInt32 link_;
};

葉方向のキャッシュ（1 段目の Trie）

根から葉へと向かう探索では，ノード番号とラベルの組を入力として，子ノードの番号とリンク情報を求めることになります．キャッシュの使い方も同様であり，ノード番号とラベルの組が入力となり，キャッシュにヒットすれば，子ノードの番号とリンク情報が出力となります．ヒットしなければ，従来の方法で探索をおこないます．

ノード番号とラベルの組からキャッシュ番号を求める方法は，以下のようになっています．(node_id << 5) はキャッシュ番号の衝突を防ぐための小細工です．

std::size_t get_cache_id(std::size_t node_id, char label) const {
  return ((node_id) ^ (node_id << 5) ^ (UInt8)label) & cache_mask_;
}

葉方向のキャッシュで重要なことは，キャッシュのサイズを 256 以上にすることです．理由は，キャッシュのヒットを確認するとき，ノード番号の比較のみで済ませるためです．これは，ノード番号とキャッシュ番号からラベルを復元できるという特徴を利用しています．

結果として，キャッシュにラベルを格納する必要がなくなり*4，根方向のキャッシュと同じ構造体が使えるようになります．

根方向のキャッシュ（2 段目以降の Trie）

葉から根へと向かう探索では，ラベルの照合をしてから，親ノードへと移動することになります．そのため，根方向のキャッシュは葉方向のキャッシュと使い方が異なり，ノード番号を入力として，キャッシュにヒットすれば，子ノードのラベルもしくはリンク情報と親ノードの番号を受け取るようになっています．ヒットしなければ，従来の方法で探索をおこないます．

ノード番号からキャッシュ番号を求める方法は単純です．小細工も必要ありません．

std::size_t get_cache_id(std::size_t node_id) const {
  return node_id & cache_mask_;
}

キャッシュのサイズ

キャッシュのサイズについては，登録文字列数と構築時のパラメータから設定しています．ノード数ではなく登録文字列数を用いている理由は，Trie を構築する前にキャッシュのサイズを決めておかないと，キャッシュの構築に余計な手間がかかるからです．Patricia Trie では登録文字列数とノード数の間に強い相関があることも理由として挙げられます．

具体的には，登録文字列数を n，パラメータを k とするとき，256 以上かつ n / k 以上で 2 のべき乗になっている最小の値をキャッシュのサイズとして採用します．パラメータは以下の通りです．

typedef enum marisa_cache_level_ {
  MARISA_HUGE_CACHE    = 0x00080,
  MARISA_LARGE_CACHE   = 0x00100,
  MARISA_NORMAL_CACHE  = 0x00200,
  MARISA_SMALL_CACHE   = 0x00400,
  MARISA_TINY_CACHE    = 0x00800,
  MARISA_DEFAULT_CACHE = MARISA_NORMAL_CACHE
} marisa_cache_level;

デフォルトでは n / 512 以上となり，登録文字列が十分に多ければ，辞書全体に占めるキャッシュの割合は 1% 前後になります*5．

実験結果

キャッシュの効果を確かめるために，英語版 Wikipedia のタイトル一覧を用いて実験をおこないました．実験の内容は，ノードと登録文字列の順序を切り替えて marisa-benchmark を実行したというだけです*6．

実験結果を眺めていると昇順とランダム順で辞書のサイズが変化していることに気づくかもしれませんが，入力するデータを間違えただけなので，あまり気にしないでください．本来は同じになります．

肝心の成果は，速くなりましたという一言でほとんど片付きます．他には，1 段目の Trie に対するキャッシュは Reverse Lookup に影響していないこととか，辞書構築の高速化はマルチキークイックソートによるものであることくらいでしょうか．辞書のサイズは少し大きくなっていますが，とにかく速くなりました．素直に喜んでおきましょう．

ノードの順序：重み順

• 登録文字列の順序：昇順

-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































marisa-0.2.0-beta2（旧）
     1   58756304   283.83  1020.88  1176.04   825.46   508.56
     2   44932184   245.17   578.17   628.17   511.07   190.37
     3   42688704   240.82   526.67   568.63   469.08   165.98
     4   42000000   239.15   515.20   555.29   459.20   160.76
     5   41747560   238.67   511.07   551.59   456.92   159.40

























































































































-




























































marisa-0.2.0-beta3（新）
     1   58952920   364.09  1314.18  1187.85  1065.55   560.55
     2   45227112   308.81   759.57   719.94   663.94   234.21
     3   43008216   302.94   688.80   653.98   606.99   203.67
     4   42325664   300.96   667.15   636.87   589.28   197.69
     5   42076304   300.30   658.13   630.57   583.05   194.44

























































































































-

• 登録文字列の順序：ランダム順

-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































marisa-0.2.0-beta2（旧）
     1   56678336   211.05   292.59   362.15   252.45   201.45
     2   43332616   192.35   208.89   247.58   186.15   107.71
     3   41146560   189.47   198.29   235.02   177.13    97.55
     4   40474104   187.42   194.80   230.27   174.34    97.71
     5   40226096   193.43   199.53   235.93   177.88    96.13

























































































































-




























































marisa-0.2.0-beta3（新）
     1   56874952   305.14   340.77   373.70   293.56   226.02
     2   43627544   272.66   251.57   276.07   221.93   129.32
     3   41466072   268.17   237.26   260.88   210.00   117.29
     4   40799768   266.64   232.69   256.35   205.87   113.66
     5   40554840   265.93   231.20   254.63   205.82   112.15

























































































































-

ノードの順序：ラベル順

• 登録文字列の順序：昇順

-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   58756304   302.17   420.48  1194.71   383.12   284.71
     2   44932184   262.67   274.24   625.80   255.77   137.74
     3   42688704   258.08   250.06   568.24   232.17   121.83
     4   42000000   249.30   241.59   550.49   226.46   116.96
     5   41747560   249.15   238.46   545.41   222.56   116.04

























































































































-




























































     1   58952920   382.59   941.90  1205.14   806.17   477.19
     2   45227112   324.68   558.66   724.98   504.84   211.05
     3   43008216   319.67   503.61   661.29   450.94   183.99
     4   42325664   317.70   483.32   639.82   439.45   176.23
     5   42076304   316.61   477.47   633.46   433.93   172.92

























































































































-

• 登録文字列の順序：ランダム順

-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   56678336   215.21   152.83   361.33   138.42   121.40
     2   43332616   197.01   109.27   247.12   101.17    72.39
     3   41146560   194.28   101.95   233.44    94.75    66.00
     4   40474104   193.33    99.38   229.87    92.58    64.11
     5   40226096   192.91    98.05   228.16    91.50    64.08

























































































































-




























































     1   56874952   318.05   235.23   373.35   207.86   171.23
     2   43627544   285.05   168.40   271.55   151.96   102.47
     3   41466072   281.03   157.08   258.76   142.55    93.12
     4   40799768   279.65   153.33   254.71   139.46    90.37
     5   40554840   278.77   151.67   253.73   138.08    89.29

























































































































-

おわりに

何気ない思い付きからキャッシュを導入するに至ったわけですが，成果のほどは上記の通り，辞書のサイズに対する影響を抑えつつ，検索を大幅に高速化できました．

少し前に LOUDS 以外の簡潔データ構造を試したときは，検索速度の向上に失敗し，辞書のサイズだけが大きくなるという結果に終わって凹んだものです．一方，今回の手法については，準備段階の実験で成功はほぼ間違いなしという手応えがあったため，気楽に実装できました．成果も概ね期待通りで万々歳です．

それから，簡潔データ構造とキャッシュは相性が良いと思います．今回は Trie という限定されたデータ構造に適用したわけですが，木構造やグラフであれば同様の手法で高速化できそうです．問題によっては，動的なキャッシュを導入することも検討に値するでしょう．劇的に高速化される可能性があります．

以上，風呂敷を広げた状態で終わることにします．

*1:0.1% の部分を 1.0% に増やすと，40% 前後の部分が 60-70% に変わります．キャッシュのサイズを大きくすればヒット率は上がりますが，あまり大きくしても効果は見込めません．

*2:ちょっとした実験で求めた値です．あまり信頼できる値ではありませんが，参考にはなります．

*3:正確には marisa::grimoire::Vector<marisa::grimoire::trie::Cache> です．

*4:Cache のメンバである label() は 1 byte のラベルにのみ有効であり，ラベルの長さが 2 bytes 以上の場合は 2 段目以降の Trie を参照する必要があります．

*5:n / 512 が 256 以上になるのは，n が 131,072 以上のときです．2 のべき乗を選択することによる誤差を考慮しても，65,536 以上を想定していることになります（無茶な設定しやがって…）．小規模な辞書では無駄に大きくなってしまうので，ご注意ください．

*6:marisa-benchmark は辞書を構築した後，登録した文字列を順に検索・復元し，std::clock() により計測した速度（文字列数 [x1000] / 秒）を出力します．