information-theory - 圧縮に対する理論上の制限はありますか?

Question

今後 10 年間、世界中のすべてのスーパーコンピューターを自由に使用できると想像してください。あなたの仕事は、10 本の長編映画を可能な限り無損失で圧縮することでした。もう 1 つの基準は、通常のコンピューターがオンザフライで圧縮解除できる必要があり、圧縮解除ソフトウェアをインストールするために HD の多くを費やす必要がないことです。

私の質問は、今日の最良の代替品よりもどれだけ多くの圧縮を達成できるかということです. 1%、5%、50%? より具体的には、辞書のサイズが固定されている場合、圧縮に理論的な制限はありますか（ビデオ圧縮でもそう呼ばれる場合）？

Answer 1

圧縮の限界は、ソースのランダム性によって決まります。情報理論の研究へようこそ！データ圧縮を参照してください。

Answer 2

理論的な限界があります。情報理論と鳩の巣の原理に関するこの記事を読むことをお勧めします。問題を非常に分かりやすくまとめているようです。

Answer 3

圧縮しようとしているすべての映画の固定カタログがある場合は、映画の ID を送信し、「解凍」でそのインデックスを使用してデータを検索することができます。したがって、圧縮は log2(N) ビットの固定サイズになる可能性があります。ここで、N はムービーの数です。

実際の下限はこれよりかなり高いと思います。

あなたは本当にロスレスを意味しますか？今日のビデオ圧縮のほとんどは非可逆圧縮だと思いました。