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

JavaでWavelet Tree(4)

Java

仕事が忙しくてなかなか更新できなかったのですが、任意の文字列に対するrank操作とselect操作を実現するWavelet Treeについて実装を進めていきます。

さて、前回までは、Wavelet Treeを利用しない強引なやり方で、任意の文字列に対するrank操作とselect操作を実現しました。
その時のポイントを整理します。
まず、任意の文字列をSとして、Sの中に含まれている文字種の数をkとします。
Sを「abababab」とした場合、kは、2となります。
この場合は、簡潔ビットベクトルを利用することで、以下のように簡単に任意の文字列に対するrank操作とselect操作を実現することができます。

f:id:ryokkie:20120708213815p:plain

つまり、ポイントとしては、

  • 「k = 2」の場合は、何の工夫もなく、任意の文字列に対するrank操作とselect操作が実現できるということ
  • 「k > 2」の場合は、簡潔ビットベクトルをそのまま適用することができないということ

があります。

前回までに紹介したやり方は、「k > 2」の場合に、各文字ごとに簡潔ビットベクトルを用意して、各文字ごとにrank操作とselect操作を実現するというものでした。
このやり方は、簡単ですが、サイズに関して効率的ではなかったです。

さて、「k = 2」の場合は、簡潔ビットベクトルで表現できるのだから、「k > 2」の場合は、うまく分解して、「k = 2」の簡潔ビットベクトルの組み合わせで表現できないか?ということを考えます。
Sを「abcdabcdabcd」とした場合、「k = 4」となります。
この時、「a」と「b」の文字をXグループと表現し、「c」と「d」の文字をYグループと表現します。
そうすると、Sには、XとYしか存在しないため、以下のように簡潔ビットベクトルで表現することができます。

f:id:ryokkie:20120708215101p:plain

しかし、これでは、XグループやYグループに対するrank操作やselect操作を行うことができても「a」や「c」に対するrank操作やselect操作を行うことができません。
ここで、各グループに着目すると、文字の種類が4つから2つに変化していることがわかります。
つまり、簡潔ビットベクトルで直接的に表現できる文字種の数である2に分解できたということがわかります。
文字種の数が2となれば、簡潔ビットベクトルで表現することができます。

さて、次回も解説を続けます。

広告を非表示にする