IME本でも紹介されているLOUDSのパワーアップ版、DFUDSを調べた

計算機科学

「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると効率が良い。
さて、そんなLOUDSにはパワーアップ版ともいうべきDFUDS(Depth First Unary Degree Sequence)というデータ構造がある。DFUDSはLOUDSが定数時間で扱える操作(parent(親ノードの位置を得る), i-th child(i番目の子ノードの位置を得る), degree(子ノード数を得る))に加えてsubtree size(現在のノードを根とする部分木のノード数を得る)という操作が定数時間で実現できる。よってDFUDSを使うと、トライでpredictive searchをした時のヒット数を部分木を探索することなく求めることが出来る。
そんなDFUDSが提案されている論文を読んでみたのでメモしておく。


DFUDSは仕組みとしてはLOUDSとBP(Balanced Parentheses)を足しあわせたようなものになっている。従って、DFUDSを知る前にBPを知る必要がある。LOUDSについてはIME本を参照されたい。
BPとは木を括弧表現にしたもので、findclose, findopen, encloseという操作を定数時間で行うことができる。findclose(i), findopen(i)はそれぞれi番目の括弧に対応する閉じ括弧、開き括弧の位置を返す。enclose(i)はi番目の開き括弧と対応する閉じ括弧を内側に持つ最小の括弧の開き括弧の位置を返す。例えば

( ( ) ( ) )

という括弧列については

findclose(0) = 5
findclose(1) = 2
findclose(3) = 4

findopen(2) = 1
findopen(4) = 3
findopen(5) = 0

enclose(1) = 0
enclose(2) = 0
enclose(3) = 0
enclose(4) = 0

となる。BPの詳細は

などを参考にされたい。気が向いたらあとで記事を書くかも。


さて、DFUDSは木を深さ優先探索して各ノードをLOUDSのようにunary符号で表す。LOUDSは先頭におまじない10を追加したが、DFUDSでは1だけを追加する。例えば

a => {b, c, d}
b => {e, f}
d => {g}

という木に対しては

a: 1110
b: 110
c: 0
d: 10
e: 0
f: 0
g: 0

なので

LOUDS: 10 1110 110 0 10 0 0 0
DFUDS: 1 1110 110 0 0 0 10 0

となる。ここでDFUDSはLOUDS同様ビット列なので簡潔ビットベクトルで扱えばrank(),select(), rank0(), select0()が定数時間で計算可能になる。
また1を開き括弧、0を閉じ括弧とみなすことでBPとしても扱うことができる。すなわちfindopen, findclose, encloseを定数時間で計算できる。
するとparent, i-th child, degree, subtree sizeは以下のようにして計算できる。

degree(p) = select0(rank0(p) + 1) - p
i-th child(p) = findclose(select0(rank0(p) + 1) - i) +1
parent(p) = select0(rank0(findclose(p - 1))) + 1
subtree size(p) = findclose(enclose(p) - p) / 2 + 1

DFUDSでは各ノードを訪問すると子ノードの数だけ1(つまり開き括弧)が出力され、子ノードが訪問される度に0(つまり閉じ括弧)が出力され括弧が閉じられる。
例えば

aノードを訪問する(子ノードb,c,dぶんの1を出力)
DFUDS: 1 111

bノードを訪問する(bのぶんの0を出力、子ノードe,fぶんの1を出力)
DFUDS: 1 11[1][0] 11

eノードを訪問する(eのぶんの0を出力)
DFUDS: 1 1110 1[1][0]

fノードを訪問する(fのぶんの0を出力)
DFUDS: 1 1110 [1]10 [0]

cノードを訪問する(cのぶんの0を出力)
DFUDS: 1 1[1]10 110 0 [0]

dノードを訪問する(dのぶんの0を出力、子ノードgぶんの1を出力)
DFUDS: 1 [1]110 110 0 0 [0] 1

gノードを訪問する(gのぶんの0を出力)
DFUDS: 1 1110 110 0 0 0 [1][0]

(最後に0を出力)
DFUDS: [1] 1110 110 0 0 0 10 [0]

というふうになっている。この値の出力の様子を注意深く見るとわかるのだが、各ノードを表すunary符号について左から順番に「1と対応する0」の右隣の要素が子ノード位置となっている。例えばaの最初の子ノードの位置を知りたいとする。するとaに対応するのは

DFUDS: 1 [1110] 110 0 0 0 10 0

の角括弧をつけた部分となる。最初の子ノードの位置が知りたいので

DFUDS: 1 11[1]0 110 0 0 0 10 0

に着目する。これに対応する0の位置は

DFUDS: 1 111[0] 110 0 0 0 10 0

なので、その右隣の

DFUDS: 1 1110 [110] 0 0 0 10 0

がaの最初の子ノード、bの位置となる。同様にaの2番目の子ノードを知りたい場合は

DFUDS: 1 1[1]10 110 0 0 0 10 0

に着目する。これに対応する0の位置は

DFUDS: 1 1110 110 0 [0] 0 10 0

なので、その右隣の

DFUDS: 1 1110 110 0 0 [0] 10 0

がaの最初の子ノード、cの位置となる。同様に他のノードの子ノード位置も計算できる。これを式で表現したのが

i-th child(p) = findclose(select0(rank0(p) + 1) - i) +1

となる。具体的には

degree(p) = select0(rank0(p) + 1) - p  # 子ノード数を計算
degree(p) + p = select0(rank0(p) + 1)  # ノードの末尾に移動
degree(p) + p - i  # i番目の子ノードを表すビットに移動
findclose(degree(p) + p - i)  # 対応する閉じ括弧(0)の位置に移動
findclose(degree(p) + p - i) + 1  # その右隣に移動

というふうになっている。parentは基本的にはこれと逆の操作をすればよい。
なおDFUDSの目玉要素であるsubtree sizeについてはBPのenclose操作によって自分の親ノードの開き括弧の位置がわかるので、そこから対応する閉じ括弧までのビット(括弧)数の半分(括弧は2ビットでひとつの対なので)を計算すれば良いことがわかる。つまり

subtree size(p) = findclose(enclose(p) - p) / 2 + 1

となる。
以上、大雑把にだがDFUDSのメモ。DFUDS自体はそれほど実装が難しくない印象で、むしろコンポーネントであるBPが曲者である気がする。DFUDSの大きな特徴は前述のとおりsubtree sizeが効率的に計算できる点にあるが、他にも深さ優先でノードを探索して組み立てるという性質上、トライ木用途だとデータをオンラインで追加できるという利点もあるんじゃないかなーと思っている(LOUDSは幅優先なので一度データを全部読み込む必要がある)。
なんにせよ気になるデータ構造なので実装してみたいが課題はBPを効率的に実装する部分だなー。うむむ。