算術編碼

算術編碼是一種無損資料壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在於，其他的熵編碼方法通常是把輸入的訊息分割為符號，然後對每個符號進行編碼，而算術編碼是直接把整個輸入的訊息編碼為一個數，一個滿足的小數n。算術編碼工作原理.在給定符號集和符號機率的情況下，算術編碼可以給出接近最優的編碼結果。使用算術編碼的壓縮演算法通常先要對輸入符號的機率進行估計，然後再編碼。這個估計越準，編碼結果就越接近最優的結果。例: 對一個簡單的訊號源進行觀察，得到的統計模型如下：算術編碼可以處理的例子不止是這種只有四種符號的情況，更復雜的情況也可以處理，包括"高階"的情況。所謂高階的情況是指當前符號出現的機率受之前出現符號的影響，這時候之前出現的符號，也被稱為"上下文"。比如在英文文件編碼的時候，例如，在字母"Q"或者"q"出現之後，字母"u"出現的機率就大大提高了。這種模型還可以進行"自適應"的變化，即在某種上下文下出現的機率分佈的估計隨著每次這種上下文出現時的符號而自適應更新，從而更加符合實際的機率分佈。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。一個簡單的例子以下用一個符號序列怎樣被編碼來作一個例子： 假如有一個以A、B、C三個出現機會均等的符號組成的序列。若以簡單的分組編碼會十分浪費地用2 bits來表示一個符號： 其中一個符號是可以不用傳的x100% = 25%。這對於長序列是可行的因為有高效的、適當的演算法去精確地轉換任意進位制的數字。編碼過程的每一步，除了最後一步，都是相同的。編碼器通常需要考慮下面三種資料：編碼器將當前的區間分成若干子區間，每個子區間的長度與當前上下文下可能出現的對應符號的機率成正比。當前要編碼的符號對應的子區間成為在下一步編碼中的初始區間。例:對於前面提出的4符號模型：當所有的符號都編碼完畢，最終得到的結果區間即唯一的確定了已編碼的符號序列。任何人使用該區間和使用的模型引數即可以解碼重建得到該符號序列。實際上我們並不需要傳輸最後的結果區間，實際上，我們只需要傳輸該區間中的一個小數即可。在實用中，只要傳輸足夠的該小數足夠的位數，以保證以這些位數開頭的所有小數都位於結果區間就可以了。例:下面對使用前面提到的4符號模型進行編碼的一段資訊進行解碼。編碼的結果是0.538。像編碼器所作的那樣我們從區間[0,1)開始，使用相同的模型，我們將它分成編碼器所必需的四個子區間。分數0.538落在NEUTRAL坐在的子區間[0,0.6)；這向我們提示編碼器所讀的第一個符號必然是NEUTRAL，這樣我們就可以將它作為訊息的第一個符號記下來。然後我們將區間[0,0.6)分成子區間：我們的分數.538在[0.48, 0.54)區間；所以訊息的第二個符號一定是NEGATIVE。我們再一次將當前區間劃分成子區間：我們的分數.538落在符號END-OF-DATA的區間；所以，這一定是下一個符號。由於它也是內部的結束符號，這也就意味著編碼已經結束。效率低下的前一個例子中的訊息0.538可能已經由同樣短的分數 0.534, 0.535, 0.536, 0.537, 0.539 編碼。這表明使用十進製而不是二進位制引入了一些低效率。這是對的;三位十進位制的資訊內容是 formula_1 個位元;相同的訊息可以在二進位制分數 0.10001010 該 8 位元輸出大於資訊內容或訊息的熵，也就是：formula_2但是在二進位制編碼中必須使用整數位，因此該訊息的編碼器將使用至少8位，從而產生比熵內容大 8.4％ 的訊息。隨著訊息大小的增加，這種至多 1 位的低效率導致相對較少的開銷。此外，要求保護的符號機率為 [0.6, 0.2, 0.1, 0.1) ，但本例中的實際頻率為 [0.33, 0, 0.33, 0.33) 。如果為這些頻率重新調整間隔，則訊息的熵將是 4.755 位元，並且相同的中性負資料結束訊息可以被編碼為間隔 [0, 1/3) ; [1/9, 2/9) ; [5/27, 6/27) ; 和二進位制間隔 [0.00101111011, 0.00111000111) 。這也是算術編碼等統計編碼方法如何產生大於輸入訊息的輸出訊息的示例，尤其是在機率模型關閉的情況下。編碼.formula_4:the probability of x = n(from prediction)formula_5現在要對dataX做編碼，假設length(X) = Ninitiation: lower = formula_6 upper = formula_7for i=2:Nlower = formula_8upper = formula_9)end假設 lowerformula_10且C和b為整數(b越小越理想)，則dataX可以被編碼成formula_11且formula_11ex = 01110ans = b=5,C=141.假設要對X來做二進位(k=2)的編碼且經由事先的估計，X[i] = a 的機率為0.8,X[i] = b 的機率為0.2formula_13若實際上輸入的資料為X = a a a b a ainitial (X[1] = a): lower = 0, upper = 0.8When i=2, (X[2] = a): lower = 0, upper = 0.64When i=3, (X[3] = a): lower = 0, upper = 0.512When i=4, (X[4] = b): lower = 0.4096, upper = 0.512When i=5, (X[5] = a): lower = 0.4096, upper = 0.49152When i=6, (X[6] = a): lower = 0.4096, upper = 0.475136由於 lower = 0.4096, upper = 0.475136lower formula_14 upper所以編碼結果為formula_15,2進位,5bits解碼.假設編碼的結果為Y,length(Y) = b,其他的假設和編碼相同(k進位)initiation: lower = 0, upper = 1, lower1 = 1, upper1 = 1for i=1:Ncheck = 1;while check =1if there exists an n such thatformula_16 andformula_17 are both satisfied,then check = 0;elseformula_18formula_19j = j+1endX(i) = n;formula_20formula_21end資料長度.假設formula_4是預測的X[i] = n的機率,formula_23是實際上的X[i] = n的機率也就是說,若length(X) = N,當中會有formula_23N個elements等於n則formula_25另一方面，由於編碼的假設formula_26formula_27formula_28在機率的預測完全準確的情況下,formula_29Totoal coding length b 的範圍是formula_30formula_31算術編碼的總資料長度的上限比霍夫曼編碼更低自適應算術編碼.與其他類似的資料壓縮方法相比，算術編碼的一個優點是適應的便利性。適應是在處理資料時改變頻率表。只要解碼中的頻率表以與編碼相同的方式和相同的步驟被替換，解碼的資料就匹配原始資料。通常，同步基於在編碼和解碼過程期間出現的符號的組合。精度和再正規化.上面對算術編碼的解釋進行了一些簡化。尤其是，這種寫法看起來好像算術編碼首先使用無限精度精度的數值計算總體上表示最後節點的分數，然後在編碼結束的時候將這個分數轉換成最終的形式。許多算術編碼器使用有限精度的數值計算，而不是儘量去模擬無限精度，因為它們知道解碼器能夠匹配、並且將所計算的分數在那個精度四捨五入到對應值。一個例子能夠說明一個模型要將間隔[0,1]分成三份並且使用8位的精度來實現。注意既然精度已經知道，我們能用的二進位制數值的範圍也已經知道。一個稱為"再歸一化"的過程使有限精度不再是能夠編碼的字元數目的限制。當範圍減小到範圍內的所有數值共享特定的數字時，那些數字就送到輸出資料中。儘管計算機"能夠"處理許多位數的精度，編碼所用位數少於它們的精度，這樣現存的資料進行左移，在右面新增新的資料位以儘量擴充套件能用的資料範圍。注意這樣的結果出現在前面三個例子中的兩個裡面。算術編碼和其他壓縮方法的關係.霍夫曼編碼.算術編碼和哈夫曼編碼的相似程度很高——事實上，哈夫曼編碼只是算術編碼的一個特例。但是，算術編碼將整個訊息翻譯成一個表示為基數 "b"，而不是將訊息中的每個符號翻譯成一系列的以 "b" 為基數的數字，因此通常比哈夫曼編碼更能達到最優熵編碼。因為算術編碼不能一次壓縮一個資料，所以在壓縮iid字串時它可以任意接近熵。相反，使用霍夫曼編碼的擴充套件不會達到熵，除非字母符號的所有機率都是 2 的冪，在這種情況下，霍夫曼和算術編碼都實現熵。當霍夫曼編碼二進製字串時，即使熵低，也不可能進行壓縮。霍夫曼編碼為每個值分配 1 位元，產生與輸入長度相同的程式碼。相比之下，算術編碼可以更加地壓縮位元，接近最佳壓縮比formula_32解決霍夫曼編碼次優性的一種簡單方法是連線符號。在上面的例子中，在編碼之前對三個符號的序列進行分組將產生具有以下頻率的新「超符號」：透過這種分組，霍夫曼編碼每三個符號平均為 1.3 位元，或每符號 0.433 位元，而原始編碼中每符號一位元，即 formula_33 壓縮。允許任意大的序列隨意接近熵，但需要大量程式碼才能這樣做，因此不如算術編碼那麼實用。另一種方法是透過基於霍夫曼的 Golomb-Rice 編碼編碼遊程長度。這種方法允許比算術編碼或甚至霍夫曼編碼更簡單和更快的編碼/解碼，因為後者需要表查詢。在 {0.95, 0.05} 示例中，具有四位餘數的 Golomb-Rice 程式碼實現了壓縮率 formula_34 ，遠遠低於使用三位塊的壓縮率。 Golomb-Rice 程式碼僅適用於伯努利輸入，例如本例中的輸入，因此它不能代替所有情況下的阻塞。區間編碼.算術編碼與區間編碼有很深的相似淵源，以至於人們通常認為兩者的效能是相同的，如果確實有什麼不同的話也只是區間編碼僅僅落後幾個位的值而已。區間編碼與算術編碼不同，通常認為它不被任何公司的專利所約束。區間編碼的原理是這樣的，它沒有像算術編碼那樣從 [0,1] 開始並根據每個字元出現的機率把它分成相應的不同的小區間，它從如 000,000,000,000 到 999,999,999,999 這樣一個很大的非負整數區間開始，並且根據每個字元的機率劃分成小的子區間。當子區間小到一定程度最後結果的開頭數字出現的時候，那些數字就能夠“左移”出整個運算，並且用“右邊”的數字替換——每次出現移位時，就大體相當於最初區間的一個迴歸放大。關於算術編碼的美國專利.許多算術編碼所用的不同方法受美國專利的保護。其中一些專利對於實現一些國際標準中定義的算術編碼演算法是很關鍵的。在這種情況下，這些專利通常按照一種"合理和非歧視"這些授權是免費的，而在另外一些案例中，則收取一定的授權費用。RAND條款的授權協議不一定能夠滿足所有打算使用這項技術的使用者，因為對於一個打算生產擁有所有權軟體的公司來說這項費用是“合理的”，而對於自由軟體和開源軟體專案來說它是不合理的。在算術編碼領域做了很多開創性工作並擁有很多專利的一個著名公司是IBM。一些分析人士感到那種認為沒有一種實用並且有效的算術編碼能夠在不觸犯IBM和其它公司擁有的專利條件下實現只是資料壓縮界中的一種持續的都會傳奇。然而，由於專利法沒有提供“明確界線”測試所以一種威懾心理總讓人擔憂法庭將會找到觸犯專利的特殊應用，並且隨著對於專利範圍的詳細審查將會發現一個不好的裁決將帶來很大的損失，這些技術的專利保護然而對它們的應用產生了一種阻止的效果。至少一種重要的壓縮軟體bzip2，出於對於專利狀況的擔心，故意停止了算術編碼的使用而轉向Huffman編碼。關於算術編碼的美國專利列在下面。注意：這個列表沒有囊括所有的專利。關於更多的專利資訊請面的連結。 算術編碼的專利可能在其它國家司法領域存在，體專利中關於軟體在世界各地專利性的討論。參考."上面文章的一個早期版本."