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

JavaでWavelet Tree(7)

Java

さて、別な形のWavelet Treeに対して、rank操作とselect操作を行ってみますが、実際の実装のWavelet Treeに変換してみようと思います。

まず、今まで、見てきたWavelet Treeは、以下です。

f:id:ryokkie:20120804081722p:plain

ここで、各ノードに必要なのは、簡潔ビットベクトルだけなので、Sの情報は不要です。
なので、Sを持たないWavelet Treeは、以下になります。

f:id:ryokkie:20120816130542p:plain

こうすると、各ノードには、簡潔ビットベクトルだけを持つことが強調されます。
ただし、このままでは、各ノードで、どの文字が0や1に割り当てられているのかわかりません。
このため、以下のような補助的な情報を付与します。

f:id:ryokkie:20120816131516p:plain

まず、Sに含まれる文字集合をσとして、別に保持します。
また、このσに保持する文字集合は、辞書順で保持することとします。
各ノードでは、σの文字集合の添え字を閾値として持ちます(添え字は0から始まるとする)。
例えば、rootノードは、閾値として、1を持ちます。
閾値が1のσの値は、「b」なので、探したい文字と「b」を比較して0か1を決定します。
つまり、探したい文字が辞書順で、「b」以下の場合は、0と判断して、左の子を探索し、「b」より大きい場合は、1と判断して、右の子を探索する。
これにより、Wavelet Treeの各ノードは、簡潔ビットベクトルと閾値を持つだけでよいことがわかります。

さて、このことを考慮して、別の形のWavelet Treeを作ってみようと思います。
以下のような文字列を考えます。

S=oosakanamba

このSに対して、σは、以下のようになります。

σ={a, b, k, m, n, o, s }

まず、rootノードの閾値を計算します。
σには、要素が7個あるため、添え字は0から6まであります。
このことから、以下のように計算されます。

rootノードの閾値=(0+6)/2=3

この閾値を反映したWavelet Treeは、以下のようになります。

f:id:ryokkie:20120816220236p:plain

rootノードの閾値以下の場合は、0を割り当て、rootノードの閾値より大きい場合は、1を割り当てています。

次にrootノードの左の子と右の子を作成します。
まず、左の子の閾値は、σの範囲が、0から3となるため、以下のように計算されます(小数点は切り捨てます)。

rootノードの左の子の閾値=(0+3)/2=1

次に、右の子の閾値は、σの範囲が、4から6となるため、以下のように計算されます。

rootノードの右の子の閾値=(4+6)/2=5

この閾値を反映したWavelet Treeは、以下のようになります。

f:id:ryokkie:20120816231713p:plain

このように続けていって作成したWavelet Treeは以下のようになります。

f:id:ryokkie:20120816234003p:plain

簡単ですね。

ただ、実際は、計算方法さえわかっていれば、各ノードで閾値を持つ必要はないです。
ここでは、わかりやすくするために閾値を保持しただけです。
また、Sも保持する必要はないです。

さて、次回は、このWavelet Treeに対して、rank操作を実行する過程を説明し、実際にプログラムをJavaで作成してみます。

広告を非表示にする