任意のシーケンスのサイズを少なくとも 1 ビット縮小できるように、2 ビットの数値の圧縮方式を作成したいと考えています。これが不可能であることをどのように証明できますか？
質問する
830 次
1 に答える
3
4 つの可能な 2 ビット数と 3 つの可能な短いビット シーケンス (ビットの空のシーケンスとシーケンス 0 と 1) があります。ピジョンホールの原則により、これは、2 ビット シーケンスから短いシーケンスへのマッピングには、同じ短いシーケンスに圧縮された少なくとも 2 つのシーケンスが必要であることを意味します。その結果、この短いシーケンスを解凍したい場合、それが元の 2 ビット シーケンスのどれから来たのかわからないため、解凍できません。
これを一般化して、n ビット シーケンスを可逆圧縮して n 未満の長さのビット シーケンスにすることはできないことを示します。 この以前の回答では、これがなぜなのかを詳しく説明しています。
お役に立てれば！
于 2013-02-16T02:52:03.297 に答える