Competitive Programming Advent Calendar 2012の12/01担当分の記事です。 Read less
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。 Read less
はじめましてこんにちわ。 4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな
9/30(日)に開催予定のDSIRNLP#03でウェーブレット木について発表しません。 なんで発表しないかというとウェーブレット行列というウェーブレット木の上位互換であるまじぱないデータ構造について話すからです。 ウェーブレット木がわからないとウェーブレット行列もわからないんじゃないの？と思われるかもしれませんが、その逆でウェーブレット木では必要以上に難しく考えていたことを「それ、もっと単純に出来るよ」っていうふうに見方を変えたのがウェーブレット行列です。 ウェーブレット木を知らない人はむしろウェーブレット行列から入ったほうが近道です。 なのでDSIRNLP#03ではウェーブレット木については発表しません。発表予定だった資料は以下のURLで公開していますので興味ある方は参考にどうぞ。 よくわかるウェーブレット木
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは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++の
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。 例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置 といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。 例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
