文件壓縮原理

這段話有17個單詞，包含61個字母、16個空格、1個破折號和1個句點。如果每個字母、空格或標點都占用1個內存單元，那么文件的總大小為79個單元。為了減小文件的大小，我們需要找出冗余的部分。

我們立刻發(fā)現(xiàn)：

如果忽略大小寫字母間的區(qū)別，這個句子幾乎有一半是冗余的。九個單詞（ask、not、what、your、country、can、do、for、you）幾乎提供了組成整句話所需的所有東西。為了構造出另一半句子，我們只需要拿出前半段句子中的單詞，然后加上空格和標點就行了。

大多數(shù)壓縮程序使用基于自適應字典的LZ算法來縮小文件?！癓Z”指的是此算法的發(fā)明者Lempel和Ziv，“字典”指的是對數(shù)據(jù)塊進行歸類的方法。

排列字典的機制有很多種，它也可以像編號列表那樣簡單。在我們檢查肯尼迪這句著名講話時，可以挑出重復的單詞，并將它們放到編號索引中。然后，我們直接寫入編號而不是寫入整個單詞。

因此，如果我們的字典是：

ask
what
your
country
can
do
for
you

我們的句子現(xiàn)在就應該是這樣的：

1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4

如果您了解這種機制，那么只需使用該字典和編號模式即可輕松重新構造出原始句子。這就是在展開某個下載文件時，計算機中的解壓縮程序所做的工作。你可能還遇到過能夠自行解壓縮的壓縮文件。若要創(chuàng)建這種文件，編程人員需要在被壓縮的文件中設置一個簡單的解壓縮程序。在下載完畢后，它可以自動重新構造出原始文件。

但是使用這種機制究竟能夠節(jié)省多少空間呢？“1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”當然短于“Ask not what your country can do for you-- ask what you can do for your country.”，但應注意的是，我們需要隨文件一起保存這個字典。

在實際壓縮方案中，計算出各種文件需求是一個相當復雜的過程。讓我們回過頭考慮一下上面的例子。每個字符和空格都占用1個內存單元，整個原句要占用79個單元。壓縮后的句子（包括空格）占用了37個單元，而字典（單詞和編號）也占用了37個單元。也就是說，文件的大小為74個單元，因此我們并沒有把文件大小減少很多。

但這只是一個句子的情況！可以想象的是，如果用該壓縮程序處理完肯尼迪講話的其余部分，我們會發(fā)現(xiàn)這些單詞以及其他單詞重復了更多次。而且，正如下一節(jié)所言，為了得到盡可能高的組織效率，可以對字典進行重寫。

壓縮程序

在上一頁的例子中，我們挑出了所有重復的單詞并將它們放在一個字典中。對于我們來說，這是最顯而易見的字典編寫方法。但是壓縮程序卻不這樣認為：它對單詞沒有概念——它只會尋找各個模式。為了盡可能減小文件的大小，它會仔細挑選出最優(yōu)模式。

如果從這個角度處理該句子，我們最終會得到一個完全不同的字典。

如果壓縮程序掃描肯尼迪的這句話，它遇到的第一個冗余部分只有幾個字母長。在ask not what your中，出現(xiàn)了一個重復的模式，即字母t后面跟一個空格——在not和what中。如果壓縮程序將此模式寫入字典，則每次出現(xiàn)“ｔ”后面跟一個空格的情況時，它會寫入一個“１”。但是在這個短句中，此模式的出現(xiàn)次數(shù)不夠多，不足以將其保留為字典中的一個條目，因此程序最終會覆蓋它。

程序接下來注意到的內容是ou，在your和country中都出現(xiàn)了它。如果這是一篇較長的文檔，將此模式寫入字典會節(jié)省大量空間——在英語中ou是一個十分常見的字母組合。但是在壓縮程序看完整個句子后，它立即發(fā)現(xiàn)了一個更好的字典條目選擇：不僅ou發(fā)生了重復，而且your和country整個單詞都發(fā)生了重復，并且它們實際上是作為一個短語your country一起發(fā)生重復的。在本例中，程序會用your country條目覆蓋掉字典中的ou條目。

短語can do for也發(fā)生了重復，一次后面跟著your，另一次跟著you，因此我們又發(fā)現(xiàn)can do for you也是一種重復模式。這樣，我們可以用一個數(shù)字來代替15個字符（包含空格），而your country只允許我們用一個數(shù)字代替13個字符（包含空格），所以程序會用r country條目覆蓋your country條目，然后再寫入一個單獨的can do for you條目。程序通過這種方式繼續(xù)工作，挑出所有重復的信息，然后計算應該將哪一種模式寫入字典?；谧赃m應字典的LZ算法中的“自適應”部分指的就是這種重寫字典的能力。程序執(zhí)行此工作的過程實際上非常復雜，您可以參考Data-Compression.com上的討論來了解更多信息。

無論使用什么方法，這種深入搜索機制都能比僅僅挑出單詞這種方法更有效率地對文件進行壓縮。如果使用我們上面提取出的模式，然后用“__”代替空格，最終將得到下面這個更大的字典：

ask__
what__-
you
r__country
__can__do__for__you

而句子則較短：

“1not__2345__--__12354”

句子現(xiàn)在占用18個內存單元，字典占用41個單元。所以，我們將文件總大小從79個單元壓縮到了59個單元！這僅僅是壓縮句子的一種方法，而且不一定是最高效的方法。（看看您能找到更好的方法嗎?。?/P>

那么這種機制到底有多好呢？文件壓縮率取決于多種因素，包括文件類型、文件大小和壓縮方案。

在世界上的大多數(shù)語言中，某些字母和單詞經常以相同的模式一起出現(xiàn)。正是由于這種高冗余性，而導致文本文件的壓縮率會很高。通常大小合適的文本文件的壓縮率可以達到50%或更高。大多數(shù)編程語言的冗余度也很高，因為它們的命令相對較少，并且命令經常采用一種設定的模式。對于包含大量不重復信息的文件（例如圖像或MP3文件），則不能使用這種機制來獲得很高的壓縮率，因為它們不包含重復多次的模式。

如果文件有大量重復模式，那么壓縮率通常會隨著文件大小的增加而增加。從我們的例子中就可以看出這一點——如果我們摘錄的肯尼迪講話再長一些，您會發(fā)現(xiàn)又多次出現(xiàn)了我們字典中的模式，因此能夠通過每個字典條目節(jié)省更多的文件空間。此外，對于更大的文件，還可能出現(xiàn)具有更大普遍性的模式，從而能夠創(chuàng)建出效率更高的字典。

此外，文件壓縮效率還取決于壓縮程序使用的具體算法。有些程序能夠在某些類型的文件中更好地尋找到模式，因此能更有效地壓縮這些類型的文件。其他一些壓縮程序在字典中又使用了字典，這使它們在壓縮大文件時表現(xiàn)很好，但是在壓縮較小的文件時效率不高。盡管這一類的所有壓縮程序都基于同一個基本理念，但是它們的執(zhí)行方式卻各不相同。程序開發(fā)人員始終在嘗試建立更好的壓縮機制。

有損壓縮和無損壓縮

我們在上文中討論的壓縮類型稱為無損壓縮，因為您重新創(chuàng)建的文件與原始文件完全相同。所有無損壓縮都基于這樣一種理念：將文件變?yōu)椤拜^小”的形式以利于傳輸或存儲，并在另一方收到它后復原以便重新使用它。

有損壓縮則與此大不相同。這些程序直接去除“不必要”的信息，對文件進行剪裁以使它變得更小。這種類型的壓縮大量應用于減小位圖圖像的文件大小，因為位圖圖像的體積通常非常龐大。為了了解有損壓縮的工作原理，讓我們看看你的計算機如何對一張掃描的照片進行壓縮。

對于此類文件，無損壓縮程序的壓縮率通常不高。盡管圖片的大部分看起來都是相同的——例如，整個天空都是藍色的——但是大部分像素之間都存在微小的差異。為了使圖片變得更小同時不降低其分辨率，您必須更改某些像素的顏色值。如果圖片中包含大量的藍色天空，程序會挑選一種能夠用于所有像素的藍色。然后，程序重寫該文件，所有天空像素的值都使用此信息。如果壓縮方案選擇得當，您不會注意到任何變化，但是文件大小會顯著減小。

當然，對于有損壓縮，在文件壓縮后您無法將其復原成原始文件的樣子。您必須接受壓縮程序對原始文件的重新解釋。因此，如果需要完全重現(xiàn)原來的內容（例如軟件應用程序、數(shù)據(jù)庫和總統(tǒng)就職演說），則不應該使用這種壓縮形式。