壓縮2位數並保存1位使用壓縮方案

我想創建一個2位數的壓縮方案，以便它將任何序列的大小減少至少一位。我怎樣才能證明這是不可能的？壓縮2位數並保存1位使用壓縮方案

2013-02-16 benji_r

當然可以將尺寸減小一位。什麼是不可能的是無損地逆轉過程。 – 2013-02-16 04:37:13

有4個可能的2位數和3個可能的較短位序列（空序列位和序列0和1）。通過pigeonhole principle，這意味着從兩位序列到較短序列的任何映射必須具有至少兩個序列被壓縮到相同的較短序列。因此，當你想解壓這個較短的序列時，你將無法做到這一點，因爲你不知道它來自哪個原始的兩位序列。

這可以概括爲顯示n比特序列不能被無損地壓縮成長度小於n的比特序列。 This earlier answer詳細說明了這是爲什麼。

希望這會有所幫助！

2013-02-16 02:52:03 templatetypedef

你的意思是「...必須至少有兩個序列被壓縮成同一個較短的序列」，我想。（很顯然，任何人都已經知道這個論點，但對新讀者來說可能並不明顯。） – Nemo 2013-02-16 03:18:40

@ Nemo-謝謝！固定。 – templatetypedef 2013-02-16 07:02:05

嘿傢伙非常感謝你的答案 – 2013-02-16 19:57:31

回答