完備辞書（簡潔ビットベクトル）の解説 - アスペ日記

2014/02/01 66 users 簡潔ビットベクトル trie LOUDS アスペ日記 完備辞書

以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。この「簡潔ビットベクトル」「... 続きを読む

ウェーブレット行列のrankを2倍高速化する案について著者からコメントをいただいた - EchizenBlog-Zwei

2013/09/28 20 users RANK EchizenBlog-Zwei doc イケ 著者

計算機科学一年くらい前にウェーブレット行列のrank計算を2倍高速化する方法を思いついた。詳細はDSIRNLP発表資料(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)のP.56以降。本当にイケているのか自信がなかったのでウェーブレット行列論文のfirst authorであるF. Claude氏に"アドバイスお願いします"と送ったメールに返信があ... 続きを読む

ウェーブレット行列の省メモリ構築方法 - アスペ日記

2013/05/05 54 users 配列 アスペ日記 領域 知識 中学生以上

ウェーブレット行列の構築方法について。前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。内容としては、相変わらず中学生以上の知識が必要ということはないけれど。 上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。で、基数ソートをするには、元の配列と同じだけの領域が必要にな... 続きを読む

ウェーブレット行列を実装した - hirokazu1020の日記

2013/03/07 30 users オーダー 高速文字列解析 グラフデータ 文字列 文字集合

元のデータに対して十分小さいサイズでありながら各種操作を高速に処理でき、文字列のみならず2次元データやグラフデータまで表現できるというウェーブレット行列を実装してみた。「高速文字列解析の世界」とかブログとか読んでやっとのことで実装した。 ウェーブレット行列の各操作のオーダーの表記では、文字集合のサイズをσ、文字列長をnとしている。 inline int bitCount(ull x){ x = (... 続きを読む

中学生にもわかるウェーブレット行列 - アスペ日記

2013/03/03 440 users アスペ日記 中学生

id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 ”The Wavelet Matrix”」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。日本以外ではあんまり来ていません。理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」と... 続きを読む

FM-Index - 気ままなブログ

2013/02/28 16 users FM-Index CSA Array てき Java

2013-02-24 FM-Index Java BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。FM-Indexは、圧縮全文索引であり、テキストを圧縮して保持しながら、全文検索を実現することができます。Compressed Suffix Array(CSA)よりも高速と言われているデータ構造です。FM-Indexは、ざっくり以下のようなことができます。 元のテキ... 続きを読む

Perlで完備辞書(Fully Indexable Dictionary)のモジュールを書いた - EchizenBlog-Zwei

2013/02/16 34 users モック EchizenBlog-Zwei アルゴリズム 行列

計算機科学ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェーブレット行列を作ってみようかな」と思ったとしても完備辞書は適当なモックで済まさないといけなかったりして面白くない... 続きを読む

ウェーブレット木でできることはウェーブレット行列でもできる - アスペ日記

2012/08/04 16 users ウェーブレット木 RANK select アスペ日記 ブロック

ウェーブレット行列のテスト実装に、rank(), select() の他、wat-array で実装されているものをだいたい追加しました。ウェーブレット木でできることは、ウェーブレット行列でも同じようにできる（元論文の最後にちゃんとそう書いてある）ということが確認できました。なぜ可能なのかというと、ウェーブレット行列でもウェーブレット木のブロックがそのまま保たれているからです。例として、11, 0... 続きを読む