c++ - 数値グリッドの高度な圧縮

Question

数字を含む正方形のグリッドがあり、ネットワーク経由で簡単に転送できるように、それを大幅に圧縮する必要があります。たとえば、グリッド内の数値の値に関係なく、40x40 グリッドを 512 バイト未満に圧縮できる必要があります。それが私の基本的な要件です。

グリッドの各セルには 0 ～ 7 の数値が含まれているため、各セルは 3 ビットに収まります。

私が望むものを達成できる優れたアルゴリズムを知っている人はいますか?

Answer 1

情報を別の方法でエンコードできます。0 から 7 までのすべての数字に同じビット数のコードを割り当てる必要はありません。シーケンス内の回数に基づいて割り当てることができます。

最初に、すべての数字の出現回数を数えてシーケンス全体を読み取ります。それに基づいて、各番号にコードを割り当てることができます。たとえばハフマン コードに続くコードを割り当てると、コードはプレフィックス コードになります。つまり、数字を区切る余分な文字はありません。

圧縮率を微調整するために、テスト結果に基づいてアルゴリズムに導入できる特定のバリエーションがあります。

私はこの手法をプロジェクト (大学) で使用しましたが、一般的に良い結果が得られます。少なくとも、1 文字あたりの理論上の 3 ビットに近似する必要があり、確率の分布が役立つ場合は、はるかに優れたものになる可能性があります。

Answer 2

他の人が述べているように、考えられるすべてのグリッドを表すには 600 バイトが必要なため、述べられている問題はあり得ません。600 バイトは、40 行、40 列、1 セルあたり 3 ビット、1 バイトあたり 8 ビットです ( 40 * 40 * 3 / 8)。Kerrek SB がコメントで説明したように、8 つのセルを 3 バイトにパックします。

あなた自身のコメントで、これはネットワーク経由で転送されるゲームの状態であると述べました。データの信頼できる転送を保証するメカニズムがあると仮定すると、更新間で変更できるセルの数に合理的な制限がある場合、または特定の数のセルが変更されたときに更新を送信できる場合は、次のことができます。 512 バイトでの表現を実現します。セルが変更されたかどうかを表すために 1 ビットを使用する場合、200 バイトが必要になります。次に、変更されたセルの新しい値を表す残りの 312 バイトがあります。312*8/3 = 832したがって、変更されたセルまで表すことができます。

余談ですが、この表現は、600 バイト未満で最大 1064 個の変更されたセルを表すことができます。

Answer 3

やりたいことは、データに対して「burrowes-wheeler」変換を実行してから圧縮することです。この場合、ランレングス エンコーディングで十分です。

http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

あなたの場合、これはハフマンよりも優れている可能性があります。

512 バイト以上が必要になる場合があることは事実です。したがって、プロトコルでは、「ひねくれた」グリッドの例外を作成してください。しかし、一般的なケースでは、簡単に 512 未満になるはずです。