包冬梅

摘? ?要：數(shù)據(jù)及通信業(yè)務(wù)的擴大給信息傳輸及網(wǎng)絡(luò)傳輸帶來極大的壓力。為了更快、更有效地存儲及傳輸數(shù)據(jù)，需要對數(shù)據(jù)進行壓縮。數(shù)據(jù)壓縮不僅節(jié)省數(shù)據(jù)的存儲空間，而且能提高傳輸過程中的安全及效率。文章介紹了常用的幾種數(shù)據(jù)壓縮算法，包括香農(nóng)-范諾編碼、哈夫曼編碼、游程長度編碼和算數(shù)編碼等。

關(guān)鍵詞：數(shù)據(jù)壓縮;編碼;算法

1? ? 數(shù)據(jù)壓縮分析

數(shù)據(jù)壓縮是一種技術(shù)方法，在有用的信息不丟失的前提下還可縮減數(shù)據(jù)量、減少存儲的空間，可提高其存儲、處理效率及傳輸技術(shù)的方法。數(shù)據(jù)壓縮包含了兩種壓縮，分別是有損壓縮和無損壓縮。（1）有損壓縮是指重構(gòu)使用壓縮后的數(shù)據(jù)，其重構(gòu)數(shù)據(jù)后與原來的數(shù)據(jù)大有不用，但數(shù)據(jù)表達信息的方式不受影響，這種算法壓縮效率極高[1]。有損壓縮大多用于語音、圖像及視頻的數(shù)據(jù)壓縮。（2）無損數(shù)據(jù)壓縮是指對使用后的數(shù)據(jù)進行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原始的數(shù)據(jù)相同，主要用于文本文件、數(shù)據(jù)庫特殊的圖像數(shù)據(jù)及程序數(shù)據(jù)等類似的壓縮數(shù)據(jù)。該算法可把普通文件的數(shù)據(jù)壓縮到原本文件的1/4～1/2。常用的基于統(tǒng)計的無損壓縮算法有香農(nóng)-范諾編碼、哈夫曼編碼、游程長度編碼和算數(shù)編碼等。文中主要介紹無損數(shù)據(jù)壓縮算法。

2? ? 無損壓縮技術(shù)

2.1? 香農(nóng)-范諾編碼

香農(nóng)-范諾編碼（Shannon-Fano Coding）最早由Shannon[2]提出，可把短編碼分派給概率大的符號，通過二叉樹標出每個碼元發(fā)生出的概率。香農(nóng)-范諾編碼原理的具體算法如下：

（1）給出一組原始的數(shù)據(jù)集，再通過統(tǒng)計的方式來取得其中各個字符出現(xiàn)的頻率，并且通過列表顯示。

（2）根據(jù)各種字符出現(xiàn)的頻在進行排序，出現(xiàn)率最高者可列于左邊，出現(xiàn)率最低者配列于右邊。

（3）把列表分為兩部分，讓左部分的總頻率和數(shù)盡量接近于右部分的總頻率和數(shù)。

（4）數(shù)字“0”分配于左半邊的二進制數(shù)，數(shù)字“1”是右半邊的二進制數(shù)。

（5）最左、最右兩部分分別遞增操作第3～4步驟，每細分化一次都添加一位編碼，到最后，各個部分只含一個字符為終點。

為了更清楚地說明上述編碼的過程，可通過實例來演示：已知一組原始數(shù)據(jù)集中各個字符的出現(xiàn)頻次以及頻率從高到低排序，如表1所示。

根據(jù)香農(nóng)-范諾編碼流程示例得出的編碼如表2所示。

據(jù)此可以得到這段數(shù)據(jù)的平均碼字長度：

2.2? 哈夫曼編碼

哈夫曼編碼（Huffman Coding）[3]是1952年為壓縮文本文件而設(shè)計的編碼方法，是一種基于統(tǒng)計模型的無損壓縮編碼方法，是目前消除視頻信息冗余最常用的方法之一。主要思想是：針對符號出現(xiàn)概率進行編碼，為出現(xiàn)概率最大的符號賦予最短的碼字，從而使表示每個符號的平均比特數(shù)最小。這種算法是最佳的逐個符號編碼方式。哈夫曼編碼過程如下：

（1）將信源符號按概率從大到小排列。

（2）分配碼字長度時，將另個出現(xiàn)概率最小的兩個符號的概率相加，產(chǎn)生新的概率。

（3）把合成產(chǎn)生的新概率集合重新排序，重復(fù)（2），直到最后兩個概率之和為1。

（4）從下到上構(gòu)造編碼樹，根據(jù)樹的結(jié)構(gòu)得到符號對應(yīng)的編碼。

按照表1的例子得出的哈夫曼編碼如圖2所示。

根據(jù)哈夫曼編碼流程示例得出的編碼如表3所示。

據(jù)此可以得到這段數(shù)據(jù)的平均碼字長度：

2.3? 游程長度編碼結(jié)果實例

游程長度編碼（run-length code）是柵格數(shù)據(jù)壓縮的重要編碼方法，利用空間冗余進行壓縮?；舅惴ㄊ牵簩⒕唧w類似值的連續(xù)串用其長度或一個代表值來進行代替。游程長度編碼中，3個字節(jié)表示一個字符串;Sc是第一個字節(jié)的壓縮指示字符，第二個字節(jié)記錄連續(xù)出現(xiàn)的字符，第三個字節(jié)記錄重復(fù)字符出現(xiàn)的次數(shù)。由此可得出：當RL>3時，進行數(shù)據(jù)壓縮才有意義。因此，編碼時要判斷RL的數(shù)值，隨后再決定是否進行游程長度編碼。具體的游程編碼結(jié)果實例的源數(shù)據(jù)流如圖3所示。

相對其他無損壓縮算法，游程長度編碼實現(xiàn)原理更簡單，在編程上更容易實現(xiàn)，適用于二值圖像，在傳真壓縮中應(yīng)用廣泛。如果圖像中具有相同灰度值的圖像塊越大，壓縮率就越高。為了數(shù)據(jù)壓縮的通用性，通常將游程長度編碼和其他編碼技術(shù)綜合使用。

2.4? 算數(shù)編碼

算數(shù)編碼是20世紀80年代發(fā)展起來的熵編碼方法，原理是：將被編碼的數(shù)據(jù)序列表示成[0，1）區(qū)間，該間隔的位置與輸入數(shù)據(jù)的概率分布有關(guān)。信息越長，編碼表示的間隔就越小，表示間隔所需的二進制位數(shù)就越多。算數(shù)編碼的過程如下：

（1）按照各信源信號出現(xiàn)的頻率，將[0， 1）這個區(qū)間分成若干段，最終每個信號源會有對應(yīng)的區(qū)間。

（2）將[0， 1）這個區(qū)間設(shè)置為初始間隔。

（3）按照待處理的信號，將一個個信號源讀入，每讀入一個信號，就將該信號源在[0， 1）上的范圍等比例地縮小到最新得到的間隔中。

（4）依次迭代，不斷重復(fù)進行步驟（3），直到最后信號中的信源信號全部被讀完為止。

3? ? 結(jié)語

綜上所述，文中對幾種數(shù)據(jù)壓縮算法進行了闡述，通過對一些簡單的壓縮算法進行介紹，了解了數(shù)據(jù)壓縮的實現(xiàn)原理也掌握了不同壓縮算法的優(yōu)點及缺點。文中幾種壓縮算法的思路各有各的優(yōu)點，且相互補充多種壓縮軟件結(jié)合幾類算法，再根據(jù)具體應(yīng)用中的數(shù)據(jù)流特點來進行改進，從而開發(fā)出適用的軟硬件壓縮器。

[參考文獻]

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997.

[2]吳樂南.數(shù)據(jù)壓縮[M].北京：電子工業(yè)出版社，2012.

[3]高瀟.地震波正演波場高效壓縮方法[D].合肥：中國科學技術(shù)大學，2019.

Research on data compression algorithm

Bao Dongmei

（College of Computer， Hulunbuir University， Hulunbuir 021000， China）

Abstract：With the expansion of data and communication services， great pressure is brought to information transmission and network transmission. In order to store and transmit data faster and more effectively， data compression is needed. Data compression not only saves the storage space of data， but also improves the security and efficiency in the process of transmission. This paper introduces several commonly used data compression algorithms， including Shannon-Fano coding， Huffman coding， run length code and arithmetic coding.

Key words：data compression; coding; algorithms