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
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 ただ
ウェーブレット木の世界
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。Read less
wat-arrayでラクラク実装☆FM-Indexの作り方 - EchizenBlog-Zwei
というわけで大変便利なライブラリwat-arrayを使ってFM-Indexを簡単に実装してみるよ。本格的なライブラリは既にFM-Index++という良いものがあるので、本記事では仕組みの解説を目的とする。 参考資料: FM-index++を公開しました - tb_yasuの日記 An alphabet-friendly FM-index (P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004) なお、本記事では前回の記事で実装した(ってほどでもないけど)text2bwt()とLF()を使っている。 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei 今回もテキストとしてmississippi#を使う。まずテキストから任意のキーの出現回数を得る関数get_rows(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
大規模フィンガープリント データーの高速類似度検索
