高速文字列解析の"別"世界 - 気ままなブログ
1月に「高速文字列解析の世界」を購入してから半年が経ちました。以下、文字列本と呼びます。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (4件) を見る 全文検索として、「CSA」や「FM-Index」が紹介されていますが、「全文検索システム」を作るには、これらだけでは不十分です。なぜなら、以下のような特徴があるからです。 文書IDの識別が遅い。 各文書IDに出現する頻度を求めるのが遅い。 ちなみに、転置インデックス(or N-gramインデックス)を使った場合、これらの処理は高速ですね。 インデックスを圧縮しているのだからしょうがないとも考えられますが、作りたいですよねぇ、「全文検索システム」。こ
Wavelet Matrix - 気ままなブログ
一部で大ブームのWavelet Matrix(ウェーブレット行列)をJavaで実装してみました。 以下を参考にしました。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 14人 クリック: 316回この商品を含むブログ (3件) を見る また、以下のスライドを参考にしました。 http://d.hatena.ne.jp/echizen_tm/20120930/1348999144 ウェーブレット行列は、ウェーブレット木と同等のことができるデータ構造です。 ウェーブレット木については、書こうと思って書いてるうちに忙しくなって投げ出した経緯があります。 http://rn.hatenablog.com/entry/2012/06/22/000315 ただ
FM-Index - 気ままなブログ
BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。 BWTのソースコードは以下にあります。ちょっとバグを見つけたので、気が向いたら直します。 http://rn.hatenablog.com/entry/2013/02/16/115423 ウェーブレット行列のソースコードは以下にあります。 http://rn.hatenablog.com/entry/2013/02/23/222314 FM-Indexは、圧縮全文索引であり、テキストを圧縮して保持しながら、全文検索を実現することができます。Compressed Suffix Array(CSA)よりも高速と言われているデータ構造です。FM-Indexは、ざっくり以下のようなことができます。 元のテキストを完全に復元することができる(self index) 任意のキーワードが出現する位置と数をキーワードの文字
Javaで簡潔ビットベクトル(まとめ) - 気ままなブログ
長かった簡潔ビットベクトルシリーズも、一応、終わりにしたので、今までの記事のリンクをまとめておきます。 ビットベクトル Javaでビットベクトル(1) Javaでビットベクトル(2) Javaでビットベクトル(3) Javaでビットベクトル(4) Javaでビットベクトル(5) Javaでビットベクトル(6) 簡潔ビットベクトル Javaで簡潔ビットベクトル(1) Javaで簡潔ビットベクトル(2) Javaで簡潔ビットベクトル(3) Javaで簡潔ビットベクトル(4) Javaで簡潔ビットベクトル(5) Javaで簡潔ビットベクトル(6) Javaで簡潔ビットベクトル(7) Javaで簡潔ビットベクトル(8) Javaで簡潔ビットベクトル(9) Javaで簡潔ビットベクトル(10) Javaで簡潔ビットベクトル(11) Javaで簡潔ビットベクトル(12) Javaで簡潔ビットベクトル(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
