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

2006/01/26 60 users CodeZine メインメモリ スワッピング 省メモリ 速度

はじめに　大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuc... 続きを読む