Wavelet TreeのTop-Kの改善 - 気ままなブログ
Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小さく、安心して使えるのに対して、Top-Kだけは、少し注意する必要があります。そのことは、文字列本にも書いてあって、最悪計算量も明示してあります。 その最悪計算量ですが、要素間の頻度に大きな偏りがある場合は、無断な節点を調べずに済み、計算量はO(klogσ)に近づくとあります。つまり、ある区間内の数値に偏りがあると、問題ないということです。 1 2 3 4 2 3 4 3 4 4上記のような場合だと、Top-1のクエリを発行すると、O(logσ)です。頻度に偏りがあると、Wavelet Treeの上段での見積もりがうまく機能するので
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
Wavelet Trees: an Introduction
Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets – a structure called the Wavelet Tree. In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression. A Wavelet Tree organises a string into a hierarchy of bit vectors. A rank query has time complexity is
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
ウェーブレット木の世界
2. ⾼高速⽂文字列列解析の世界 宣伝 データ圧縮・全⽂文検索索・テキストマイニング l 岩波書店 l 「確率率率と情報の科学」シリーズ l 5巻発⾏行行済, 全18巻 l 2012/12/27 発⾏行行 l 著者：岡野原⼤大輔 l 編者：⽢甘利利俊⼀一、⿇麻⽣生英樹、伊庭幸⼈人 l 新しい⽂文字列列解析の技術を初めて解説 l Burrows Wheeler変換 l 簡潔データ構造 l ウェーブレット⽊木（今回紹介） 2
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
