データ圧縮スキーム、数学

Question

私は24個の乱数のリストを持っています。すべてが[0,255]の範囲です。たとえば、最初のリストは[32,15,26,27、... 11]です。 2番目のリストは[44、44、18、19、.. 113]であるかもしれません。どのようにして各リストから番号を選ぶことができますか（私は約42,000の番号の新しいリストに終わるでしょう）、この新しいリストはZIPを使って最も圧縮可能です。

- この質問は、数学としなければならない、データ圧縮

Answer 1

これは私にはNP完全ににおいが、私はどこにもそれを証明するの近くにできていません。外部には、テストするために約7.45e + 57968（！）の構成があります。非圧縮の初期セクションは後で大幅に圧縮可能であるため、特定の構成を早期にオプトアウトすることはできません。

「良い」圧縮を推測するには、百万要素セット全体の各数値の出現回数を数え、各出現順番の数字を選択するのが最も良いでしょう。たとえば、すべてのリストに42がある場合、そのリストを選択すると、同じ値の42,000インスタンスの非常に圧縮可能な配列が得られます。

Answer 2

ZIPファイル形式は圧縮アルゴリズムにDEFLATEを使用します。したがって、アルゴリズムの仕組みを検討し、アルゴリズムが簡単に圧縮できるようにデータを選択する必要があります。ウィキペディアの記事によると、2段階の圧縮があります。最初はLZ77を使用してデータの繰り返しセクションを検索し、短い参照で置き換えます。 2番目のブロックはHuffman codingを使用して残りのデータを取り出し、ブロック全体の冗長性を除去します。これはエントロピーコーディングと呼ばれます。情報があまりランダムではない（エントロピーが低い）場合、コードは共通のものを短い記号で置き換え、エントロピーを増加させます。

一般に、多くの繰り返し実行（すなわち、[111,2,44,93,111,2,44,9,9 ...]）を持つリストは、最初のパスでうまく圧縮されます。他のランダムなもの（すなわち、[111,34,43,50,111,34,111,111,2,34,22,60,111,98,2]、34と111が頻繁に現れる）内の繰り返し数が多いリストは、 2回目のパス。

適切な数字を見つけるには、最も簡単なのは、各リストをソートしてマージし、マージをソートしたままにして、42000の出力番号になるまでです。あなたは起こるように実行されます。これは最適ではありません。各入力リストに255という数字があり、このテクニックを使用して見逃してしまうかもしれませんが、簡単です。

もう1つの方法は、数字を256ビンにヒストグラムすることです。目立つビンは、グループ化すべき数字を示します。その後、シーケンスを検索しなければならないと思います。ここでも、入力を並べ替えることでこれが簡単になるでしょう。

各リストから1つの番号を選択するという制約があることに気付きました。したがって、どちらの場合も、各リストをソートして重複を削除することができます。

さらに、ハフマンコードはツリーを使用して生成することができるので、自動的に正しい答えを与える数字を入れることができるマジックツリー構造があるのだろうかと思います。