數據壓縮算法研究

包冬梅

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

關鍵詞：數據壓縮;編碼;算法

1? ? 數據壓縮分析

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

2? ? 無損壓縮技術

2.1? 香農-范諾編碼

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

（1）給出一組原始的數據集，再通過統計的方式來取得其中各個字符出現的頻率，并且通過列表顯示。

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

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

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

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

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

根據香農-范諾編碼流程示例得出的編碼如表2所示。

據此可以得到這段數據的平均碼字長度：

2.2? 哈夫曼編碼

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

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

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

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

（4）從下到上構造編碼樹，根據樹的結構得到符號對應的編碼。

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

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

據此可以得到這段數據的平均碼字長度：

2.3? 游程長度編碼結果實例

游程長度編碼（run-length code）是柵格數據壓縮的重要編碼方法，利用空間冗余進行壓縮。基本算法是：將具體類似值的連續串用其長度或一個代表值來進行代替。游程長度編碼中，3個字節表示一個字符串;Sc是第一個字節的壓縮指示字符，第二個字節記錄連續出現的字符，第三個字節記錄重復字符出現的次數。由此可得出：當RL>3時，進行數據壓縮才有意義。因此，編碼時要判斷RL的數值，隨后再決定是否進行游程長度編碼。具體的游程編碼結果實例的源數據流如圖3所示。

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

2.4? 算數編碼

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

（1）按照各信源信號出現的頻率，將[0， 1）這個區間分成若干段，最終每個信號源會有對應的區間。

（2）將[0， 1）這個區間設置為初始間隔。

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

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

3? ? 結語

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

[參考文獻]

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997.

[2]吳樂南.數據壓縮[M].北京：電子工業出版社，2012.

[3]高瀟.地震波正演波場高效壓縮方法[D].合肥：中國科學技術大學，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