読者です 読者をやめる 読者になる 読者になる

JavaでWavelet Tree(5)

Java

さて、Wavelet Treeの解説を続けます。

前回までで、文字をグループ化することで、簡潔ビットベクトルで表現できることがわかりました。
このとき、文字のグループに対するrank操作とselect操作は可能ですが、文字に対するrank操作とselect操作はできません。
文字に対するrank操作とselect操作を可能とするために、以下のような木構造を構築します。

f:id:ryokkie:20120722173629p:plain

まず、木の根(root)に対象となる文字列Sを配置します。
次に、文字列Sに含まれるすべての文字を2つのグループに分けます。
今回は、「a」と「b」をXグループとし、「c」と「d」をYグループとしました。
文字列Sに含まれる文字を一つずつチェックして、Xグループに属する文字があれば、左の子に配置します。
Yグループに属する文字があれば、右の子に配置します。
このような操作により、文字列Sから新しい文字列であるS_leftとS_rightを作成します。

さて、文字列Sは、文字の種類が4つ(k=4)であったため、直接的に簡潔ビットベクトルを適用することができませんでした。
しかし、どちらの文字グループに属しているか?ということを表現するだけであれば、2種類しか存在しないので、簡潔ビットベクトルで表現することができます。
では、木の根(root)に配置されている文字列Sに対して、どの文字グループに属しているか?ということが判別できる簡潔ビットベクトルを付与してみます。

f:id:ryokkie:20120722175531p:plain

木の根の簡潔ビットベクトルを利用すると、XグループとYグループに対するrank操作とselect操作を実現できることがわかります。
さて、文字「b」に対するrank操作とselect操作を実現するために、木の根に対する左の子の情報を利用します。
左の子には、Xグループに属する文字しか存在しません。
つまり、文字列S_leftは、文字の種類が2つ(k=2)ということです。
これにより、文字列S_leftは、各文字にビットを対応させ、簡潔ビットベクトルを作成することができます。
また、右の子には、Yグループに属する文字しか存在しないため、文字列S_rightも同様な性質を持っています。
では、左の子と右の子のS_leftとs_rightに、簡潔ビットベクトルを付与してみます。

f:id:ryokkie:20120722182726p:plain

このように、文字のグループごとに分解して、簡潔ビットベクトルを付与していくことで、文字列Sの文字の種類が、2より大きい場合でもrank操作とselect操作を実現することができるようになります。
この木は、2分木であり、任意の文字列に対するrank操作とselect操作を行うことができます。
このように構成される木のことをWavelet Treeと呼びます。
Waveletと呼ばれるのは、おそらく、文字種の数に依存せず、どのような文字列Sであっても、文字に対する簡潔ビットベクトルの組み合わせで表現できることからだと思います。

次回は、このWavelet Treeを利用して、rank操作とselect操作を行う方法について説明します。

広告を非表示にする