ネットワーク　その８　算術符号化圧縮

算術符号化は解りづらく、めったに使われないツールのひとつですが、時々その威力を発揮します。例えるならネットワークデータ圧縮における変なサイズの六角レンチです。

算術符号化はクールです。なぜなら、あまり知られていないし、一見すると動かないように思えるものだからです。パーティーで女の子に好印象を持たせるのに活躍します(訳注:そうか？)

以下のデータがあったとします。

     enum Species    // 種類
    {
        Camel,          // ラクダ
        Cat,            // ねこ
        Caterpillar,    // いもむし
        Cheetah,        // チーター
        Chimpanzee,     // チンパンジー
        Cobra,          // コブラ
        Cormorant,      // 鵜(う)
        Cougar,         // クーガー
        Coyote,         // コヨーテ
        Crab,           // カニ
        Crocodile,      // ワニ
    }

    Species animalA;
    Species animalB;
    bool whoWon;

(そう、私たちは世界中の男の子が一度は思う「クーガーとワニはどっちが強いか？」という疑問に答えるためのゲームを作るんだ(訳注:ねこが最強))

ビットフィールド圧縮を使った場合、animalAとanimalBの変数には１１種類の動物がいるので、その情報を格納するのにそれぞれ４ビットが必要になり、誰が勝ったのかという情報で１ビット必要になるので合計で８ビットを超えてしまいます。

でも、ちょっと待って

animalAに格納する値の組み合わせは１１種類、animalBも１１種類、そしてwhoWonには２種類の値です。全ての組み合わせを考えると１１× １１× ２の合計２４２通りになります。これならbyteに収まりそうです。

ここでは４ビットを動物の種類に割り当てていますが実際は１１種類必要なところに１６種類を表すだけのスペースを用意してしまうというのはビットフィールド圧縮の問題です。この中途半端な組み合わせをコンパクトにする方法があれば良いと思いませんか？

前の記事のビットフィールド圧縮の部分を、乗算、除算、そして剰余算に変更することで解決することができます。

     void ArithmeticEncode( ref int encoded, int valueRange, int Value )
    {
        encoded *= valueRange;
        encoded += value;
    }

    int encoded = 0;
    ArithmeticEncode( ref encoded, 11, (int)animalA );
    ArithmeticEncode( ref encoded, 11, (int)animalB );
    ArithmeticEncode( ref encoded, 2, whoWon? 1: 0 );
    packetWriter.Write((byte)encoded);

そして、読み込み側は、ビットフィールドの時と同じようにパラメーターを逆順に読み込みます。

     void ArithmeticDecode( ref int encoded, int valueRange )
    {
        int value = encoded % valueRange;
        encoded /= valueRange;
        return value;
    }

    int encoded = packetReader.ReadByte();
    whoWon = ArithmeticDecode( ref encoded, 2 ) != 0;
    animalB = (Species)ArithmeticDecode( ref encoded, 11 );
    animalA = (Species)ArithmeticDecode( ref encoded, 11 );

どう？クールでしょ？

原文:

http://blogs.msdn.com/shawnhar/archive/2007/12/30/network-compression-arithmetic-encoding.aspx