博士

ロボ子、今日はWavelet Treeについて話すのじゃ！

ロボ子

Wavelet Treeですか。文字列のランククエリを高速に実行するためのデータ構造とのことですが、詳しく教えてください。

博士

そうじゃ！Grossi、Gupta、Vitterという賢い人たちが2003年に発表したのじゃ。文字列をビットベクトルの階層に構造化するらしいぞ。

ロボ子

ビットベクトルの階層ですか。具体的にはどのように構造化されているのでしょうか？

博士

まず、文字列のアルファベットを取得して、それを半分に分けてエンコードするのじゃ。例えば、{a, b, c, d} というアルファベットなら、{a, b} を0、{c, d} を1としてエンコードするのじゃ。

ロボ子

なるほど。{a, b}が0、{c, d}が1になるのですね。そして、それを再帰的に繰り返すと。

博士

その通り！シンボルが1つか2つになるまで繰り返すのじゃ。アルファベットサイズをAとしたとき、ランククエリの時間計算量はO(log₂A)になるらしいぞ。

ロボ子

ランククエリの時間計算量がO(log₂A)ですか。かなり高速ですね。ランククエリとは、具体的にどのようなクエリなのでしょうか？

博士

ランククエリは、指定された位置までの1のビット数をカウントするものじゃ。木が構築された後、ビットベクトルに対してlog Aのランククエリで実行できるのじゃ。

ロボ子

なるほど、理解しました。各内部ノードでのエンコードがあいまいとのことですが、それはどういう意味でしょうか？

博士

それは、どのサブツリーに進むかを決めるために使うからじゃ。あいまいでも、適切なサブツリーに誘導できるのじゃ。

ロボ子

Suffix Arrayと組み合わせると、長さPの任意のパターンを2Pのランククエリで検索できるそうですね。これはどういうことでしょうか？

博士

Suffix Arrayは文字列のすべての接尾辞をソートした配列じゃ。これとWavelet Treeを組み合わせると、文字列中のパターンを効率的に見つけられるのじゃ。Wavelet Treeを使う場合、パターン検索の時間計算量はO(P log₂A)になるぞ。

ロボ子

なるほど。Suffix ArrayとWavelet Treeを組み合わせることで、より高度な検索ができるようになるのですね。

博士

そうじゃ！それに、ビットベクトルをRRRシーケンスに格納すると、元のシーケンスよりも少ないスペースで済む場合もあるらしいぞ。賢いじゃろ？

ロボ子

確かに、省スペースになるのは大きなメリットですね。実装は、Francisco Claudeさんが作成したCompressed Data Structure Library (libcds)で利用可能とのことですね。

博士

その通り！libcdsを使えば、簡単にWavelet Treeを実装できるぞ。ロボ子も試してみるのじゃ！

ロボ子

はい、ぜひ試してみたいと思います。今日はWavelet Treeについて詳しく教えていただき、ありがとうございました。

博士

どういたしまして。ところでロボ子、Wavelet Treeって、なんだかお菓子の名前みたいじゃない？ウェーブレット・ツリー味のクッキーとか、作ってみようかの？

ロボ子

博士、それはちょっと…味が想像できません…。