同じ文字が続く限り0が連続します。小さな数字が登場し易い偏った状態の文字列に変換されます。エントロピー符号化による圧縮率が向上します。ランレングス圧縮やハフマン符号と相性が良いです。BWTを実装してみたBWTをCで実装してみました。アルゴリズム確認のため非効率な面があります。qsortでソートするための構造体を作ります。qsortはstdlibの関数です。qsortで使う比較関数です。,((Pair*)y)->str);}目印となる特殊文字には$を使います。$でなくても良いですがソート時に一番小さい値にする必要があります。先頭の文字から一文字ずつずらした文字列(巡回シフト)をPair構造体に格納していきます。suffixの文字を配列に入れて完成です。}実際に使ってみます。LinuxKernelの冒頭部分です。連続した文字が出現し易い傾向がわかります。Implementation続いて逆変換です。LF-mappingという性質があります。元の文字列の1文字前の位置を返すことでBWTから復元するために用いられます。Pair構造体に入れていきます。そこから辿って元の文字列を復元していきます。以下の文字列を入力します。0の出現率が高くなっています。比較的理解し易いのは以下だと思います。と連続した回数を数字で表現します。元の文字列よりサイズが大きくなる欠点があります。実装して今回のBWT文字列を圧縮したところ元データの文字列に対して28%圧縮率が高くなりました。bit-codeを割当てることで効率よく表現します。代表的な可変長符号化はハフマン符号化です。増分分解法や動的辞書法とも呼ばれます。繰り返し同じ文字列が出現する場合に有効な圧縮方法です。復元が早いのも特徴です。ハフマン符号化が使われています。174Byteと完敗でした...こうなったらgzipのソースコード見て勉強します。ハフマン符号化も書いてみたいです。参考にさせて頂いた本は『高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング』です。Elmastudio。