テキトーなメモ帳

テキトーなメモ帳

LOUDS-trieを実装してみた

何年前のネタだよって感じですが、『日本語入力を支える技術』のサンプルコードを参考にとても原始的なLOUDS-trieをC++で実装してみました。

原始的なというのは、select,rankが定数時間でできなかったり、日本語入力に対応してなかったりするというあたりです。でも、これらはLOUDSを実装するうえで本質的な部分ではないはずです。[要出典]


『日本語入力を支える技術』のサンプルコードは下記URL

サポートページ:日本語入力を支える技術 ―変わり続けるコンピュータと言葉の世界:|技術評論社

 

実装しているときにちょっと詰まってしまったのは以下の2点です。

1)

Jacobson(1989)の論文

Jacobson, Guy. "Space-efficient static trees and graphs." Foundations of Computer Science, 1989., 30th Annual Symposium on. IEEE, 1989.

https://www.computer.org/csdl/proceedings/focs/1989/1982/00/063533.pdf

 

のrankの定義と、本に書いてある実装でのrank関数が微妙に違っていて結構そこで詰まりました。
具体的には、

Jacobsonの論文・・・rank(m)は"Counts the number of elements in S less than or equal to m" 、つまり位置mまでのビットを含んだビットの数

本の実装・・・rank(m)は位置mを含まないビットの数
となっているのですが、実際に実装してみるとここはそんなに重要な部分ではないみたいでした。

2)

あとは、一連のrankやselectの操作を行った後に最終的に返される"位置"ってどこの位置のことを指してるの?という部分でも詰まってしまいました。

 

"位置"には以下の3種類があります。

  • 簡潔ビットベクトル上の対応するビット1が立っている位置
  • 通常のグラフ上でのノードの位置(例:ルートのノードは位置0、そこから幅優先でノードをたどっていくとして、次の子供は位置1・・・)
  • 通常のグラフ上でのエッジの位置

 

ではまず初めに、
実際に「簡潔ビットベクトル上の対応するビット1が立っている位置」を求める関数の一つである
first_child関数( 
https://github.com/titsuki/louds-practice/blob/master/louds.cpp#L263 )の動作を追ってみましょう。

 

下記の図(Jacobson(1989)と同じ図です)を簡潔ビットベクトルで示すと1011101100101010000となります。

簡潔ビットベクトル上でビット1が立っている箇所はグラフ上のノードのいずれかと対応しています。ルートからBFSでノードをたどっていって、各ノードにおいて、そのノードが持っている子の数だけビット1を立てて、最後に0を付加するということを繰り返していくからです。(以降、これを付加操作と呼ぶ(※これは専門用語じゃないです))

 

 

f:id:say_hello_to_okaoka:20160515233636j:plain

 

たとえば、1011101100101010000の赤字で示したビット1は下図の赤い星マークのところのノードに対応しています。

f:id:say_hello_to_okaoka:20160516001512j:plain


では赤い星マークの子のノード、つまり下図での紫の星マークの位置をfirst_child関数で求めていきましょう。

 

f:id:say_hello_to_okaoka:20160516002207j:plain

1011101100101010000の赤字で示したビット1は簡潔ビットベクトル上では位置4にあるので、子のノードを求めるにはfirst_child(4)と呼び出します。
そうするとfirst_child(4)の中では

rank1(4) = 4 // 赤い星にたどり着くまでに付加操作を4回やったということ
select0(4) = 9 // 4回目の付加操作のときの0の簡潔ビットベクトル上での位置
child_pos = 9 + 1 = 10 // 5回目の付加操作(つまり、赤い星のときの付加操作)のときの最初の1の簡潔ビットベクトル上での位置、つまり赤い星の子==紫の星 の簡潔ビットベクトル上での位置

という操作が行われてfirst_child(4) == 10というのを得ることができます。

つまり、簡潔ビットベクトル上では下記の赤字のビットが紫の星と対応しています。

1011101100101010000

 

 

次に、「通常のグラフ上でのノードの位置」を求めてみましょう。

これはrank1(簡潔ビットベクトル上での位置)を行うだけです。

例えば、先ほどの例だと、紫の星の位置はrank1(first_child(4)) = rank1(10) = 7となります。

 

 

さいごに、「通常のグラフ上でのエッジの位置」を求めてみましょう。

これは「通常のグラフ上でのノードの位置 - 2」を行えばよいです。

各子ノードは親をひとつしか持たないという性質を利用するので、エッジの位置はノードの位置に依存しています。

 

以上です。