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(
話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei
先日PFIの岡野原氏によってwat-arrayというライブラリが公開された。 wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research Blog このライブラリは内部でウェーブレット木(wavelet tree)という簡潔データ構造(succinct data structure)を使っている。このため文字列に対するrank()やselect()などの操作が効率的にできるようになっている。 ・・・といっても馴染みのない人にとっては何が嬉しいのかピンと来ないかもしれない。そこでBurrows-Wheeler変換(BWT, Burrows-Wheeler Transform)を例にとってwat-arrayの使いみちを説明してみる。 Burrows-Wheeler変換というのはテキストを同じ文字が並びやすいように変換したもので、通常ランレ
Burrows-Wheeler変換(BWT)の圧縮率が高い理由 - EchizenBlog-Zwei
Burrows-Wheeler変換(BWT, Burrows-Wheeler Transform)されたテキストは同じ文字が並びやすい。従ってランレングス法等と併用することで大きな圧縮効果を得ることができる。 では、なぜBurrows-Wheeler変換によって同じ文字が並びやすいのか。これについて説明するよ。 BWTは与えられたテキストを1文字ずつずらして並べたものを考える。例えばmississippiなら mississippi# ississippi#m ssissippi#mi sissippi#mis issippi#miss ssippi#missi sippi#missis ippi#mississ ppi#mississi pi#mississip i#mississipp #mississippiという感じ。ここでテキストの先頭と末尾はマーカ#を通じて繋がっていることを記
データを加工して圧縮率を高めよう
データを加工して圧縮率を高めよう：コーディングに役立つ！ アルゴリズムの基本（9）（1/5 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 圧縮率を上げるために、ひと工夫 前回「データ量を操る圧縮／展開を究めよう」では、圧縮アルゴリズムの基本としてランレングス法とハフマン符号を紹介しました。今回は、データを圧縮しやすいように加工することで、より圧縮率を上げるアルゴリズムを紹介していきたいと思います。 さて、圧縮率を上げるにはどうすればよいでしょうか。 ランレングス法では、連続する文字列が多ければ多いほど圧縮率が高まります。ハフマン符号では、できるだけ特定の文字が多く出現するようになっていれば圧縮率が高まります。このようなデータの加工の手法を見ていきます。
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
ブロックソート - Wikipedia
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 原理[編集] 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、B
Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮 - naoyaのはてなダイアリー
先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。 BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。 今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。 http://github.com/naoya/perl-algorithm-mtf/tree/master に置いています。 use Algorithm::MTF; my $encoder = Algorithm::MTF
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ