Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」

大規模な文字列データの文字検索/カウントを効率的に行う

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/01/26 12:00

ダウンロード ソースコード (6.8 KB)
ダウンロード バイナリファイル (51.6 KB)

本記事では大規模なデータを扱うためのデータ構造であるwavelet tree(WT)を紹介します。WTは文字列が与えられた時、文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造です。作業領域量は元テキストの約2倍です。WTはsucBVの延長上にあるデータ構造であり、WTを用いることで圧縮索引やsuccinct data structureなどを実装できます。

目次

はじめに

 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree(以下「WT」と表記)です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。

  • rank(p, c)――T[0...p]中のcの出現回数を返す
  • select(i, c)――(i+1)番目のcの位置を返す

 WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。

対象読者

 C++の利用者を対象としています。

必要な環境

 C++、32bit環境を想定しています。Windows XP上のVisual Studio C++ 2003、gcc 3.2.2で動作確認済みです。

wavelet treeの概要

 wavelet tree (WT)は文字列T[0...n-1]上で定義されるデータ構造であり、rankselectの2つの操作をサポートします。rank(p, c)T[0...p]中のcの数を返し、select(i, c) (i+1)番目のcの位置を返します。WTは、sucBVと呼ばれるデータ構造を拡張したデータ構造です。sucBVで扱えるのはTがbit vector(文字が0か1のみ)の場合だけなのに対し、WTはTがどんな文字列や整数列からなっていてもよいところが違います。

 このWTを利用することで、近年提案されている圧縮全文索引(Compressed Suffix Arrays、FM-index、wavelet treeなど)やsuccinct data structure(括弧木など)を実現することができます。WTを利用した、これらのデータ構造についても今後記事にする予定です。

圧縮索引、succinct data structure
 「圧縮全文索引」は、任意のキーワードや部分列を漏れなく検索できる全文索引を、圧縮して保持したものです。従来の全文索引は作業領域量が大きい問題がありましたが、圧縮全文索引はわずかな速度低下で作業領域を大幅に減らすことが可能なデータ構造です。「succinct data structure」は、bit arrayや木構造情報をデータサイズに対し線形サイズ、もしくは情報理論的限界近くまで圧縮した状態に保持した上で、各操作を定数時間で実現するデータ構造です。本記事のwavelet treeは、文字列に対するsuccinctなデータ構造です。詳しくは[3]を参照してください

 いくつか例を挙げて、WTにおけるrankselect操作を説明します。今、T[0...9] = abccbbabcaが与えられたとします。この時、rank(5, 'b')=3です。なぜなら、T[0...5]中には3つのbがあるからです。同様にしてrank(5, 'c')=2となります。一般にΣ_c rank(p, c)=p+1が成り立ちます(添え字が0始まりなのでpではなくp+1)。またselectの場合は、select(2, 'b')=5となります。なぜなら、(2+1)番目のbの位置は5だからです。同様にして(2+1)番目のcの位置は8なので、select(2, 'c')=8となります。その他の結果は次の通りとなります。

T[0...9] = abccbbabca
prank(p, 'a')rank(p, 'b')rank(p, 'c')
0100
1110
2111
3112
4122
5132
6232
7242
8243
9343
pselect(p, 'a')select(p, 'b')select(p, 'c')
0012
1643
2958
3-7-
 「-」は未定義。

 このrankselect操作を、前処理無しに毎回求めるとO(n)時間必要です。前もって全ての答えを求めておく場合も、rankselectの結果を全て明示的に保持するには、文字種類数がAの時、約32 (A+1) N bit必要になります(rankに32AN bit、selectに32N bit必要)。これは文字列本体の作業領域量: N lg(A) bit(lg(x)は2を底としたxの対数)の32(A+1) / lg(A)倍にもなります。今回紹介するWTは、定数時間(正確には入力長に対し定数時間。入力する文字種類数がSの時はlg(S)より小さい0次エントロピー)でrankselect操作を約3 lg(A) N bitの作業領域で実現しています。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5