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
