DSIRNLP#1で発表しました「TRIEにトライ！〜今日からはじめるTRIE入門〜」

昨日開催された「第1回データ構造と情報検索と言語処理勉強会(DSIRNLP)」に発表者として参加しました。主催者の@overlastさん、発表者の皆さん、ボランティアの皆さん、会場を提供してくださったミクシィさん、そして発表を聞いてくださった皆さん。どうもありがとうございました。
また発表スライドについては@overlastさん、@uchumikさん、@machyさん、@nokunoさんにチェックして頂きました。特に@uchumikさん、@machyさんより頂いた意見のおかげでスライドの質が向上しました。ありがとうございました。

発表スライド：
(scribdのembedがうまくいかなかったので暫定的にリンクおいておきます)
TRIEにトライ！〜今日からはじめるTRIE入門〜

本記事では質疑応答でフォローしきれなかった部分を中心に、私の発表の補足的なものを書いて行きます。
会のまとめ的なものは@overlastさんの記事を見ていただけると良いかと思います。

［O］第1回データ構造と情報検索と言語処理勉強会　#DSIRNLP で発表してきました

以下、補足事項を項目ごとにわけて書いて行きます。今回の勉強会では様々なバックグラウンドの方がいらっしゃったようですので項目ごとに説明のレベルを変えて書いています。☆が多いほど専門的な話題になります。

TRIEは何に使えるか(☆)
TRIEの単純な利用法は「辞書引き」と呼ばれるものです。どういうことかというと

キーワード  値
Aさん       80点
Bさん       70点
Cさん       90点

というようなキーワードと値のペアが並んだもの(辞書)があったときに、「キーワード」を与えたらそれに対応する「値」を返すようなものを「辞書引き」といいます。
どういう用途で使われるかというと例えば「ある文章に不適切な言葉が入っていないかを調べる」ことができます。この場合「キーワード」として「不適切な言葉」を「値」として「不適切な度合い(スコア)」などを事前に用意します。で、適切かどうかをチェックしたい文章に含まれる言葉を「辞書引き」してやってスコアが一定値を超えたら不適切と判断する。というような使い方になります。もっと一般的には機械学習で素性に対する素性値をもたせるのに利用したりします。
「辞書引き」の機能は最近ではKVS(Key-Value Store)で実現したりすることも多いと思います。他のKVSと比べてTRIEを使う大きなメリットは「前方一致検索」が可能だということです。前方一致検索というのは例えば「言語〇〇」というようなある言葉で始まる言葉を全部見つけてくるものです。「言語○○」の場合は「言語処理」「言語仕様」などの言葉を検索できます。前方一致検索の使いどころとしては「予測変換」が挙げられます。検索エンジンに途中まで言葉を入れたら検索する言葉の候補がでてくるのを見たことがあると思いますが、ああいう機能を思い浮かべれば良いです。
KVSでは入力したキーワードに対して「1対1で一致する値」を取ってくるだけなのに対して、前方一致検索のように「字面上近い範囲のキーワード」をまとめて取ってこれるのがTRIEの利点です。この利点があるのでTRIEは自然言語処理(NLP)の分野ではよく利用されるデータ構造だと思います。

LOUDSは何がすごいか(☆☆)
LOUDSはノード数Nに対して時間計算量を定数に抑えたままで、空間計算量をO(NlogN)からO(N)にしているという点で優れています。
これを実現するには2つのアイデアを用いています。一つが「各ノードは子ノードリストではなく、子ノード数を持っているだけで子ノードの位置を特定できる。」というものです。子ノードリストをもたせる場合は子ノード毎にlogNビットの情報量を必要とします。子ノード数が必要というだけなら子ノードの区別が不要なので子ノードごとに1ビットあれば良いというわけです。
で。発表で解説したように「子ノード数だけもっていればよい」ためには「子ノードの累計値を定数時間で計算する」ことが必要になります。これができなければ「時間計算量を定数時間に抑えたままで」の部分が達成できません。
ここでもう一つのアイデア「データ列の部分和を定数時間で求める」が必要になってきます。これの実現には簡潔データ構造(Succinct Data Structure)というものを用います。「データ列の部分和を定数時間で求める」が実現できれば必ずしも簡潔データ構造に拘る必要はないので、この部分は改良の余地はあるかもしれないです。

簡潔データ構造とは(☆☆☆)
簡潔データ構造はLOUDSの考案者であるJacobson氏の提案するデータ構造です。情報理論的な下限に近いデータサイズを保ちつつ諸々の機能を効率的(大抵は定数時間)で実現するデータ構造のことを簡潔データ構造と言います(たぶん。間違ってたらすみません)。
上述のとおり簡潔データ構造の定義は範囲が広いです。データ構造としては具体的にはビット列や文字列、木構造などが該当します(LOUDSは簡潔ビット列を使って実現した簡潔木です)。諸々の機能というのもいろいろあるのですが一般にはrankおよびselectという機能を指します。
rank/selectもデータ構造によって定義が色々ありますがLOUDSに必要な部分だけ解説します。まず一般的なデータ構造として集合(set)を考えます。これは

{1, 3, 4, 7}

のように値が幾つか集まったものです。ただし重複した値は無いものとします。このときrank/selectは

rank(x)  : 値がx以下のデータの数
select(i): i番目に小さなデータの値

と定義されます。上述の{1,3,4,7}の例だと

rank(3) = 2
select(2) = 3

という感じになります。ちなみrankとselectは逆関数の関係になります。で。問題の集合なんですが具体的にどのようにデータをもたせるのでしょうか。これは単純には

{1, 3, 4, 7}
=> {1, 0, 1, 1, 0, 0, 1, 0}

というビット列に置き換えて考えられます。集合に含まれる数値の位置のビットが立っています。このビット列に対してrankとselectは具体的には

rank(x)  : x番目のビット以前(xの位置を含む)の立っているビットの数
select(i): i番目に立っているビットの位置

となります。上述の{1,3,4,7}の例だと

rank(3) = 2
select(2) = 3

となり、以前の定義と最終的に得られるものは同じだということに注意してください。
まとめると、もともと集合に対してrank、selectを考えるよという話だったのですが、具体的な集合の持たせ方としてビット列を採用しビット列に対してrank/selectが定義できました。
ここで気になるのは実装についてですが、これは単純に「適当なサイズごとに事前にrank/selectを計算して持っておく」だけです。もちろん計算して持っておく分、余計なデータサイズがかかるので他の部分でデータサイズを節約していくことになります。詳細は記事末尾の参考資料を見てください。とにかくポイントは「(部分的に計算して持っておく方法が使える形を保ちつつ)データサイズを小さくする」という部分だということです。
さて、ここで発想の転換です。経緯はどうあれビット列に対してrank、selectが定義できたので集合云々は忘れて、様々な(立っているビットが集合に含まれる要素だよ、というような意味を持たない)ビット列に対してrank/selectを計算できることになります。ということはunary符号についてもrank/selectが計算できます。unary符号というのは

1 => 10
2 => 110
3 => 1110

というように値分だけ1を並べて最後に0を置くビット列です(ものによっては0と1が逆だったりします)。でこのunary符号で子ノードを管理するよ、というのがLOUDSです。unaryのビット列に対してrank/selectを駆使することで子ノードの合計を定数時間で計算できます。unaryを用いたLOUDSの詳細は(http://d.hatena.ne.jp/echizen_tm/20101005/1286291649)をご参照ください。
で。今回の発表ではunaryのかわりにVerticalCodeを使いました。VerticalCodeの詳細は(http://d.hatena.ne.jp/echizen_tm/20100804/1280942359)や(http://d.hatena.ne.jp/echizen_tm/20100531/1275323074)を参考にしていただくとして、ここではVerticalCodeを使った場合のLOUDSについて解説します。
VerticalCodeのrank/selectはビット列に対するものではなく本来の定義である集合に対するrank/selectです。つまり

rank(x)  : 値がx以下のデータの数
select(i): i番目に小さなデータの値

です。VerticalCodeで扱う集合の要素を「i番目までの子ノード数の合計」とします。つまり子ノード数が

ノード番号: 1  2  3  4
子ノード数: 2  1  1  2

と並んでいたら

{2, 3, 4, 6}

という集合だと考えます。このとき子ノード数の合計はselectで簡単に計算できます。つまり

select(3) = 4

なので3番目のノードまでの累計子ノード数は4(= 2 + 1 + 1)だということがわかります。合計値でノード数をもっていても3番目のノードの子ノード数は

select(3) - select(2) = 4 - 3 = 1

と定数時間で計算できるので安心です。というわけでVerticalCodeで子ノード数を管理するとselect操作のみでデータ列の部分和が計算できるので実装が簡単になります。余談ですがVerticalCodeはselectに特化していてrankはあまり効率的に実行できません。ただしLOUDSではrankを使わないため問題が起こりません。
まとめると本来のLOUDSはunaryで子ノード数を管理していて「ビット列のrank/select」を用いて子ノードにアクセスしていました。一方今回の発表で用いたVerticalCodeを用いた方法(暫定的にLOVESとします)では「集合のselect」を用いて子ノードにアクセスしました。「ビット列のrank/select」も本来は「集合のselect」の集合をビット列で表した場合のrank/selectでしたがLOUDSでは「集合を表さないビット列=unary」に対してrank/selectを使っているので単純に本来のLOUDSのrank/selectとLOVESのselectを比較できるものではない、という点には充分にご注意ください。

以上で補足は終わりです。発表では初心者を意識し難解な箇所は大幅にカットしましたが詳細が気になる方もいるかと思い、ある程度の補足をさせて頂きました。

参考資料:
トライ木 - Wikipedia
最近のtrieの話（xbwなど） : Preferred Research
Succinct data structure - Wikipedia, the free encyclopedia
"Space-efficient　Static Trees and Graphs" G. Jacobson, 1989
"Practical Entropy-Compressed Rank/Select Dictionary" D. Okanohara & K. Sadakane, 2007