Blog
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。
wat-arrayというC++ライブラリを公開しました。
google code:wat-array
wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます．
wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。
例えば、
– 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度
– 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数
– 任意の文字のi番目の出現位置
といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。
例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[123456789…987654321]の範囲内にある77777777番目に大きい値を大体1マイクロ秒以下で取得できます。
wat-arrayがサポートしている基本操作を組み合わせることによって、更に様々な統計量を求めることができます。例えば、範囲A[sp, ep)中の中央値(median)はA[sp, ep)中の(ep-sp)/2番目に大きい値を求めることによって得られます。
これらの操作を組み合わせることで2Dサーチ、つまり二次元中にある点について、\(a \le x \lt b, c \le y \lt d \)中にある要素の数を数えるのが定数時間、列挙も出現数に比例する時間で実現することも知られています。
また、接尾辞配列が苦手としている文書列挙や、AND検索において出現位置がk以内にあるペアの列挙(Pair-End Mapping問題、ゲノム解析で重要）なども高速に行うことができます。
wat-arrayの構築時間は入力サイズに対して線形です。大体1秒あたり数十MBのデータを処理して構築します。
wat-arrayのサイズは入力データと同じです。正確には入力配列長がn, 各値の範囲が\(0 \lt a[i] \lt s\)の時 \(n \log_2 s\) ビット必要とします。
また、wat-arrayはself-index、つまり元の配列を必要とせず、さらに元の配列をwat-arrayだけから復元することもできます。
wat-arrayは近年のwavelet木にまつわる様々な研究成果をまとめた結果です。私がcodezineというサイトでwavelet木を紹介したのが4年前でしたが（codezine）、それからwavelet木が元々想定されていた全文索引用途以外に様々なタスクに利用できるということが分かってきました。また、wavelet木自身についても、元々のwavelet木はアルファベット数が大きくなるにつれてオーバーヘッドが急激に大きくなっていたのですが、今回実装した方法ではアルファベット数が配列長とほぼ同じような場合でさえ、オーバーヘッドが殆んど発生しません。
今回はwavelet木について、その性質について簡単に説明したいと思います。
一つの軸の値でのみ構成されている要素集合に対して最大値、最小値、k番目に大きい値を求めるのは簡単です。値の順でソートしておけば終わりです。
これと同じようにwavelet木は2つの軸から構成される要素の集合を”両方の軸”でソートした状態で保持しているとしてデータ構造として考えることができます。例えば、T[i]=cの要素は二次元中の(x=i, y=c)にあるような要素としてみることができます。wavelet木においては各要素は両方の軸でソートされているように扱えるので、例えばある連続した範囲内にある最大値というのはx軸方向では連続した領域にあり、そのなかでy軸方向で一番上側にある要素を求めればできます。その他の操作も基本的にはこの特性を利用して実現しています。
wavelet木がどのようにその特性を実現しているのか、また各種機能はどのように実現されているのかについてはまたの機会にすることにします。（興味のある方はプロジェクトに書いてある参考論文、もしくはwat_arrayのソースコードを読んでみてください）
wat-arrayはまだドキュメントも不十分ですが、これから暇を見つけて充実させていこうと思います。またwat-arrayを利用した様々なツール、2D探索やPE mappingなども作っていきたいと思います。その時はまた本ブログで触れていきたいと思います。
なお，wat-arrayはPFIの20%プロジェクトで作りました。
興味のある方はぜひさわってみてください。
Tag
