Engineering the LOUDS Succinct Tree Representation

　Engineering the LOUDS Succinct Tree Representation(O. Delpratt et al., 2006)を読んだ。モチベーションとしてはTxの実装ってどういう風になってるのかが知りたかったというのがある。
　LOUDSというのは順序木を効率的に実装するためのアルゴリズムで、この論文ではさらにそれを改良したLOUDS++というのを実装・提案している。
　基本的なアイデアは、木の上の方から、ノードに存在する子ノードの数だけ1を並べる。デリミタは0。（まぁ、1と0が逆でもいいんだけど。）そうすると、それぞれの1とノードの対応が取れるようになる。このビット列をLBSと呼ぶ。LBSに対してis_leaf, parent, next_siblingなどの関数が実装できれば順序木が実現できる訳だけど、これらの関数はそれぞれ数個のrank, select操作で実現できる。ここまでがLOUDSのアイデア（いくつか省いてるけど）。
　LBSをさらに2つのビット列に分割することを考えてみる。LBS中で1つ以上連続する0の数をl=l_1, l_2,...l_nと表現することにすると、l=1,2,2,4...2みたいな感じになる。このlの各要素から1を引いたものをLとすると、L=0,1,1,3,...1みたいな感じになる。で、Lの各要素分だけ0を並べて、その間に1を置くと、新しいビット列ができる。これをR0と呼ぶことにする。同様に、1に関して同じ事を行ってR1も作る。
　LBSの構成要素は0と1しかないので、1つ以上の0と1つ以上の1は交互に連続する（うう、自明過ぎて日本語にしにくい…）。これにより、R0とR1から元のLBSが復元できることは明らか。そんでもって、i番目の1や0に対するアクセスはR1[i]とかR0[i]で行える事になる。こっから効率のよいis_leafやparentなどの実装をどうすんのかといった話は省略。（前提となるLOUDSのアイデアをちょっと省いてるので。）
　i番目の0に対するアクセスがR0[i]で行えることが飲み込めるまでにはやや時間が必要だった。l→Lの段階で要素数を1引いてるので難しい気がしたんだけど、単純にR0[i]でいい。間に1を挟んでいるので、1までをひとまとまりだと考えると、結局並ぶ要素数自体はlの時と変わりがない。
　実験結果としては、LOUDS++で1つのノードを表現するために必要なデータ数が3〜4bitぐらい、LOUDSの場合は5〜5.5bitぐらい。速度に関してもLOUDS++の方が速い。大体1.5倍程度の感じ。
　さて、ここからはTxの話。眺めた限り、TxはLOUDSを使っているようだ。BitVectorを一本しか使ってないので、LOUDS++ではない。たぶん。
　Trieに使うためには遷移する際のキー情報が必要になるけれど、LOUDSにはそのようなデータを保存する場所はない。Txではどうやっているのか、コードを読んでみると、edgeという名前の配列に、どのキーで遷移するのかが保存してあった。インデックスはノード番号になっているようだ。複数の子要素を持つ場合にはnext-siblingで線形探索。通常、TrieはO(k)で要素にアクセスできる（k=要素数）というイメージがあるんだけど、これだと定数項が128とかになりそう。定数なのは確かなんだけど、ちょっと気になる。あと、このやり方だと無順序木でも問題なさそうだけど、順序木よりも空間効率のよい無順序木を実現するデータ構造とか、あるんだろうか。ありそうな気もするけど、よくわからない。