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

JavaでWavelet Tree(3)

Java

さて、任意の文字列に対するrank操作とselect操作を簡潔ビットベクトルで実現してみます。簡潔ビットベクトルは自作のsbvjという簡潔ビットベクトルのライブラリを利用します。

http://code.google.com/p/sbvj/

sbvjを利用すると以下のようなコードで実現できます。

public class ArbitrarySequence {
	
	private CharSequence mArbitrarySequenece;
	
	private Map<Character, SuccinctBitVector> mCharToSBV;
	
	public ArbitrarySequence(final String pArbitrarySequence) {
		this.mArbitrarySequenece = pArbitrarySequence;
		this.mCharToSBV = new HashMap<Character, SuccinctBitVector>();
	}
	
	public void build() {
		// 含まれている文字を1文字ずつ取り出す。
		for (int index = 0; index < this.mArbitrarySequenece.length(); index++) {
			Character character = this.mArbitrarySequenece.charAt(index);
			
			// 文字ごとに簡潔ビットベクトルを作成する。
			if ( this.mCharToSBV.containsKey(character) ) {
				SuccinctBitVector sbv = this.mCharToSBV.get(character);
				sbv.setBit(index, 1);
				this.mCharToSBV.put(character, sbv);
			} else {
				SuccinctBitVector sbv = new SuccinctBitVector(this.mArbitrarySequenece.length());
				sbv.setBit(index, 1);
				this.mCharToSBV.put(character, sbv);
			}
		}
		
		// 格納したビットベクトルに補助領域を作成する。
		for (SuccinctBitVector sbv : this.mCharToSBV.values()) {
			sbv.build(BuildType.SIMPLE);
		}
		
	}
	
	public long getRank( final long pPos, final Character pCharacter ) {
		long rank = 0;
		
		if ( this.mCharToSBV.containsKey(pCharacter) ) {
			SuccinctBitVector sbv = this.mCharToSBV.get(pCharacter);
			rank = sbv.getRank(pPos, 1);
		}
		
		return rank;
	}
	
	public long getSelect( final long pCount, final Character pCharacter ) {
		long select = 0;
		
		if ( this.mCharToSBV.containsKey(pCharacter) ) {
			SuccinctBitVector sbv = this.mCharToSBV.get(pCharacter);
			select = sbv.getSelect(pCount, 1);
		}
		
		return select;
	}

}

簡単ですね。
与えられた任意の文字列から文字を一つずつ取り出し、それぞれの文字に対応するビットベクトルに1を設定していくだけです。
その後、文字に対応するビットベクトルに対して、高速なrank操作とselect操作のための補助領域を作成します。
任意の文字に対するrank操作とselect操作は、文字に対応するビットベクトルを利用して実現します。

実際に実行するプログラムは以下のようになります。

public static void main(String[] args) {
	
	String arbitrarySequence = "すもももももももものうち";
	
	ArbitrarySequence as = new ArbitrarySequence(arbitrarySequence);
	as.build();
	
	long rank = as.getRank(3, 'も');
	System.out.println("rank : " + rank);
	
	long select = as.getSelect(2, 'も');
	System.out.println("select : " + select);
	
}

実行結果は、以下のようになります。

rank : 2
select : 3

さて、このような単純なやり方でも任意の文字列に対して、rank操作とselect操作を高速に行うことができます。
しかし、このやり方には、一つ問題があります。
それは、扱う文字の種類が多い場合に、領域が大きくなってしまうという問題です。
任意の文字列をSとし、その長さをnとすると、各文字のビットベクトルの領域は、nビットとなります。このことから、任意の文字列に存在する文字の種類数をσとすると、領域のサイズは、

σ×n(ビット)

となります。ただし、高速なrank操作とselect操作のための補助領域を考慮していない場合です。
この問題を解決するために、Wavelet Treeを利用します。
Wavelet Treeの領域のサイズは、

log2(σ)×n(ビット)

となります。ここで、log2とは、低を2とする対数です。

さて、次回は、Wavelet Treeについてより詳しく説明したいと思います。

広告を非表示にする