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

JavaでWavelet Tree(2)

Java

さて、任意の文字列に対するrank操作とselect操作を行えるようにしていきます。これを実現するための簡単な方法の一つとして、簡潔ビットベクトルを利用するやり方があります。

ビットベクトルは、0と1がひたすら並んでいるデータ構造です。このとき、任意の文字列が「a」と「b」の2文字でしか構成されていなかったら、以下のように0に「a」を対応させ、1に「b」を対応させることで、任意の文字列に対するrank操作とselect操作をビットベクトルを使って実現することができます。

f:id:ryokkie:20120624101658p:plain

この例では、「a」に対するrank操作とselect操作しか扱っていないですが、「b」に対するrank操作とselect操作は、ビットベクトルBの1に対するrank操作とselect操作で実現できます。

これらから、任意の文字列を構成する文字の数をkとした場合、kが2以下の場合は、任意の文字列に対するrank操作とselect操作は、簡潔ビットベクトルを使うことで実現できそうです。では、次に、k>2の場合も同様に簡潔ビットベクトルで実現することができるかを考えてみます。まず、k=3の場合を考えてみます。k=2の場合と違って単純に0と1を文字に対応させることができなさそうです。なので、文字ごとにビットベクトルを作成し、そのビットベクトルに対して対応する文字の位置に1を設定していきます。以下のようなイメージです。

f:id:ryokkie:20120624104743p:plain

こうすることで、以下のように、各文字のビットベクトルに対してrank操作やselect操作を行えば、任意の文字列に対するrank操作とselect操作が実現できそうです。

f:id:ryokkie:20120624110823p:plain

さて、次回は、ここで紹介したやり方をJavaで実装してみたいと思います。

広告を非表示にする