Burrows Wheeler TransformとLF mapping - Preferred Networks Research & Development
最近オープンウォーターダイバーのライセンスを取りました。徳永です。 今日はBurrows Wheeler Transform（BW変換もしくはBWT）の逆変換において用いられるLF mappingを説明します。 BWTはデータ圧縮の前処理などに使われるテクニックです。Burrows Wheeler Transformはとても簡単でわかりやすい（高速な実装は複雑ですが……）のですが、逆変換で用いられるLF mappingは、実装は簡単なものの、なぜそれでよいのかは少しわかりにくいところがあります。また、私はこれまで、LF mappingがなぜあれでうまくいくのか、わかりやすい説明を日本語でも英語でも見た記憶がありません。そこで今回はLF mappingを中心に説明します。なお余談ですが、BTWのMichael Burrowsは現在はGoogle勤務で、ChubbyやBigTableなどのソフ
bwtの圧縮率解析 - DO++
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ページを開く
