數據壓縮：算術編碼不清

Question

任何人都可以請詳細解釋用於數據壓縮的算術編碼嗎？我已經通過互聯網衝浪，發現了標記納爾森的帖子，但實施的技術在嘗試了幾個小時後對我來說確實不清楚。

馬克·尼爾森的算術編碼解釋可以在

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

算術壓縮的主要思想是它能夠使用所需數據長度的確切數量來編碼概率。

數據的這個量是已知的，通過香農證明，並且可以通過使用下面的公式簡單地計算：-log2（P）

例如，如果p = 50％，則需要1個比特。 如果p = 25％，則需要2位。

對於2的冪的概率（在這種特殊情況下，霍夫曼編碼就足夠了），這很簡單。但是如果概率是63％呢？那麼你需要-log2（0.63）= 0.67位。聽起來很棘手......

如果您的概率很高，此屬性尤其重要。如果您能夠以95％的準確度預測某些東西，那麼您只需要0.074位來表示一個很好的猜測。這意味着你將壓縮很多。

現在，該怎麼做？

好吧，它比聽起來簡單。您將根據概率劃分您的範圍。例如，如果您有100個範圍，2個可能的事件，並且第一個可能事件的概率爲95％，那麼前95個值將表示「事件1」，最後5個剩餘值將表示「事件2」 。

好的，但在計算機上，我們習慣使用2的冪。例如，對於16位，您有65536個可能值的範圍。只要做同樣的事情：取第一個95％的範圍（即62259）說「事件1」，其餘的說「事件2」。你顯然有一個「四捨五入」（精確）的問題，但只要你有足夠的價值來分配，它並不重要。此外，你不受限於2個事件，你可能會有無數的事件。重要的是價值取決於每個事件的概率。 OK，但現在我有62259個可能的值來說「事件1」，而3277來說「事件2」。我應該選擇哪一個？那麼，他們中的任何一個都可以。它是1,30,55或62256，它仍然意味着「事件1」。

事實上，決定選擇哪個值不取決於當前的猜測，而是取決於當前的猜測。

假設我有「事件1」。所以現在我必須選擇0到62256之間的任何值。在下一個猜測中，我有相同的分佈（95％事件1，5％事件2）。我將簡單地用這些概率分配分佈圖。除此之外，它分佈在62256個值上。我們繼續這樣做，每次猜測都會縮小數值範圍。

所以實際上，我們正在定義「範圍」，這些範圍會隨着每個猜測而縮小。然而，在某些情況下，存在準確性問題，因爲只剩下很少的值。

這個想法，是簡單地再次「膨脹」範圍。例如，每次範圍低於32768（2^15）時，您輸出最高位，並將其餘的乘以2（實際將值左移一位）。通過不斷這樣做，你會逐個輸出比特，因爲他們正在通過一系列的猜測來解決。

現在與壓縮的關係變得很明顯：當範圍快速縮小（例如：5％）時，輸出很多位以使範圍回到極限以上。另一方面，當概率非常高時，範圍變窄非常緩慢。在輸出第一位數據之前，你甚至可以進行很多猜測。這就是將事件壓縮到「一小部分」的可能性。

我有意使用術語「概率」，「猜測」，「事件」來保持這篇文章的通用性。但是對於數據壓縮，您只需以您想要爲數據建模的方式來替換它們即可。例如，下一個事件可以是下一個字節;在這種情況下，你有256個。

Answer 2

一切都歸功於首先被定位爲向我介紹了壓縮算法的概念！

我可以看到，該方法具有以下步驟：

1. 創建映射：計算出現的分數爲其中給出了每個字母的範圍內的大小的每個字母。然後命令他們和從0到1
2. 給定消息計算的範圍內（非常簡單IMHO）分配實際範圍
3. 查找最佳代碼

第三部分是有點麻煩。使用以下算法。

設b是最優表示。初始化它爲空字符串（''）。設x是最小值，y是最大值。

1. 雙x和y：X = 2 * X，Y = 2 * Y
2. 如果兩者都是大於1次追加1至b。轉到步驟1.
3. 如果兩者都小於1，則向b追加0。轉到步驟1
4. 如果x < 1，但Y> 1，然後附加1至b和停止

B實質上包含要發送數的小數部分。例如。如果b = 011，則該分數對應於二進制中的0.011。

你不明白什麼部分的實現？

Answer 3

也許這個腳本可能有助於建立一個更好的算術編碼器心智模型：gen_map.py。最初它是爲了便於調試算術編碼器庫並簡化爲其生成單元測試而創建的。但是它會創建出色的ASCII可視化，這對於理解算術編碼也很有用。

一個小例子。想象一下，我們有3個符號的字母表：0,1和2，概率分別爲1/10,2/10和7/10。我們想編碼序列[1, 2]。腳本會給以下輸出（忽略-b N選項現在）：

$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2" 
000000111111|1111|111222222222222222222222222222222222222222222222 
------011222|2222|222000011111111122222222222222222222222222222222 
---------011|2222|222-------------00011111122222222222222222222222 
------------|----|-------------------------00111122222222222222222 
------------|----|-------------------------------01111222222222222 
------------|----|------------------------------------011222222222 
================================================================== 
000000000000|0000|000000000000000011111111111111111111111111111111 
000000000000|0000|111111111111111100000000000000001111111111111111 
000000001111|1111|000000001111111100000000111111110000000011111111 
000011110000|1111|000011110000111100001111000011110000111100001111 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
001100110011|0011|001100110011001100110011001100110011001100110011 
010101010101|0101|010101010101010101010101010101010101010101010101 

首先6線（前====線）表示的範圍從0.0到1.0，其上的間隔成比例的符號概率遞歸細分。註釋第一行：

[1/10][  2/10 ][     7/10      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 

然後我們再細分每個間隔：

[ 0.1][  0.2  ][     0.7      ] 
000000111111|1111|111222222222222222222222222222222222222222222222 
     [ 0.7 ][.1][ 0.2 ][   0.7     ] 
------011222|2222|222000011111111122222222222222222222222222222222 
            [.1][ .2][ 0.7    ] 
---------011|2222|222-------------00011111122222222222222222222222 

注意，一些間隔沒有細分。當沒有足夠的空間來表示給定精度內的每個子區間時（這是由-b選項指定的）。

每一行對應於輸入中的符號（在我們的示例中，序列號爲[1, 2]）。通過跟蹤每個輸入符號的子區間，我們將得到一個最終的區間，我們想用最少的位數進行編碼。在我們的情況下，它的第一子區間2上的第二行：

  [ This one ] 
------011222|2222|222000011111111122222222222222222222222222222222 

繼7行（====之後）表示相同的間隔在0.0到1.0，但細分根據二進制符號。每行都有一點輸出，通過在0和1之間選擇，您可以選擇左側或右側半子區間。例如比特01對應於第二行子區間[0.25, 05)：

    [ This one ] 
000000000000|0000|111111111111111100000000000000001111111111111111 

算術編碼器的想法是輸出比特（0或1），直到相應的間隔將是完全內部（或等於）間隔確定由輸入序列。在我們的案例中，它是0011。 ~~~~行顯示我們有足夠的位清楚地標識我們想要的時間間隔。

由|符號組成的垂直線表示可用於編碼輸入序列的比特序列（行）的範圍。