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

JavaでWavelet Tree(6)

Java

懐かしいわ~。

D

作業がかなり中断しましたが、Wavelet Treeに対するrank操作とselect操作について説明していきます。
rank操作とselect操作は、以下のような操作です。

  • rank(i, c) : i-1の位置までに現れるcの数を取得する。
  • select(i, c) : i-1番目に現れるcの位置を取得する。

前回の記事で紹介したWavelet Treeを使って、これらの操作について説明したいと思います。
まずは、rank操作から説明します。

前回、紹介したWavelet Treeを以下に示します。

f:id:ryokkie:20120804081722p:plain

ただし、実際は、各ノードで文字列を保持せず、ビットベクトルを保持しています。
そのあたりの話は、今後、実際に実装していくので、そこで書きます。

まず、例として、rank(5, 'a')を行う場合を考えます。
つまり、4の位置までに「a」という文字が現れる数を取得します。
rootノードにおいて、「a」は、0に対応しているため、0の数を数えます。
つまり、rank(5, 0)というrank操作をrootノードのビットベクトルに対して実行します。
以下のような感じです。

f:id:ryokkie:20120728092320p:plain

4の位置までに出現する0の数を数えると、3なので、rootノードの時点で、「a」と「b」のグループに属する文字が3回出現したことがわかります。
次に、rankに指定された文字が「a」なので、rootノードで0に対応するため、左の子を調べます。
左の子には、「a」と「b」の情報しか表現されていないため、rootノードで分かった3回出現したというrankの情報の内訳を知ることができます。
つまり、左の子が持つビットベクトルに対して、rank操作を行えば、「a」の数が分かります。
左の子において、「a」という文字は、0に対応しているので、rank(3, 0)というrank操作を左の子のビットベクトルに対して実行します。
以下のような感じです。

f:id:ryokkie:20120728092758p:plain

これにより、左の子で、0の数が2ということがわかります。
また、左の子は、子供のノードを持っておらず、葉に到達するので、ここで処理を終えます。
結局、rank(5, 'a')の結果は、2ということが分かります。

簡単ですね。

次回もrank操作についての説明を続けます。
いろいろな例にを紹介した方が理解しやすいと思うので、別の形のWavelet Treeでrank操作を適用しながら説明したいと思います。

広告を非表示にする