壓縮前綴樹

㈠ 深入理解gzip原理

gzip 使用deflate演算法進行壓縮。gzip 對於要壓縮的文件，首先使用LZ77演算法的一個變種進行壓縮，對得到的結果再使用Huffman編碼的方法

如果文件中有兩塊內容相同的話，那麼只要知道前一塊的位置和大小，我們就可以確定後一塊的內容。所以我們可以用（兩者之間的距離，相同內容的長度）這樣一對信息，來替換後一塊內容。由於（兩者之間的距離，相同內容的長度）這一對信息的大小，小於被替換內容的大小，所以文件得到了壓縮。

舉一個例子

有一個文件的內容如下
http://jiurl.yeah.net http://jiurl.nease.net

其中有些部分的內容，前面已經出現過了，下面用()括起來的部分就是相同的部分。
http://jiurl.yeah.net ( http://jiurl.)nease(.net )
我們使用 (兩者之間的距離，相同內容的長度) 這樣一對信息，來替換後一塊內容。（22,13)中，22為相同內容塊與當前位置之間的距離，13為相同內容的長度。(23,4)中，23為相同內容塊與當前位置之間的距離，4為相同內容的長度。由於（兩者之間的距離，相同內容的長度）這一對信息的大小，小於被替換內容的大小，所以文件得到了壓縮。

LZ77演算法使用"滑動窗口"的方法，來尋找文件中的相同部分，也就是匹配串.

解壓縮：
從文件開始到文件結束，每次先讀一位標志位，通過這個標志位來判斷下面是一個(之間的距離，匹配長度) 對，還是一個沒有改動的位元組。如果是一個（之間的距離，匹配長度）對，就讀出固定位數的（之間的距離，匹配長度）對，然後根據對中的信息，將匹配串輸出到當前位置。如果是一個沒有改動的位元組，就讀出一個位元組，然後輸出這個位元組。

LZ77壓縮時需要做大量的匹配工作，而解壓縮時需要做的工作很少，也就是說解壓縮相對於壓縮將快的多。這對於需要進行一次壓縮，多次解壓縮的情況，是一個巨大的優點。

深入理解
要理解這種演算法，我們先了解3個關鍵詞:短語字典，滑動窗口和向前緩沖區。
前向緩沖區
每次讀取數據的時候，先把一部分數據預載入前向緩沖區。為移入滑動窗口做准備
滑動窗口
一旦數據通過緩沖區，那麼它將移動到滑動窗口中，並變成字典的一部分。

短語字典
從字元序列S1...Sn，組成n個短語。比如字元(A,B,D) ,可以組合的短語為{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果這些字元在滑動窗口裡面，就可以記為當前的短語字典，因為滑動窗口不斷的向前滑動，所以短語字典也是不斷的變化。

LZ77的主要演算法邏輯就是，先通過前向緩沖區預讀數據，然後再向滑動窗口移入（滑動窗口有一定的長度），不斷的尋找能與字典中短語匹配的最長短語，然後通過標記符標記。

當壓縮數據的時候，前向緩沖區與移動窗口之間在做短語匹配的是後會存在2種情況:

短語標記包含三部分信息：（滑動窗口中的偏移量（從匹配開始的地方計算）、匹配中的符號個數、匹配結束後的前向緩沖區中的第一個符號）。

我們採用圖例來看:

1、開始

2、滑動窗口中沒有數據，所以沒有匹配到短語，將字元A標記為A

3、滑動窗口中有A,沒有從緩沖區中字元（BABC）中匹配到短語，依然把B標記為B

4、緩沖區字元（ABCB）在滑動窗口的位移6位置找到AB,成功匹配到短語AB,將AB編碼為(6,2,C)

5、緩沖區字元（BABA）在滑動窗口位移4的位置匹配到短語BAB,將BAB編碼為(4,3,A)

6、緩沖區字元（BCAD）在滑動窗口位移2的位置匹配到短語BC，將BC編碼為（2,2,A）

7、緩沖區字元D,在滑動窗口中沒有找到匹配短語，標記為D

8、緩沖區中沒有數據進入了，結束

解壓類似於壓縮的逆向過程，通過解碼標記和保持滑動窗口中的符號來更新解壓數據。

我們還是採用圖例來看下:
1、開始

2、符號標記A解碼

3、符號標記B解碼

4、短語標記(6,2,C)解碼

5、短語標記(4,3,A)解碼

6、短語標記(2,2,A)解碼

7、符號標記D解碼

大多數情況下LZ77壓縮演算法的壓縮比相當高，當然了也和你選擇滑動窗口大小，以及前向緩沖區大小有關系。其壓縮過程是比較耗時的，因為要花費很多時間尋找滑動窗口中的短語匹配，不過解壓過程會很快，因為每個標記都明確告知在哪個位置可以讀取了。

哈夫曼樹也叫最優二叉樹（哈夫曼樹）

問題：什麼是哈夫曼樹？

例：將學生的百分製成績轉換為五分製成績：≥90 分: A，80～89分: B，70～79分: C，60～69分: D，＜60分: E。

判別樹：用於描述分類過程的二叉樹。

如果每次輸入量都很大，那麼應該考慮程序運行的時間

如果學生的總成績數據有10000條，則5％的數據需 1 次比較，15％的數據需 2 次比較，40％的數據需 3 次比較，40％的數據需 4 次比較，因此 10000 個數據比較的

次數為： 10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次

此種形狀的二叉樹，需要的比較次數是：10000 (3×20％＋2×80％)＝22000次，顯然：兩種判別樹的效率是不一樣的。

問題：能不能找到一種效率最高的判別樹呢?

那就是哈夫曼樹

樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，通常記作：

其中，n表示葉子結點的數目，wi和li分別表示葉子結點ki的權值和樹根結點到葉子結點ki之間的路徑長度。
赫夫曼樹（哈夫曼樹，huffman樹）定義：
在權為w1,w2,…,wn的n個葉子結點的所有二叉樹中，帶權路徑長度WPL最小的二叉樹稱為赫夫曼樹或最優二叉樹。

例：有4 個結點 a, b, c, d，權值分別為 7, 5, 2, 4，試構造以此 4 個結點為葉子結點的二叉樹。

WPL=7´2+5´2+2´2+4´2= 36

WPL=7´3+5´3+2´1+4´2= 46

哈夫曼樹的構造(哈夫曼演算法)
1.根據給定的n個權值{w1,w2,…,wn}構成二叉樹集合F={T1,T2,…,Tn},其中每棵二叉樹Ti中只有一個帶權為wi的根結點,其左右子樹為空.
2.在F中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹,且置新的二叉樹的根結點的權值為左右子樹根結點的權值之和.
3.在F中刪除這兩棵樹,同時將新的二叉樹加入F中.
4.重復2、3,直到F只含有一棵樹為止.(得到哈夫曼樹)

哈夫曼樹的應用很廣，哈夫曼編碼就是其在電訊通信中的應用之一。廣泛地用於數據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。在電訊通信業務中，通常用二進制編碼來表示字母或其他字元，並用這樣的編碼來表示字元序列。

例：如果需傳送的電文為 『ABACCDA』，它只用到四種字元，用兩位二進制編碼便可分辨。假設 A, B, C, D 的編碼分別為 00, 01,10, 11，則上述電文便為 『00010010101100』（共 14 位），解碼員按兩位進行分組解碼，便可恢復原來的電文。

能否使編碼總長度更短呢？

實際應用中各字元的出現頻度不相同，用短（長）編碼表示頻率大（小）的字元，使得編碼序列的總長度最小，使所需總空間量最少

數據的最小冗餘編碼問題

在上例中，若假設 A, B, C, D 的編碼分別為 0，00，1，01，則電文 『ABACCDA』 便為 『000011010』（共 9 位），但此編碼存在多義性：可譯為： 『BBCCDA』、『ABACCDA』、『AAAACCACA』 等。

解碼的惟一性問題

要求任一字元的編碼都不能是另一字元編碼的前綴，這種編碼稱為前綴編碼（其實是非前綴碼）。 在編碼過程要考慮兩個問題，數據的最小冗餘編碼問題，解碼的惟一性問題，利用最優二叉樹可以很好地解決上述兩個問題

以電文中的字元作為葉子結點構造二叉樹。然後將二叉樹中結點引向其左孩子的分支標 『0』，引向其右孩子的分支標 『1』； 每個字元的編碼即為從根到每個葉子的路徑上得到的 0, 1 序列。如此得到的即為二進制前綴編碼。

編碼： A：0， C：10，B：110，D：111

任意一個葉子結點都不可能在其它葉子結點的路徑中。

用哈夫曼樹設計總長最短的二進制前綴編碼

例：如果需傳送的電文為 『ABACCDA』，即：A, B, C, D 的頻率（即權值）分別為 0.43, 0.14, 0.29, 0.14，試構造哈夫曼編碼。

編碼： A：0， C：10， B：110， D：111 。電文 『ABACCDA』 便為 『0110010101110』（共 13 位）。

解碼
從哈夫曼樹根開始，對待解碼電文逐位取碼。若編碼是「0」，則向左走；若編碼是「1」，則向右走，一旦到達葉子結點，則譯出一個字元；再重新從根出發，直到電文結束。

電文為 「1101000」 ，譯文只能是「CAT」

㈡ 數據流壓縮原理和數據壓縮Zlib的實現

壓縮的本質就是去冗餘，去除信息冗餘，使用最短的編碼保存最完整的數據信息。所以對於不同的場景，壓縮採用的演算法也因時制宜，比如視頻和圖片可以採用有損壓縮，而文本數據採用無損壓縮。壓縮率又取決於信息的冗餘度，也就是內容中重復的比例。那些均勻分布的隨機字元串，壓縮率會降到最低，即香農限

deflate是zip文件的默認演算法。它更是一種數據流壓縮演算法。

LZ77壓縮演算法採用字典的方式進行壓縮，是一種簡單但是很高效的數據壓縮演算法。其方式就是把數據中一些可以組織成短語的字元加入字典。維護三個概念： 短語字典、滑動窗口、向前緩沖區

壓縮的逆過程，通過解碼標記和保持滑動窗口中的符號來更新解壓數據。當解碼字元被標記:將標記編碼成字元拷貝到滑動窗口中，一步一步直到全部翻譯完成

在流式傳輸中，不定長編碼數據的解碼想要保持唯一性，必須滿足唯一可以碼的條件。而異前綴碼就是一種唯一可解碼的候選，當然這樣會增加編碼的長度，卻可以簡化解碼。

huffman編碼是一種基於概率分布的貪心策略最優前綴碼。huffman編碼可以有效的壓縮數據，壓縮率取決於數據本身的信息冗餘度

計算數據中各符號出現的概率，根據概率從小到大，從下往上反向構建構造碼樹，這樣最終得到的編碼的平均長度是最短的。同時也是唯一可譯的

解讀：在一開始，每一個字元已經按照出現概率的大小排好順序，在後續的步驟中，每一次將概率最低的兩棵樹合並，然後用合並後的結果再次排序（為了找出最小的兩棵樹）。在gzip源碼中並沒有專門去排序，而是使用專門的數據結構（比如最小堆或者紅黑樹）。

使用優先隊列實現huffman樹，最後基於Huffman樹最終實現文件壓縮。
具體步驟：

gzip = gzip 頭 + deflate 編碼的實際內容 + gzip 尾

zlib = zlib 頭 + deflate 編碼的實際內容 + zlib 尾

壓縮之前：初始化各種輸入輸出緩沖區；
壓縮：我們可以不斷往這些緩沖區中填充內容，然後由deflate函數進行壓縮或者indeflate函數進行解壓

總結：在調用deflate函數之前，應用程序必須保證至少一個動作被執行（avail_in或者avail_out被設置），用提供更多數據或者消耗更多的數據的方式。avail_out在函數調用之前千萬不能為零。應用程序可以隨時消耗被壓縮的輸出數據

㈢ tar壓縮文件，如何加一個前綴的目錄

各位請教LINUX何tar壓縮文件解壓指定目錄直接用tar xvf 解壓放前目錄放指定目錄應該用哪參數請舉例謝謝
tar xvf te.tar ./test/ -C
或
tar xvf te.tar -C ./test/
都起作用
ls -l te.tar顯示

使用
tar -xvf te.tar test/
tar xvf te.tar test/
tar -xvf te.tar ./test/
tar xvf te.tar ./test/
都行啊solaris 9

答試行：
tar -xvf xx.tar 目標目錄/ -號加再試試
tar -xvf /home/zjx/aa.tar -C ./test/我試
tar -xvf a.tar -C ./test/ 絕

請指教謝謝

㈣ python壓縮存儲

美國 國務卿 柯林頓 。 <> 美國（國務卿（希拉里 （競選 （總統））（就職）（。））））

這行壓縮後的 柯林頓 不要了？

你只給可能數據，目前能做到這樣子了（pyton3.3腳本）