Wavelet TreeのTop-Kの改善 - 気ままなブログ

2013/09/01 13 users Top-K Greedy 改善 ブログ 操作

2013-09-01 Wavelet TreeのTop-Kの改善 NLP Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小さく、安心して使えるのに対して、Top-Kだけは、少し注意する必... 続きを読む

Wavelet Treeをもう一度 - 気ままなブログ

2013/07/29 23 users 一度 ブログ

2013-07-28 Wavelet Treeをもう一度 NLP 文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見るWave... 続きを読む

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

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

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