我需要幫助來分析這種編程技術來壓縮數組

Question

我希望讀者能夠意識到shannon的信息理論，它指出與概率爲p（a）的事件a相關的信息內容是-log（p（a））。通俗地說，如果您需要表示0-7範圍內的數字，那麼您至少需要-log（1/8）= log（8）（其中base爲2）即3位。

假設有一個範圍從0到255的整數數組，而不是將數組存儲爲8位數字，我會先按照升序對數組進行排序（保留一個課程備份）。而不是編碼每個數組元素作爲一個8位整數我會輸出其排序數組中的位置。現在的問題是讓解碼器或接收器知道這個有序的數組。我將輸出第一個（最小）整數值作爲一個8位數字，然後將增加到這個數字，並很快。首先是所有排序後的數組，即元素的順序，即位置值。

例：原始陣列 - > 231，3，45，0，23，32，78

排序陣列 - > 0,3,23,32,45,78,231

所述經編碼的信息是0（排序數組的第一個元素爲8位數），然後是3（這是增量超過0），然後是20，然後是9，然後是13，然後是33，然後是153.

發送第一個數字和連續的delta後，順序，即因爲有7個整數，這裏我需要一個三位數字的順序，3（0在原始數組中的位置），然後是1（3的位置），然後是4（23的位置），然後是5（32的位置）然後2（位置45），然後6（78的位置），然後0（231的位置）。

即現在的位置的值是3,1，4，5，2,6，0

分析，看是否該方案將壓縮：

第一號 - > 8位（它實際上可能因爲它是最小的，所以需要更少的位）

接下來的6位數 - > 5位（問題是我們可以用5位編碼0,3,20,9,13，但不是我們可能需要編碼的33和153作爲31（最多5位））

7位，每個3位 - > 21位

total-> 8 + 6 * 5 + 21 = 59。這比我們需要編碼7個8位數據所需的56位要多，而且我們已經實現了擴展而不是壓縮，並且由於我們沒有能夠代表一些大數目，所以我們的方案是有損的。

讓我們給這個方案增加一些複雜性。

我會將第一個0編碼爲8位數字，緊接着是最後一個數字231的代碼。然後，我將發送代碼給3，下一個增量爲0，然後編碼爲153，減少231，然後是20，然後是33， 9,13

即我在不同的命令 - 的>代替0,3,20,9,13,33,153已將我會3,153,20,33,9,13

送什麼我得到這是動態範圍的連續減少，你觀察到我們已經發送了0，然後是231，然後是3，然後是153，這時值的範圍減少了，我的意思是下一個增量爲3，即20將不能大於第二個數字，即78，並且20號的數字不能超過75（如果它是那麼的話） d數（3 + 76（說））將大於78明顯違反我們的排序假設。

如果你明白這個想法到現在我有一個進一步的改進方案，以使用二進制搜索的想法，以進一步降低動態範圍，並把這種技術類固醇。 這裏是排序後的數組

0，3，23，32，45，78，231

觀察到排序後的數組是具有7號和中間的一個是32。所以，現在我們將編碼本32與8位，然後我們將發送三角洲預先訂購。即32之後的下一個數字將是3，其將被編碼爲29（即32-3），並且下一個數字將被編碼爲46（78-32），然後0編碼爲3（3-0），然後23編碼爲20 （23-3），然後45編碼爲33（78-45），然後編碼爲153的最後一個231（231-78）。

如果你現在看到的，我們可以決定多少位爲每個數字逐情形使用上的情況。我們將發送排序的數組爲32（範圍0-255所以8位），29（範圍0-32所以6位），46（範圍32-255所以8位），3（範圍0-32所以8位），3（範圍0-32所以6位） 3（所以2位），20（範圍3-32所以5位），33（範圍32-78所以6位），153（範圍78-255所以8位）

所以完全8 + 6 + 8 + 2 + 5 + 6 + 8 = 43這是非有損的並且比我們的初始估計值38（8比特+5 * 6比特）多，所以這增加了三個比特的7個位置值，每個總共43 + 21 = 64更多我們的計劃還在擴大。

我們可以做這是21位的位置編號什麼改善。由於每次我們發送位置信息，如果我們有7個位置發送，則位數減1，那麼位數是log（7）+ log（6）+ log（5）....這就是log（事實（7））位，其中所有的對數是基體2

觀察到我已經使用式日誌（一）+日誌（b）=日誌（AB）

這是等於其與添加時12.299 43等於55.299，比56低一點。但這不實際。我們至少需要3（範圍7）+3（範圍6）+3（範圍5）+2（範圍4）+2（範圍3）+1（範圍2）+0（範圍1）= 14，有43個給出了57個擴展。

這一工作的目的是實現在數據大小至少1位的減少。如果我們將56位壓縮成55而沒有任何關於數據的假設，那麼我們可以將55位的輸出再次壓縮到54位，並且很快。這看起來不可能，這個想法與永久機器類似。現在的任務是查看阻止我們壓縮更多的東西。

我需要分析一個更大的數組的例子，看看排序數組的43位是否可以小於43.還有什麼是將數組分割成許多部分和分別編碼每個部分的優點。另一個目標是找出計算表示排序數組所需位數的公式。即給定的數組元素的數組大小和範圍如何找到號碼等43.

允許再次藉此3,1,4,5,2,6,0作爲排序的數組，並觀察該序列中的一個50個從0到6的7個數字的排列。我們可以將其表示爲13位數（理論表明爲12.299）。

我需要知道的是，可以更壓縮該陣列。

Answer 1

如果我們將56位壓縮成55而沒有任何關於數據的假設，那麼我們可以獲取55位的輸出並將其再次壓縮爲54位，並且很快。這看起來不可能，這個想法與永久機器類似。現在的任務是查看阻止我們壓縮更多的東西。

不可能有一個無損壓縮算法，沒有任何有關數據的假設，保證減少所有可能的數據值的大小。只需通過pigeon hole principle我們可以看到以下內容。當您使用n位時，您可以表示2^n個值。使用n-1位，只能表示2 ^（n-1）個值。因此，如果您編碼原始值的一半，則必須使用與已編碼值之一相同的位對下一個值進行編碼，因此信息鬆散。當然，如果在原始數據中只使用少於2 ^（n-1）個不同的值，那麼可以將該數據的大小減少一位（或更多），但這已經對數據進行了假設。此外，您將無法使用該方法以遞歸方式減少數據的大小而不會造成任何損失。

因此，您可能會發現一些壓縮數組的方法，但僅限於當前壓縮方式至多使用一半可能位模式的情況。這可能是壓縮數組的一些晦澀的方式，但肯定會使用一些k位的一半以上的位模式。這k將是你的門檻，你將無法再減小尺寸。

另外，將數組拆分爲多個部分並分別對每個部分進行編碼的優點是什麼。

如果將數組分成較小的部分，則局部差異會較小，因此您可以使用較少的位來表示數字之間的差異。因此，在像[1,2,3,4,2^30,2^30 + 1,2^30 + 2，2^30 + 3]這樣的數組中，您可以節省一些空間。然而，您將不得不使用更多位來表示新的絕對值。他們再次可以表示爲距離某些任意的絕對值來節省一些空間。但我不確定在某些情況下，您可能會節省1比特的所有努力是否值得。

總結一下。如果你有一個像[2^30，2^30 + 1，2^30 + 2，2^30 + 3]這樣的數組，你顯然可以通過考慮數字之間的差異來節省一些空間，但正如你已經在你的回答，在某些情況下，它會增加數據的大小。因此，你不能有一個壓縮算法來存儲任何（沒有做出假設）數組使用少於n位的數組，其中n是數組中數字對數的上限的總和。

Answer 2

這項工作的目標是實現數據至少減少1比特的大小。

這是不可能的所有輸入。當你真正需要做的是計算有多少個案例時，你可以浪費大量的精力來試圖正確地計算各種表示中的位數，犯錯誤，修復它們等。

有2^k個可能的輸入，其中k是輸入中的位數。假設您相信您有每個輸入的k-1位表示。然後有2 ^（k-1）個可能的表示。然後，如果你將這2 ^（k-1）個表示中的每一個表達給你的解壓縮器，你顯然只會得到2 ^（k-1）個結果。其他2 ^（k-1）個可能的輸入在行動中失蹤。沒有辦法從您的表示中生成缺少的輸入，這意味着實際上您的表示不能涵蓋所有可能的2^k輸入。至少有一半沒有被覆蓋。