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

FM-Index

Java

BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。

BWTソースコードは以下にあります。ちょっとバグを見つけたので、気が向いたら直します。

http://rn.hatenablog.com/entry/2013/02/16/115423

ウェーブレット行列のソースコードは以下にあります。

http://rn.hatenablog.com/entry/2013/02/23/222314

FM-Indexは、圧縮全文索引であり、テキストを圧縮して保持しながら、全文検索を実現することができます。Compressed Suffix Array(CSA)よりも高速と言われているデータ構造です。FM-Indexは、ざっくり以下のようなことができます。

  • 元のテキストを完全に復元することができる(self index)
  • 任意のキーワードが出現する位置と数をキーワードの文字数に依存する時間で検索することができる(検索対象のテキストサイズに依存しない)

FM-Indexを作成する手順は簡単です。

  1. テキストに対してBWTした文字列を取得する。
  2. BWTして得られた文字列に対して、ある文字より小さい文字の出現数を保持した配列とウェーブレット行列を構築する。

これだけの手順でFM-Indexを構築できます。

検索時は、キーワードの最後から1文字ずつ照合していきます。このとき、ウェーブレット行列を使って、rank操作を実行することで、効率的に検索を実行することができます。検索時の性能は、ウェーブレット行列の性能に依存することから、ウェーブレット行列内の簡潔ビットベクトルに依存すると言えます。なので、簡潔ビットベクトルのrank操作の性能が定数時間であれば、検索したいキーワードの文字数ぐらいにしか依存しません。

参考にしたのは、以下の本です。

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

以下がFM-Indexです。

public class FMIndex {
	
	private String mText;
	private int mTextCodePointCount;
	
	private WaveletMatrix mWM;
	
	private int mMaxCodePoint;
	
	private int [] mCodePointFreq;
	
	public FMIndex( final String pText ) {
		this.mText = pText;
		this.mTextCodePointCount = this.mText.codePointCount(0, this.mText.length());
	}
	
	public void build() {
		
		// BWT
		BWT bwt = new BWT( this.mText );
		bwt.build();
		
		String bwtText = bwt.getBWT();
		
		this.mMaxCodePoint = bwt.getMaxCodePoint();
		this.mCodePointFreq = bwt.getCodePointFreq();
		
		// Wavelet Matrix
		this.mWM = new WaveletMatrix( bwtText );
		this.mWM.build();
		
		// テキストは不要である。
		this.mText = null;
		
	}
	
	/**
	 * 
	 * <p>
	 * キーワードのヒット数を返すメソッドである。
	 * </p>
	 * 
	 * @param pKeyword キーワード
	 * @return ヒット数
	 */
	public int getHitCount( final String pKeyword ) {
		
		int codePointCount = pKeyword.codePointCount(0, pKeyword.length());
		
		// Backward Search
		int start = 0;
		int end = this.mTextCodePointCount;
		for ( int pos = codePointCount - 1; pos >= 0; pos-- ) {
			int codePoint = pKeyword.codePointAt(pos);
			
			if ( this.mMaxCodePoint < codePoint ) {
				// ヒットしない。
				break;
			}
			
			start = this.mWM.getRank(start, codePoint) + this.mCodePointFreq[codePoint];
			end = this.mWM.getRank(end, codePoint) + this.mCodePointFreq[codePoint];
			
			if ( start >= end ) {
				// ヒットしない。
				break;
			}
			
		}
		
		if ( start < end ) {
			return end - start;
		}
		
		return 0;
		
	}
}

以下がテストコードです。

public class FMIndexTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//String text = "abracadabra\0";
		String text = "abracadabra_abracadabra_abracadabra\0";
		String keyword = "abra";
		
		FMIndex fmi = new FMIndex( text );
		fmi.build();
		
		int hitCount = fmi.getHitCount(keyword);
		
		System.out.println( "Hit Count : " + hitCount );

	}

}

もう少しブラッシュアップしてライブラリとして公開しようと思う。

広告を非表示にする