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


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

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

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

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

    Species animalA;
    Species animalB;
    bool whoWon;

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

 

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

でも、ちょっと待って

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

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

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

 

    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

Comments (3)

  1. takumi says:

    どうも気になって記事を読まさせて頂きました。

    算術符号化圧縮を丁寧に説明されてあって非常に参考になります。非常にcoolでした。

    ひとつ、

     encoded += Value;

     encoded += valueRange;

    と誤字になっております。

  2. vFetchでスキンアニメーション、その2:vFetchの使い方 Fetchを使ったスキンアニメーションの実装例を紹介する前にvfetchの基本的な使い方を紹介します。   例えば、以下のシェーダーコードのように頂点位置、色を使用する頂点シェーダーがあるとします。

Skip to main content