文書解析のための簡潔データ構造

岡野原です。

12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。

ここの業界の進展は速く毎年様々な方法が出てきますが、要点だけを上げると

– Wavelet Treeがアルファベットサイズが大きい場合のRank/Select操作だけではなく、2D矩形探索、最頻要素列挙など様々な問題を効率的に解けることが分かってきて非常に重要なデータ構造であることが分かってきた。2D探索も、もはや数億 x数億とかでも解けてしまうので2D探索を利用するような様々な手法が全部現実的になった。

– Top-K Queryが盛り上がっている。検索などデータ構造に問い合わせをする際に、該当する結果を全部を列挙することの高速化は理論的にも難しいが、スコアが高い順（例えばterm frequencyやPageRankなど）にk個だけ列挙するだけなら非常に高速にできる。この場合も大体Wavelet TreeのGreedy Searchが使われるが、Top-Kを効率的に実現するためのデータ構造（グリット上の優先度付キュー）も研究が盛ん

– CFG (Straight Line Program)をベースにしたGrammer Compressionが実用的になって、いろいろなところで使われ始めている。元々Navarroらのグループが多く利用していたRePairだけではなく、九大の研究グループが中心となってやっている方法などはかなり実用的になってきた。現実的な時間での文法抽出だけでなく、抽出した後のデータに対する簡潔データ構造表現も盛ん。

ちなみに高松ということで、ご飯は、うどん、うどん、鍋＋うどん、徳島ラーメンでした。