轉自：http://deercrane.spaces.live.com/blog/cns!8BEF692B75EB8095!189.entry

算術編碼 + 統計模型 = 數據壓縮 - 第二部分：統計模型
（撼庭秋譯自http://compression.graphicon.ru/download/articles/ppm/nelson/arithmetic2.htm）

作者：Mark Nelson

　　這兩部分系列文章的第一篇以一些細節準確地解釋了什么是算術編碼。概括地講，算術編碼提供使用最佳位數目編碼符號的方法。由每個符號所使用的位數不一定像霍夫曼編碼（Huffman coding）的情況下一樣是一個整數。為了使用算術編碼壓縮數據，需要給數據一個模型。這個模型需要能夠完成兩件事來有效地壓縮數據：

·模型需要精確地預計輸入數據流中符號的頻率／概率。
·由模型生成的符號概率需要脫離均勻分布。

　　本文將討論有效達成這些目標，獲取高性能壓縮的一些方法。

建模

　　需要精確地預計輸入數據中符號的概率是算術編碼中固有的本質。這類編碼方法的原理是隨著字符出現概率的增加而減少編碼這個字符所需要的位數目。因此，如果字母“e”出現在輸入數據的概率是25%，它將只使用2位來編碼。如果字母“Z”在輸入數據中出現的概率只有1%，它可能要用10位來編碼。如果模型沒有精確地生成概率，它可能用10位來表示“e”并且用2位來表示“Z”，原因是用數據展開代替了壓縮。

　　第二個情況是模型需要創建脫離均勻分布的預計。體現在創建脫離均勻的預計上越好的模型，將獲得越好的壓縮率。例如，模型可能是按給所有256個可能的字符指定均勻分布的概率1/256來創建的。這個模型將創建一個與輸入文件大小嚴格一樣的輸出文件，因為每個符號將嚴格地用8位來編碼。只有通過正確地找到脫離均勻分布的概率才能減少位數目，而獲取壓縮率。當然，如第一種情況所規定，增加的概率需要精確地反映事實。

　　一個給定符號出現在數據流中的概率似乎是固定的，但是不完全是這樣。取決于所使用的模型，字符的概率可以改變很多。例如，當壓縮一個C程序時，換行符在文本中的概率可能是1/40。可以通過掃描整個文本并通過字符的總數除以這個字符出現的次數來決定這個概率。但是如果我們使用一個看前一個單個字符的建模技術，這個概率就變了。在這種情況下，如果前一個字符是“}”，換行符的概率增長為1/2。這改善了建模技術并獲得了更好的壓縮，盡管這兩種模型都生成精確的概率。

有限上下文建模

　　我將要在本文中介紹的建模類型稱為“有限上下文”建模。這種建模類型基于一個非常簡單的思想：每一個輸入符號的概率都是基于符號出現的上下文中計算而來。在所有我將在此說明的例子中，上下文由除前面已經碰到的符號外，沒有更多的東西所組成。模型的“序”稱為建立起環境的前面字符的數目。

　　最簡單的有限上下文模型將會是一個0序模型。這意味著每一個符號的概率獨立于任何前面的符號。為了實現這個模型，需要的所有事情是一個包含可以在輸入流中碰到的每一個符號的頻率計數。對于1序模型，你要明了256個不同的頻率表，因為你需要為每一個可能的上下文保持獨立的一組計數。同樣，2序模型需要能夠處理65,536個不同的上下文表。

自適應模型

　　隨著模型序的增長，壓縮率也應該隨之改善，這似乎是合乎正常的邏輯。例如，符號“u”在本文中的出現概率可能只有5%，但是如果前一個上下文字符是“q”，概率增長至95%。能夠預測具有高概率的字符所需要的位數目較少，以及較大的上下文應該會讓我創建更好的預測。

　　不幸的是，隨著模型序的線性增長，模型所消耗的內存呈指數級增長。使用0序模型，由統計消耗的空間可能跟256個字節一樣小。一旦模型的序增長至2或者3，甚至是很聰明地設計的模型也要消耗數百K字節。

　　壓縮數據的一個便利的方法就是單程掃描一遍要壓縮的符號為模型收集統計。然后進行第二遍掃描真正地編碼數據。然后統計常常預先考慮壓縮的數據，因此解碼程序將有一個統計的副本與其一起工作。如果模型的統計比要壓縮的數據消耗更多的內存，這個方法顯然將會有嚴重的問題。

　　這個問題的解決方法是執行“自適應”壓縮。在自適應數據壓縮中，壓縮程序和解壓縮程序都以相同的模型開始。壓縮程序使用已的有模型編碼符號，然后更新模型以說明新的符號。解壓縮程序同樣使用已有的模型解碼符號，然后更新模型。對壓縮程序和解壓縮程序來說，只要更新模型的操作一致，那么處理可以完美地操作而無須從壓縮程序傳送統計表給解壓縮程序。

　　自適應數據壓縮有一個稍微不利的一點就是它使用不如最佳的統計開始壓縮。不過，通過減少隨壓縮數據傳輸的開銷，自適應算法通常比固定統計模型執行得更好。

　　自適應壓縮真正要忍受的地方是在更新模型的開銷中。當使用算術編碼更新對某個特定符號的計數時，更新代碼有為所有其它符號更新累積的計數的潛在開銷，導致平均必須為每個單個符號的編碼和解碼執行128次算術操作。

　　因為在內存和CPU時間兩者中的高開銷，較高序的自適應模型可能在以后10年內變得可以實用。有點諷刺意味的是，隨磁盤空間和內存的降價，壓縮存儲在其中的數據的開銷也在降低。隨著這些開銷持續下降，我們將能夠實現比今天可以實踐的程序更加有效的程序。

一個簡單的例子

　　0序壓縮程序的一個例子在此說明在列表6-9中。（列表達式1-5在上個月的文章中。）COMP-1.C是壓縮程序驅動，EXPAND-1.C是展開程序驅動。MODEL.H和MODEL-1.C組成用于實現0序統計模型的建模單元。

　　當使用一個像這個例子程序一樣的固定序的模型時，壓縮程序自身相當簡單。程序只需要在循環中不停地從純文本文件中讀取字符，將字符轉換成算術編碼，編碼符號，然后更新模型。

　　在MODEL-1.C中的建模代碼是理解這段代碼是如何工作的關鍵。在上個月的文章中，我們看到每個字符在從0.0至0.1的基礎上放大的范圍中是如何“擁有”概率范圍的。為了用整數實現算術編碼，這個所有權按照從0到最大計數重新聲明為底計數和頂計數。統計有多精確留在MODEL.C中。

　　使用MODEL-1的所有可能符號的計數存放在一個稱為totals[]數組中。對于每一個c符號，底計數放在total[c]并且頂計數放在totals[c+1]。所有符號的總范圍放在totals[256]。這三個計數就是需要傳送給算術編碼程序來編碼一個給定符號的東西。

　　這使查找符號的計數的操作非常直接。不過，在符號編碼或者解碼后更新totals[]數組是另一個麻煩事。為了更新符號c的累積計數，在totals[]中從c上至256之間的每一個計數都需要增加。這意味著對編碼和解碼每一個字符平均要執行128個增加操作。對于像使用MODEL-1.C的簡單驗證程序來說，這并不是一個主要的問題，但是對于產品程序應該修改得更有效率一些。

　　減少增加操作數目的一個方法就是將最頻繁訪問符號的計數移到數組的頂部。這意味著模型必須明了每一個字符在total[]數組中的位置，但是使增加操作的數目有一個數量級的減少，會產生一個正面的負作用。這是對這個程序相對簡單的增強。使用這個技術的一個非常好的程序示例是發表在1987年6月期的《Communication of the ACM》的論文《Arithmetic Coding for Data Compression》的一部分。這篇論文由 Ian H.Witten、Radford Neal和John Cleary合著的論文是關于算術編碼的出色的信息資源，并且一些簡單的C源程序來說明其內容。

性能

　　COMP-1是一個只需要非常少內存的小程序。因為它只維護0序統計，當與那些通用的壓縮程序相比，它壓縮得并不是特別好。例如，當壓縮C代碼時，COMP-1通常會將文本壓縮成每個字節大約5位。而這并不足以吸引人，但對于需要在內存寶貴的環境中運行的實現來說會很有用。如果只是有一點內存可用，維護排序的列表將增加壓縮和展開的速度，而不影響壓縮率。

改進

　　COMP-1創建一個足夠用的驗證程序，但是它可能并不能讓每個人都很興奮。它壓縮得比0序霍夫曼編碼要好一點，但同時遠不及像ARC或者PKZIP這樣的程序。為了超過這些程序的壓縮率，我們需要開始給模型代碼加入一些增強功能。所有增強的頂點都在用于創建一個壓縮程序和一個展開程序的COMP-2.C和EXPAND-2.C以及MODEL-2.C中找到。

最高序的建模

　　對于用于此處的模型的每一個增強是增加模型的序。0序模型在計算文本文件中當前符號的概率時并不重視前面任何的任何符號。通過考慮文本文件中前面的符號，或者“上下文”，我們可以更精確地預測輸入符號。

　　當我們提升到2序或者3序模型時，一個問題立刻變得很明顯。驗證前面上下文使用的一個好例子就是在文字處理文本文件中嘗試預測“REQ”后面會出現哪個字符。下一個字符是“U”的概率至少應該是90%，我們編碼這個符號少于1位。但是我們使用自適應模型的時間可能是在我們建立起足夠大的統計體來開始用高概率預測“U”之前的某個時間。

　　在固定序模型中的問題是，每一個字符必須有一個有限非零概率，因此如果并且當它出現時就能被編碼。因為我們并沒有任何關于我們的輸入文本會有什么類型的統計方面的預備知識，我們通常需要從給每一個字符指定一個相等的概率開始。這意味著如果我們包括了EOF符號，從-1至255之間的每一個字節都有1/257出現在“REQ”之后的機會。現在，盡管在這個特別的上下文之后字母“U”在一行中出現了10次，它的概率將只是增加至11/267。當剩余的符號十有八九將不再可見時，它們占用概率表中的有值空間。

　　解決這個問題的方案是在給定的上下文中將所有符號的初始概率設為0，并且在前面未曾見過的符號出現時有方法回退到一個不同的上下文中。通過發出一個稱為轉義碼（Escape code）的特殊編碼來做到這一點。對于前面的“REQ”的上下文，我們可以將轉義碼的計數置為1，并且所有其它符號的計數置為0。在“REQ”后面字符“U”第一次出現時，我們將必須在一個不同的上下文中“U”的編碼之后發出轉義碼。在隨后立即更新模型期間，我們把在“REQ”上下文中的“U”的計數置為 1，因此它現在的概率為 1/2。根據隨著字符概率的遞增它的每一次出現所需要的位數目是遞減的原則，下一次它出現時，將只需用1位來編碼它。

　　然后明顯的問題是：在發出轉義碼之后，我們使用稱為我們的“回退”上下文做什么呢？在MODEL-2中，如果3序上下文生成一個轉義碼，下一個要嘗試的上下文是2序上下文。這意味著上下文“REQ”第一次被使用，并且“U”需要被編碼，然后生成一個轉義碼。隨后，MODEL-2程序回退到2序模型，并且使用上下文“EQ”嘗試編碼字符“U”。這會繼續向下進行直到0序上下文。如果在0序仍然生成轉義碼，我們回退到一個特殊的序（-1）上下文。這個-1上下文在初始化時建立，每一個可能符號的計數為1，并且從不會更新。因此它保證能夠編碼每一個符號。

　　使用這個轉義碼技術意味著對驅動程序只做少許的修改。COMP-2.C程序現在處在一個循環中嘗試編碼它的字符：

do {
　　escaped = convert_int_to_symbol(c, &s);
　　encode_symbol(compressed_file, &s);
} while (escaped);

　　建模代碼負責記住當前的序是多少，并且只要轉義碼發出時就遞減它。甚至更復雜的是明了需要哪一個上下文表用于當前序的建模模塊的工作。

更新模型

　　最高序建模算法的使用要求我們需要記錄從每個序至最高序的全部上下文表，而不是只記錄用于最高序的一組上下文表。這意味著如果我們正在進行2序建模，就有一個0序表、256個1序表以及65,535個2序表。當新來字符已經編碼過或者解碼過時，建模編碼需要更新每一個序的相關表。在前一個例子中，“U”在“REQ”之后，建模代碼將更新3序“REQ”表中“U”的計數，2序“EQ”表中的“U”的計數，1序“Q”表中的“U”的計數，以及0序表中“U”的計數。

　　更新所有這些表的代碼看起來如下：

for (order = 0; order <= max_order; order++)
　　update_model(order, symbol);

　　對這個算法進行少許修改可以產生既可以更快地更新又可以獲得更好的壓縮。我們可以只更新這些實際參與編碼字符的模型，而不是為當前上下文更新所有不同序的模型。例如，如果“U”在“REQ”之后作為轉義碼（ESCAPE）編碼，我們只遞增在“REQ”和“EQ”模型中“U”的計數，因為只是在“EQ”表中找到“U”的計數。“R”和“”兩個表都不會受影響。

　　這個對全部更新方法的修改稱為“排除更新”（update exclusion），因為它排除了不用更新的較低序模型。這在壓縮率方面通常有一個較小但是值得注意的改時。排除更新的工作基于一個事實，即如果符號在較高序的模型中頻繁出現，它們常常不會出現在較低序的模型中，這意味著我們不必在較低序的模型中增加它們的計數。使用了排除更新方法的更新代碼看起來如下：

for(order = encoding_order; order <= max_order; order++)
　　update_model(order, symbol);

轉義概率

　　當我們第一次開始編碼文本流時，我們會順理成章地發出相當多的轉義碼。從這一點看，用于編碼轉義碼的位數目可能會對達到的壓縮有較大的影響，特別是對小文件來說。在MODEL-2A.C中，我們將轉義碼的計數置為1并將其保持為1，而不管剩余上下文表的狀態。這與Bell、Cleary和Witten稱為“A 方法”（Method A）相當。B方法（Method B）將轉義字符的計數置為目前定義在上下文表中符號的數目。因此，如果目前為止已經見過十一個不同的字符， 那么轉義符號的計數不管是多少將置為11。

　　A方法和B方法兩種方法似乎都工作得相當好。在MODEL-2.C中的代碼可以很容易地進行修改以支持這兩種方法之一。對于A方法和B方法最好的事情可能是它們都不需要密集的計算。當使用A方法時，可以將轉義符號加入表中，更新有這個符號的表并不會比更新沒有這個符號的表耗費更多的工作。

　　在MODEL-2.C中，我已經實現了一個些微復雜點的轉義符計數的計算算法。這個算法在計算轉義符概率時嘗試考慮三個不同的因素。首先，隨著定義在上下文表中的符號數目的增加，轉義符概率將會減少，這似乎是有意義的。當表中的256個符號全部定義后，它達到它的最大值，使轉義符的概率成為0。

　　其次，這個算法嘗試考慮表中對隨機性的估量。通過將可以在表中找到的最大計數除以平均計數可以計算出這個隨機量。這個比率越高，表的隨機性就越低。在“REQ”表中有一個好例子。它可能只定義了三個符號：有50個計數的“U”、10個計數的“U”和3個計數的“.”。“U”的計數50與平均計數21的比率相當高。這意味著字符“U”可以用相當高的精確度來預測，并且轉義符的概率應該更低。在一個高計數是10，并且平均計數是8的表中，似乎有更多一點隨機性，并且轉義符的概率可能更高。

　　最后一個因素在通過簡單地計算對于這個特定的表來說已經見過多少個符號來判斷轉義符概率的時候考慮。隨著符號數目的增長，表的可預測性上升，使轉義符的概率下降。

　　我用于計算轉義符號的計數數目的公式在下面說明：

count = (256 - number of symbols seen) * number of symbols seen
count = count / (256 * the highest symbol count)
if count is less than 1
　　count is 1

　　在這個等式中丟失的變量是未出現符號的計數。這是隱含在計算中，因為轉義符概率是轉義符計數除以未出現符號計數。 未出現符號計數將自動地將轉義符的計數縮小成概率。???

記分板

　　當使用最高序建模技術時，一些額外的增強可以用來改善壓縮效率。當我們首先嘗試使用最高序上下文壓縮符號時，我們可以生成符號的編碼，或者生成轉義碼。如果我們生成轉義碼，它意味著符號以前在這個上下文中沒有出現過，因此我們可以將其計數為0。但是我們通過生成轉義碼獲得了一些信息。我們可以考慮轉義符的上下文并且生成與要被編碼的符號不匹配的符號列表。然后在我們在較低序模型進行計算時，可以將這些符號臨時計數為0。在這個特定的字符的編碼工作完成后，再將這些符號的計數恢復成它們的永久值。

　　下面說明一個例子。如果現在的上下文是“HAC”，并且下一個符號是“K”，我們將使用下面的表來編碼K。不用記分板，“HAC”上下文生成一個具有1/6概率的轉義符。“AC”上下文生成具有1/7概率的轉義符。“C”上下文生成具有1/40概率的轉義符，以及“”上下文最后生成具有1/73概率的“K”。

　　　""　　　　　　 "C"　　　　　　 "AC"　　　　　　"HAC"
-------------------------------------------------------------------------
　ESC　　　1　　　ESC　　　1　　　ESC　　　1　　　ESC　　　1
　'K'　　　1　　　'H'　　 20　　　'C'　　　5　　　'E'　　　3
　'E'　　 40　　　'T'　　 11　　　'H'　　　2　　　'L'　　　1
　'I'　　 22　　　'L'　　　5　　　　　　　　　　　'C'　　　1
　'A'　　　9　　　'A'　　　3

　　如果我們使用記分板來排除前面見過的字符的計數，我們可以在這些概率中做出重大的改善。第一個“HAC”的轉義符的編碼不受影響，因為之前并沒有看到字符。不過，“AC”的轉義碼從它的計算中消除“C”符號，結果得到的概率是1/3。“C”轉義碼從它的概率中排除“H”和“A”的計數，概率從1/40上長到1/17。并且最終，“”上下文通過排除“E”和“A”的計數，將概率從1/73上升到1/24。這使編碼這個字符所要求的位數目從14.9降為12.9，可觀的節約。

　　保持符號記分板在壓縮中大多數情況下都會得到一些改進，并且它從不會將事情弄糟。使用記分板的主要問題是所有較低序上下文的概率表在每次表被訪問時都必須重新計算。這導致編碼文本所要求的CPU時間大大增加。記分板留在MODEL-2.C中，以便在使用它壓縮文本時驗證可能獲得的結果。

數據結構

　　對基本建模的所有改善假設較高序建模實際上可以在目標機器上完成。隨著序的增加內存是問題。對于 MODEL-1中的0序模型，累積的總表占用516字節的內存空間。如果我們對1序使用相同的數據結構，內存的使用將暴漲到133K字節，這仍然是一個可以接受的數目。但是增到達2序時統計單元的內存需求將增至34M字節！因為我們喜歡能夠試驗甚至比2序更高的序，我們需要重新設計數據結構來容納計數。

　　為了節省內存空間，我們必須重新設計上下文統計表。在MODEL-1中的表通過將每個符號被用作直接索引到一對計數，來使其自身盡可能地簡單。在1序模型中，通過一次在上下表的數組中的索引來找到合適的上下文表，然后再次索引正在被討論的符號，代碼看起來如下：

low_count = totals[last_char][current_char];
high_count = totals[last_char][current_char+1];
range = totals[last_char][256];

　　這很方便，但是有巨大的浪費。首先，全部的上下文空間甚至沒有使用的表都被分配了。其次，在這些表中，為所有的符號都分配了空間，而不管這些符號有沒有見過。這兩個因素導致在較高序模型中有巨大數量的內存被浪費。

　　第一問題，即為沒有使用的上下文預留了空間的解決方法是將上下文表組織成一個樹。我們可以從將0序上下文表放在一個已知位置開始，然后用它來包含指向1序上下文表的指針。1序上下文表將包含它自身的統計，以及指向2序上下文表的指針。這樣繼續下去，直到上下文樹的葉子包含了n序表，而沒有指向更高序的指針為止。

　　通過使用樹結構，我們可以將沒有使用的指針節點置為空指針，直到上下文出現。一旦上下文出現，創建一個表并將其加入到樹結構的父節點上。

　　第二個問題是每次新表創建的時候也創建了表中的256個計數。事實是，最高序的上下文經常只有少數幾個符號，因此我們可以通過只為那些在某個上下文中可見的符號分配內存來節省許多空間。

　　在實現了這些改變后，我得到了一組如下的數據結構：

typedef struct {
??? unsigned char symbol;
??? unsigned char counts;
} STATS;

typedef struct {
??? struct context *next;
} LINKS;

typedef struct context {
??? int max_index;
??? STATS *stats;
　　LINKS *links;
??? struct context *lesser_context;
} CONTEXT;

　　新的CONTEXT結構有四個主要元素。第一個是計數器max_index。max_index告訴當前在某個特定上下文表中定義了多少個符號。當表第一次創建時，它并沒有定義符號，并且max_index是-1。完全定義的表的max_index是255。Max_index告訴為*stats和*links所指向的數組分配了多少個元素，每一個元素包含一個符號和對這個符號的計數。如果CONTEXT表并不是最高序的表之一，它也將有一個links數組。對于定義在stats數組中的符號來說，在links表中將會有一個指向下一個更高序CONTEXT表的指針。

　　CONTEXT表的樹的例子放在在圖1中。放在這里的表將在保持最大3序統計的時候，輸入文“ABCABDABE”后創建。9個輸入符號已經生成了一個相當復雜的數據結構，但是它在數量級上比一個數組的數組成的結構要小。

　　　Order 0　　　　　　　Order 1　　　　　　　Order 2　　　　　　Order 3
┌─────────┬─────────┬─────────┬─────────┐
│Context: ""　　　 │Context: "A"　　　│Context: "AB"　　 │Context: "ABC"　　│
│Lesser: NULL　　　│Lesser: ""　　　　│Lesser: "B"　　　 │Lesser: "BC"　　　│
│Symbol Count Link │Symbol Count Link │Symbol Count Link │Symbol Count Link │
│　A　　　3　　"A" │　B　　　3　 "AB" │　C　　　1　 "ABC"│　A　　　1　 NULL │
│　B　　　3　　"B" ├─────────┤　D　　　1　 "ABD"├─────────┤
│　C　　　1　　"C" │Context: "B"　　　│　E　　　1　 "ABE"│Context: "BCA"　　│
│　D　　　1　　"D" │Lesser: ""　　　　├─────────┤Lesser: "CA"　　　│
│　E　　　1　　"E" │Symbol Count Link │Context: "BC"　　 │Symbol Count Link │
└─────────┤　C　　　1　 "BC" │Lesser: "C"　　　 │　B　　　1　 NULL │
　　　　　　　　　　│　D　　　1　 "BD" │Symbol Count Link ├─────────┤
　　　　　　　　　　│　E　　　1　 "BE" │　A　　　1　 "BCA"│Context: "CAB"　　│
　　　　　　　　　　├─────────┼─────────┤Lesser: "AB"　　　│
　　　　　　　　　　│Context: "C"　　　│Context: "CA"　　 │Symbol Count Link │
　　　　　　　　　　│Lesser: ""　　　　│Lesser: "A"　　　 │　D　　　1　 NULL │
　　　　　　　　　　│Symbol Count Link │Symbol Count Link ├─────────┤
　　　　　　　　　　│　A　　　1　 "CA" │　B　　　1　 "CAB"│Context: "ABD"　　│
　　　　　　　　　　├─────────┼─────────┤Lesser: "BD"　　　│
　　　　　　　　　　│Context: "D"　　　│Context:"BD"　　　│Symbol Count Link │
　　　　　　　　　　│Lesser: ""　　　　│Lesser: "D"　　　 │　A　　　1　 NULL │
　　　　　　　　　　│Symbol Count Link │Symbol Count Link ├─────────┤
　　　　　　　　　　│　A　　 1　　"DA" │　A　　　1　 "BDA"│Context: "BDA"　　│
　　　　　　　　　　├─────────┼─────────┤Lesser: "DA"　　　│
　　　　　　　　　　│Context: "E"　　　│Context: "BE"　　 │Symbol Count Link │
　　　　　　　　　　│Lesser: ""　　　　│Lesser: "E"　　　 │　B　　　1　 NULL │
　　　　　　　　　　│Symbol Count Link │Symbol Count Link ├─────────┤
　　　　　　　　　　└─────────┴─────────┤Context: "DAB"　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│Lesser: "AB"　　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│Symbol Count Link │
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│　E　　　1　 NULL │
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　├─────────┤
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│Context: "ABE"　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│Lesser: "BE"　　　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│Symbol Count Link │
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　└─────────┘

　　　　　　　　　　　　　　　　　　"ABCABDABE"

　　　　　　　　　　　　　　　　　　　　圖1

　　在這個結構中我們沒有解釋的一個元素是lesser_context指針。當使用更高序模型時，對這個指針的需要變得很明顯。如果我的建模代碼正在嘗試定位3序上下文表，它首先掃描一遍0序符號列表以查找第一個符號，匹配，然后掃描1序符號列表，等等。如果在較低序模型中的符號列表相對較滿，這個掃描可能會是較長的過程。更糟的情況是，每次生成轉義碼后，當查找較低序上下文時，這個過程必須重復。這些搜索會消耗過度量的CPU時間。

　　這個問題的解決方法是為每個表維護一個指針，這個指針指向比其低一級序的上下文的表。例如，上下文表“ABC”將有它的指向“BC”的向后指針，“BC”有一指向“C”的向后指針，“C”也將有一個指向“”即空表的指針。然后，建模代碼需要總是要有一個指向當前最高序上下文的指針。通過這一點，查找order-i上下文表簡單地說實質是進行指針操作。

　　例如，在圖1中說明的表中，假設下一個輸入文本是“X”，并且當前的上下文是“ABE”。不需要利用lesser上下文指針的好處，我們不得不為符號“X”檢查3、2、1和0序表。這會進行總共15次符號比較，以及3次表查找。使用反向指針消除了所有的符號比較，并且只讓我進行3次表查找。

　　在維護后向指針中的工作發生在更新模型期間。當更新圖1上下文樹，以使其在“ABE”之后包含“X”，建模代碼必須為每一個序／上下文執行一組單向查找。這個代碼放在MODEL-2.C中的add_character_to_model()程序中。每次創建新表時，需要同時創建后向指針，在設計更新程序時要注意這一情況。

最后一筆：表1和2

　　對MODEL-2.C中的上下文樹的最后一筆是加上兩個特殊表。1序表前面已經討論過。這是一個每個符號具有固定概率的表。如果在任何較高序模型中都符號不能找到符號，我們保證它一定會出現在1序模型中。這個表是最后的手段。因為它必須保證它總是能夠為每一個符號提供一個編碼，我們不用更新這個表，這意味著它為每一個符號使用一個固定的概率。

　　另外，我增加了一個用于將控制信息從編碼程序傳送到解碼程序的特殊2序表。例如，編碼程序可以傳送一個-1給解碼程序來表示一個EOF情況。因為正常的符號總是作為范圍從0到255的無符號值來定義的，建模代碼將一個負數認作一個生成轉回2序表的所有路徑的轉義碼的特殊符號。建模代碼也可以檢測到因為它是一個負數，當調用update_model()代碼時，符號將被忽略的情況。

模型刷新（Model Flushing）

　　創建2序模型讓我將一個第二控制碼從編碼程序傳送到展開程序。這就是告訴解碼程序將統計刷出模型的刷新碼（Flush code）。我在壓縮程序的性能開始減退時執行這個操作。這個下降比率是可調的，但是我曾經使用過我可以容忍的相當于最壞壓縮率90%的統計。當超過這個比率時，我通過將所有的計數除以2來刷新模型。這會給較新的統計更多的權重，這樣應該對改善模型的性能有所幫助。

　　實際上模型只要在輸入符號流中的字符劇烈變化時就可能會刷新。例如，如果程序正在壓縮可執行文件，可執行代碼壓縮期間，累積的統計可能在壓縮程序的數據時沒有值。不幸的是，定義檢測輸入的“自然改變”的算法并不容易。

實現

　　即使在這里使用稍微復雜些的數據結構，圍繞MODEL-2.C的壓縮程序和展開程序的創建有巨大的內存要求。當運行在內存限制為640K的DOS機器上時，這些程序也必須限制為1序，或者對于有較高冗余率的文本限制為2序。

　　為了在二進制文件上測試較高序的壓縮率，對于這些程序來說有三個選擇。首先，它們可以使用Zortech C并用EMS_handle指針來編譯。其次，它們可以使用DOS Extender，如Rational Systems 16/M來創建。第三，它們可以在支持虛擬內存的機器上，如VMS創建。在這里發布的代碼是以嘗試在所有這三種選擇中可移植的方式編寫。

　　我發現用額外1M字節的EMS，我實際上在我的PC上使用3序壓縮模型來壓縮任何ASCII文件。一些二進制文件要求更多的內存。我的Xenix系統使用3序壓縮模型沒有問題，并且按速度來說全面取得最佳性能。我混合使用多個DOS Extender。出于未知的原因，我使用Lattice C 286和Microsoft C + DOS 16/M的測試比Zortech的 EMS code慢很多，而邏輯將說明與此相反的事實。它也并不是優化的問題，因為當在640K之內時，Lattice和Microsoft實現運行得比Zortech快。用Lattice C/286和Zortech 2.06 code創建的可執行代碼可以在DDJ的清單服務上獲得。Rational Systems 16/M授權協議要求特許使用金，因此代碼不能發布。

測試和比較：CHURN

　　為了測試壓縮程序，我創建了一個稱為CHURN的通用測試程序。CHURN通過遍歷一個目錄及其子目錄來簡單地攪拌，壓縮，然后展開它在那里找到的所有文件。在每一次壓縮／展開之后，比較最初的輸入和最終的輸出來確保它們是一致的。對時間和空間的壓縮統計也加入到累積總數中，并且程序繼續。在程序完成之后，它打印出運行完后的累積統計，以便可以檢測它們。（CHURN和一個它的Unix變體－－CHURNX，出于空間的考慮，在此并不列出。這兩個程序都可以從DDJ清單服務上獲得。）

　　用一個包含要測試數據的目錄的名稱作為參數調用CHURN。我通常將CHURN的輸出重定向到一個日志文件中，以備以后分析，調用看起來如下：

churn c:\textdata > textdata.log

　　壓縮程序將一些信息寫到stderr，因此這此信息在壓縮運行的時候可以顯示在屏幕上。注意隨著測試不同的程序，CHURN.C按照它調用的是spawn()還是system()必須作一些修改。

　　在下面表1中說明的是當根據兩個不同的輸入體測試不同的壓縮程序時返回的結果。第一個例子是TEXTDATA，有大約1M字節的一組文本文件，由源代碼、字處理文件和文檔組成。第二個例子，BINDATA，是大約1M字節的一組隨機選擇的文件，包括可執行文件，數據庫文件以及二進制圖像等等。

　　我在這兩個數據上用七種不同的壓縮程序完成了測試。MODEL-1是在本文開頭討論的0序示例模型。MODEL-1A實現1序模型而不需要轉義碼。MODEL-2A實現最高上下文的1序算法，它將為前面未出現過的符號生成轉義碼。最后，MODEL-2是一個實現了所有在本文中所討論的全部改善的最高上下文3序模型。

　　就比較而言，三個基于字典的編碼方案也可以運行在數據集中。COMPRESS是在Unix系統上廣泛使用的16位 LZW實現。使用16位的PC實現占用大約500K的內存。LZHUF是一個由Haruyasu Yoshikazi編寫的具有自適用霍夫曼編碼階段的LZSS程序，后來由Paul Edwards修改并投稿給Fidonet。這與用在LHARC程序中的壓縮本質上是相同的。最后，由PKWare推出的商業產品PKZIP 1.10，（Glendale Wisconsin），我們也在數據集上進行了測試。PKZIP使用一個在程序的文檔中討論的私有基于字典的方案。

　　結果說明了完全優化的MODEL-2算法在此測試的數據集上提供了超強壓縮性能，并且在基于文本的數據上執行得極好。二進制數據似乎并不適合統計分析，基于字典的方案在性能上取得與MODEL-2接近一致的結果。

　TEXTDATA - Total　input bytes: 987070　Text data
----------------------------------------------------------------------------------
　Model-1　 Fixed context order-0.　　　　　 548218 bytes　4.44 bits/byte
　Model-1A　Fixed context order-1.　　　　　 437277 bytes　3.54 bits/byte
　Model-2A　Highest context, max order-1.　　381703 bytes　3.09 bits/byte
　COMPRESS　Unix 16 bit LZW implementation.　351446 bytes　2.85 bits/byte
　LZHUF　　 Sliding window dictionary　　　　313541 bytes　2.54 bits/byte
　PKZIP　　 Proprietary dictionary based.　　292232 bytes　2.37 bits/byte
　Model-2　 Highest context, max order-3.　　299327 bytes　1.94 bits/byte

　BINDATA - Total　input bytes: 989917　Binary data
----------------------------------------------------------------------------------
　Model-1　 Fixed context order-0.　　　　 　736785 bytes　5.95 bits/byte
　COMPRESS　Unix 16 bit LZW implementation.　662692 bytes　5.35 bits/byte
　Model-1A　Fixed context order-1.　　　　　 660260 bytes　5.34 bits/byte
　Model-2A　Highest context, max order-1.　　641161 bytes　5.18 bits/byte
　PKZIP　　 Proprietary dictionary based.　　503827 bytes　4.06 bits/byte
　LZHUF　　 Sliding window dictionary　　　　503224 bytes　4.06 bits/byte
　Model-2　 Highest context, max order-3.　　500055 bytes　4.03 bits/byte

總結

　　根據壓縮率，這些測試說明統計建模可以至少與基于字典的方法執行得一樣好。不過，由于這些程序有較高的資源需要，它們目前稍微有點不實際。MODEL-2相當慢，以范圍在每秒1K之內的速度壓縮數據，并且需要大量的內存用于較高序建模。不過，隨著內存正在變得更便宜并且處理器變得更強大，在此說明的這類方案可能變得實用。它們在今天可以用于存儲或者傳輸開銷極高的情形。

　　使用算術編碼的0序自適應建模在今天可以有效地應用于要求極低內存消耗的情況。壓縮率可能不如更有老練的模型，但是內存的消耗是最小的。

增強

　　超過在這里討論的實現，這些算法的性能可以得到重大的改進。第一個改進的區域將是內存管理。當程序運行時內存溢出，它們立刻終止。更明智的方法將是開始時為統計提供固定數量的有效內存。當統計填滿空間，然后程序將停止更新表，并且只使用它有的東西。這將意味著實現內部內存管理程序而不是使用C運行時庫例程。

　　另一個潛在的改時將在用于上下文表的樹數據結構中。通過使用哈希來定位表會相當快，并且可以要求較少的內存。上下文表自身也可以得到改善。當一個表到達超過為其定義的潛在符號的50%的點時，可以使用另一個將計數存儲在線性數組中的數據結構。這會允許更快的索引，并且降低了內存需求。

　　最后，嘗試自適應地修改所使用的模型的序的方法可能是有價值的。當使用3序統計壓縮時，輸入文本的前面部分在統計表填滿時生成許多轉義碼。開始使用0序統計編碼而保持3序統計應該是可能的。隨著表被填滿，用于編碼的序可能會增長直到達到最大值。

列表 6 comp-1.c 0序固定上下文壓縮程序的驅動程序。通過從文件中讀取符號，將它們轉換成頂、底、范圍集，然后對它們進行編碼，它遵守在BILL.C中為壓縮程序說明的模型。 列表 7 expand-1.c 使用0序固定上下文模型的解壓縮程序的驅動程序。 列表 8 model.h 需要與在model-1.c或model-2.c中發現的建模代碼接口的函數原型和外部變量聲明。 列表 9 model-1.h 用于0序固定上下文數據壓縮程序的建模模塊。 列表 10 comp-2.c 用于可變序的有限上下文壓縮程序的驅動程序模塊。最大的序由命令行選項確定。這個特別的版本也監控壓縮率，并且只要本地（256符號）壓縮率達到或者高于90%時，刷新模型。 列表 11 expand-2.c 這個模塊是可變有限上下文展開程序的驅動程序。最大的序由命令行選項決定。這個特別版本可以響應由壓縮程序插入在位流中的刷新碼（FLUSH code）。 列表 12 model-2.c 這個模塊包含所有與comp-2.c和expand-2.c一起使用的建模函數。這個建模單元明了從0至max_order所有上下文，缺省是3。 列表 13 churn.c 這是用于測試壓縮/解壓縮程序精確度、速度和壓縮率的工具程序。用一個單個參數調用CHURN.EXE將引起CHURN壓縮然后解壓縮在指定目錄下的每一個文件，檢查壓縮率和操作的精確度。這是在你認為你的新算法工作正確時可以整天運行的一個好程序。 列表 14 churnx.c

churn程序工作在Unix系統上的版本。

轉載于:https://www.cnblogs.com/aquar/archive/2009/11/08/3451478.html

總結

以上是生活随笔為你收集整理的[转]算术编码+统计模型=数据压缩 - 第二部分：统计模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。