幅優先/深さ優先探索による Predictive Search
本日の内容は Predictive Search の実装についてです．
概要
marisa-trie には Predictive Search 用の関数が 3 種類あります．
- predict()
- キーの復元をおこなうときは predict_depth_first() を呼び出し，そうでないときは predict_breadth_fist() を呼び出します．
- predict_breadth_first()
- 入力された文字列にしたがってトライを探索し，それから先は幅優先探索をおこなって，見つけたキーを順番に出力します．
- predict_depth_first()
- 入力された文字列にしたがってトライを探索し，それから先は深さ優先探索をおこなって，見つけたキーを順番に出力します．
predict() の役割は，特徴の異なる 2 種類の使い分けです．与えられた引数によって，どちらを呼び出すべきかを判断します．判断基準は，keys が NULL であれば predict_breadth_first() を呼び出し，そうでなければ predict_depth_first() を呼び出すというものです．使い分けの理由は，キーを復元しないときは predict_breadth_first() の方が高速で，キーを復元するときは predict_depth_first() の方が高速だからです．
そんなわけで，キーの復元をするかどうか，およびに幅優先探索と深さ優先探索の違いがポイントになります．残るポイントは，LOUDS というデータ構造の特徴です．単純に分かりやすく実装するというのも魅力的な案ではありますが，効率を求めるのであれば，これらのポイントは外せません．
ボトルネック
LOUDS を利用する marisa-trie では，rank/select の計算，特に select の計算にかかる時間がボトルネックになります．そのため，select の省略が時間効率の向上につながります．
キーを復元する / しない
キーを復元するかどうかで何が違うのかというと，入力された文字列にしたがってトライを探索した後の探索において，2 段目以降のトライや TAIL を参照する必要があるかどうかが変化します．
- キーを復元するとき
- 2 段目以降のトライや TAIL を参照する必要があります．
- キーを復元しないとき
- 2 段目以降のトライや TAIL を参照する必要がありません．
2 段目以降のトライや TAIL を参照しなくてよいとなれば，リンクを辿るために rank の計算をしたり，2 段目以降のトライを探索するために rank/select の計算をしたりする必要がなくなります．そのため，キーを復元しないときは，探索の手間を大幅に削減できます．パトリシアトライの利用が時間効率の向上に役立つ場面です．
幅優先探索
木構造の幅優先探索となれば，待ち行列を使うのが基本です．しかし，LOUDS は幅優先（Level-Order）な構成になっているので，待ち行列を使わない方法があります．それは，1 階層ずつ探索範囲を求める方法です．
まず，探索の開始位置となるノードを k とすると，最初の探索範囲は [k, k+1) になります．そして，次の階層における範囲は，下限・上限ともに louds.rank1(louds.select0(x)+1) で算出することができます．後は，下限と上限が同じになるまで繰り返すのみです．
唐突に現れた計算式の意味が何かというと，実のところ，子ノードの番号を求める計算式とまったく同じです．子ノードがなくても問題無用で適用してしまうことに少し不安を感じるかもしれませんが，上手く働きます．
結果として，待ち行列のような補助領域を必要とせず，1 階層毎に select を 2 回という低コストで探索を進めることができます．そのため，キーを復元しないときは，深さ優先探索より高速になります．ただし，キーを復元するときは，待ち行列に途中経過を残しながらの探索か，もしくはキー ID からの復元が必要となり，深さ優先探索より手間がかかってしまいます．
深さ優先探索
木構造の深さ優先探索となれば，再帰呼び出しやスタックを使うのが基本です．しかし，下へ上へと移動を繰り返すと select の計算回数がかさむので，スタックに少し工夫を施して使います．どのような工夫を施すのかというと，pop しても内容を残しておき，後で再利用するようにします．
- 階層 k に初めて到達するとき
- 子ノードの番号を計算して push します．select を含むので時間がかかります．
- 階層 k から上に移動するとき
- スタックのカウンタをデクリメント（pop）するだけで，内容は残しておきます．
- 階層 k-1 から再び下に移動するとき
- スタックのカウンタをインクリメント（push）するだけで，以前の内容をそのまま使います．select の計算は不要になります．
結果として，1 階層毎に select を 1 回という低コストで探索を進めることができます．ただし，スタックの操作をしながらノードを 1 つずつ確認する必要があるので，キーを復元しないときは，幅優先探索より手間がかかってしまいます．
深さ優先探索におけるポイントは，幅優先探索より効率的にキーを復元できることです．その理由は，待ち行列に途中経過を残しておいたり，キー ID から復元したりする必要がないからです．
- 待ち行列を用いる場合との比較
- 1 つの文字列（std::string）に対して，ラベルを足したり（append()）引いたり（resize()）するだけなので，文字列を大量に複製する必要がありません．
- キー ID から復元する場合との比較
- ラベルの復元はそれぞれ 1 度きりになるので，無駄がなくなります．
というわけで，キーを復元するときは深さ優先探索の方が効率的になります．
