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という感じ。ここでテキストの先頭と末尾はマーカ#を通じて繋がっていることを記
こっそり更新。。 "Dynamic Extended Suffix Arrays" という論文に書かれているアルゴリズムがなかなかおもしろかったので、4年ほど前の Dynamic Wavelet Tree を書き直して実装、簡単なライブラリを作ってみました。とりあえず、BWT・Suffix Array・Inverse Suffix Arrayの動的更新が可能になってます。・・遅いけどね。 File: libdbwt-0.3.0 Size: 47,561 bytes SHA1: 747f8aa9f2eeaf5a6769bfe478a4f2dd0a75af92 かなり適当に作ったので、まだバグやコンパイルできない環境があるかもしれない。 ===================== 参考文献 Mikaël Salson, Thierry Lecroq, Martine Léonard and L
Burrows-Wheeler Transform (blocksortingと同じもの。以下bwt)はbzip2などで利用されている文字列に対する可逆変換です（詳細は勉強会資料とかググってください）。bwtを適用した後のテキストは同じ文字が連続しやすい圧縮しやすいデータとなり簡単な後処理（MTF変換+order-0圧縮）を加えることでLZ法よりも圧縮率は高く、PPM法に匹敵するぐらいに小さくなることは実験的に示されていました。 しかし、どのくらい小さくなるかの理論的解析はあまり進んでおらず、bwt後の処理に関してはもっといい方法があるはずだと研究が進んできました。 最近発表された話(compression boosting, The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compr
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
