文本壓縮技術

文本壓縮是指用較少的位或位元組來表示文本，這樣將可以顯著地減小計算機中存儲文本的空間大小。通常說的“文本壓縮”都是無損壓縮。

基本介紹

• 中文名：文本壓縮技術
• 外文名：Text compression technology
• 定義：用較少的位或位元組來表示文本
• 目的：減小計算機中存儲文本的空間大小
• 特點：無損、通用等
• 學科：計算機科學

簡述

為了存儲和傳輸數據，減少數據所占用空間的大小是很有用的。完成這項工作的技術稱為數據壓縮。過去由於存儲的局限性，需要進行數據壓縮。現在，雖然存儲容量不受限制，但由於要與他人共享數據，網路具有固有的頻寬限制，定義了在固定時間內從一個地點傳輸到另一個地點的最大位數或位元組數，因此也需要進行數據壓縮。

壓縮率說明了壓縮的程度，是用原始數據的大小去除壓縮後的數據大小。計算壓縮率可以是位數、字元數或其他單位，只要這兩個值採用的單位相同即可。壓縮率是一個0到1之間的數。壓縮率越小，壓縮程度越高。

數據壓縮技術可以是無損的，即解壓縮後的數據沒有丟失任何原始信息。數據壓縮也可以是有損的，即在壓縮過程中丟失了一些信息。儘管不希望丟失信息，但在某些情況下，丟失是可以接受的。在處理數據表示和壓縮時，往往要在精確度和數據大小之間做出權衡。

主要方法

通信頻寬是一種昂貴的資源。許多用戶希望儘可能地減少傳送的總“比特”數，即文本壓縮。此外，文本壓縮也有保密的意義。下面介紹實現文本壓縮的主要方法。

1．採用符號有限集合編碼及替換方法

實際套用中，報文中的許多數據項都可以用編碼表示。如器材庫的器材名稱，設其為10個字元，採用ASCII碼表示後，則一個器材名稱占70位。若給器材進行編號，就可以大大壓縮原器材名的比特數。如果有1萬種器材，用14位二進制編碼就足夠了。這樣使器材名由原來的70位壓縮成14位。報文中其他數據項也可採用同樣的方法進行壓縮替換。此外很多場合可以採用一目了然的方式存儲信息。如日期的存儲，可寫成正規的1989年6月1日，也可編寫成89.6.1。可用應用程式來完成這種替換。

在很多情況下，如果是以人們都能“一目了然”的方式存儲信息，勢必包含有許多冗餘的信息。常常利用程式來壓縮冗餘信息。

2．字元的可變長編碼

一般的字元編碼位數都是固定的。數據傳輸過程中，字元的出現機率分布懸殊很大，通常數字比字母出現的頻率大，而數字0又占了很大的比例。在英文中，各字母出現的機率也不同，字母E出現的頻率是字母Q的100倍。下面介紹一種更為緊湊的編碼方式。它採用不同長度的位進行編碼，對出現頻率高的字元給以位數最短的編碼——霍夫曼編碼。

霍夫曼編碼技術只適用於字元出現機率不同的場合，如果出現的機率相同，採用霍夫曼編碼反而不利，字元的機率分布越不均勻，則效果越好。

實現霍夫曼編碼的方法是把原來的字元作為存儲器地址查詢表，找出字的編碼。因為存儲器的位置長度是固定的，而編碼是可變的，所以要用標誌說明用哪些位。為了方便起見，可以根據霍夫曼編碼理論對產生的最長編碼進行壓縮。最長的編碼共17位，而實際使用時最大長度縮減到14位。解碼也同樣可以用查表的方法來處理。為節省存儲空間，可採用樹結構。

如果先將重複字元壓縮，再使用霍夫曼編碼，則壓縮量還要增加。研究結果表明，利用霍夫曼編碼，對規整的程式文本進行壓縮，其壓縮量為55%～57%;對目標檔案進行壓縮，壓縮量為35%～45%。

常見算法

GZIP

Deflate算法是同時使用了LZ77與哈夫曼編碼的一個無損數據壓縮算法，Gzip算法是以Deflate算法為基礎擴展出來的一中算法。Gzip是一種數據壓縮格式，一般情況下使用Gzip壓縮可以達到70%左右的壓縮率，例如你的網頁是100K，壓縮後可以達到30K左右。

GZIP只能指定源檔案，目標檔案的擴展名由GZIP確定。壓縮檔案的屬性、時間等都保持不變。通常，新檔案的擴展名改為.GZ，但如果源檔案還有擴展名，則根據擴展名的長度確定。若擴展名有三個字元，則第三個字元用“Z”代替，否則擴展名加一字元“z”。對於Windows 95和Windows NT則是在檔案名稱後直接加.GZ，而不管被壓縮檔案有沒有擴展名。如果不喜歡使用GZIP的默認擴展名，也可自由定義。

GZIP最大的特點是高性能的壓縮以及自由使用，而且被GNUI程(開發linux系統的)所開發的系統列為標準壓縮程式。所以在網路上非常流行使用GZIP。

Haffman

Huffman方法是多媒體信息壓縮中經常採用的方法，它是一種不定常的熵編碼方法，當由字元集{c₁,c_2,..,c_n}構成的源信息中各字元出現頻率(機率)不均勻時具有很好的壓縮效果，我們希望，通過適當選擇不定常的代碼字，使平均碼長儘可能小。

為了用不定量的代碼字，同時又要避免解碼時的不確定性，可以採用由二元樹所定義的“前綴碼”，所謂前綴碼是一個代碼字的集合，其中任一個代碼字都不是另一個代碼字的前綴(即前面一部分，如10是101的前綴)，顯然，任一個二元樹，每一結點的左右邊分別賦標號值0，1，由於每個葉都有一條唯一的由根到葉的道路，從而對應一個由道路中各邊標號形成的二進制代碼字，顯然，這些代碼字構成前綴碼，反之，由一個前綴碼，也可以構造出相應的二元樹，因此，要找一個使平均碼長最小的的前綴碼，可以找一個二元樹，Halfman提出了一個根據頻率p₁,p_2,..,p_n找出一棵有n個葉的二元樹，其對應的前綴碼能使平均碼長最小。不過按原來的算法所得的二元樹不是唯一的，雖然它們彼此等價，即相應的前綴碼平均碼長是一樣的，為了消除不唯一性，便於程式實現和用圖來表示。

LZ77算法

LZ77(Lempel-Ziv-1977)是一個簡單但十分高效的數據壓縮算法，它與霍夫曼編碼的思想完全不同。LZ77算法是一種字典式編碼，由於所用的字典是由前面已處理過的一串字元所構成的，隨著編碼的進行，字典也不斷地滑動，故取名為滑動視窗編碼。文本視窗分成兩個部分，第一部分為搜尋快取區(Search Buffer)，用於存放部分最近已編碼的序列，即字典；第二部分為前視快取區(Look-ahead Buffer)，一般要小一些，用於存放剛被讀入但尚未編碼的字元。

LZ77通過用小的標記代替數據中多次重複出現的長串來方法來壓縮數據。與霍夫曼編碼不同的是，其處理的符號不一定是文本字元，可以是任何大小的符號，但其通常選擇一個位元組的符號。

LZ78算法

LZ78算法仍是基於字典的，與LZ77算法一樣，在壓縮編碼之初，所用的字典是空的，隨著編碼的進程，字典由已處理的文本逐步構成。但與LZ77算法的實現思路有本質的區別，LZ78算法放棄了視窗滑動的概念，採用樹形結構組織字典，保存短語。字典的大小沒有限制，凡是已出現過的短語都被收入在字典之中。編碼輸出的碼字由兩部分構成，即字典中短語的標號和緊跟在該短語之後的第一個字元的標號(或字元碼)。與LZ77不同，不給出匹配字元串的長度，其長度可由算法本身的規則來確定。

在實現LZ78算法時，字典的構建和維護十分重要。LZ78算法用一棵多叉樹存放字典，每個結點對應一個短語，即一串字元，並且被賦予一個固定的標號，碼樹的根結點是空字元(NULL)。LZ78算法開始壓縮時從NULL開始構造字典。每讀入源檔案的一個字元就與字典已存放的短語逐一比較，如果與某一條目匹配，繼續輸入下一個字元，直至找不到匹配的條目為止。這時將最後找到的也是最長的匹配字元串的標號和未匹配的字元作為輸入串的壓縮碼字輸出，同時將匹配字元串和緊隨其後不匹配的字元級聯，構成一個新的短語，加入到字典中。

PPM

部分匹配預測(predictionbypartialmatching，PPM)技術採用字元有限上下文模型。PPM依賴於前面編碼過的文本中已觀察到的上下文，採用不同的上下文長度，而不是把上下文長度嚴格地限制為一種來作出預測，“部分匹配”就由此得名了。

PPM是一種混合有限上下文統計建模技術，即混合使用若干固定階數的上下文模型來預測輸入序列中的下一個字元的機率，而這種預測是根據自適應更新的頻率計數實現的。該算法計算以前出現的上下文中信源符號發生的統計特性，然後用這些統計特性給序列中下一個位置上即將發生的符號分配碼字，並使碼字的平均長度最小。這就是說，給可能發生的符號要有比不太可能發生的符號分配更短的碼字。某一符號在不同上下文下發生的機率分別存儲，這樣在處理一個符號時由於上下文的變化使得分配給該符號的編碼有可能完全不同。

套用

文本壓縮技術因為有無損、通用的獨特優點，一部分算法還非常簡單、容易實現，並且資源開銷不大，所以得到了廣泛的套用。對它的套用主要體現在以下三個方面。

1．軟體上的套用

這是最活躍、最多樣化的一類套用。

在UNIX作業系統領域，最早的通用壓縮程式之一是COMPACT，但是它運行得太慢。後來有了比COMPACT運行更快、壓縮更好的COMPRESS。

上世紀80年代，通過SQ程式，數據壓縮首次進入了MS-DOS領域。後來ARC程式取而代之。ARC程式不但可以實現壓縮，還可以對檔案進行歸檔處理。接下來的有PKZIP、LHARC和ARJ等程式。以後發展出的程式一般都被廣泛移植到了各種作業系統和硬體平台上。

2．硬體上的套用

數據壓縮算法在硬體中實現具有高速的特點。LZW提出時就是被套用到磁碟的數據讀寫通道的硬體電路中的。而近來提出的新的數據壓縮算法，一般具有較高的複雜度，不少作者都提出了它的硬體實現方案，充分利用現代先進的半導體技術提高算法的運行速度。而不少工業廠商都致力於用硬體產品的形式提供它們的數據壓縮算法，例如IBM公司一直致力於開發ALDC系列高性能數據壓縮專用晶片。

3．通信的套用

在數據傳輸之前先進行無損的壓縮可以有效地節約通信頻寬，加快傳輸速度。當然，能夠這樣做的前提是通信雙方的壓縮、解壓縮算法必須相互成一對，因為這樣才能保證實現正確的還原。美國的Stac電子公司用專用晶片實現的基於LZ77的壓縮算法被“1/4英寸盒式磁帶(Quarter Inch Cartridge)工業集團”接受為工業標準，得到了廣泛的套用。