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

はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは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++の

[teddy-g]

ウェーブレット木の実装方法

[tyru]

Bjarne Stroustrupが文字列クラスの実装には様々な実装があるって論文書いてた記憶 / Vimではどうだったかな。シンプルに行ごとのリストでバッファを実現してただろうか。

[jusuke]

Wavelet Tree

[witchstyle]

WTは文字列が与えられた時、文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造です。作業領域量は元テキストの約2倍です。

[taki0313]

メモ．実装してみたいな．

[hitsujibane]

データをコンパクトに扱うためのデータ構造

[sshi]

おもしろそげ。地味なテーマなのに楽しそうだな

[subarukun]

『WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です』

[hiromark]

任意の文字列に対する rank/select 操作を定数時間で実現するためのデータ構造。