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

JavaでWavelet Tree(1)

Java

さて、JavaでWavelet Treeを構築してみようと思います。Wavelet Treeは、任意の文字列に対してrank操作とselect操作を効率良く行えるようにしたデータ構造です。

まず、Wavelet Treeの説明は、簡潔ビットベクトルの知識を前提とします。簡潔ビットベクトルについては、以下の記事を参照してください。

Javaで簡潔ビットベクトル(まとめ)

rank操作とselect操作は、簡潔ビットベクトルの時と同様の定義ですが、任意の文字列に適用できるように拡張します。

まず、簡潔ビットベクトルでのrank操作は、ビットベクトルBとして、b=(0 or 1)がposまでに出現する数を求める以下のような操作です。ただし、posの開始位置は0からとします。

rank(B, pos, b)

このrank操作を任意の文字列に対して適用できるように拡張します。rank操作の対象となる文字列をSとし、出現する数を数えたい文字をcとすると、以下のように定義されます。

rank(S, pos, c)

また、同様に任意の文字列に対してselect操作を拡張します。このとき、以下のように定義されます。

select(S, count, c)

例えば、任意の文字列をSとして、S=「すもももももももものうち」とします。このとき、Sに対して、rank操作とselect操作を実行することを考えます。pos=5とし、c='も'として、rank操作を実行した場合は、

rank(S, 5, 'も') = 4

となります。

また、count=4とし、c='も'として、select操作を実行した場合は、

select(S, 4, 'も') = 5

となります。

定義自体は、簡潔ビットベクトルで定義していたrank操作とselect操作を任意の文字列に対して拡張しただけなので、問題にならないぐらい簡単だと思います。

しかし、実装は、それほど簡単ではないです。

Wavelet Treeは、このような任意の文字列に対するrank操作とselect操作を効率的に実行できるようにするデータ構造です。

さて、次回は、実際に実装を進めていきます。

 

広告を非表示にする