哈夫曼解壓演算法
注:哈夫曼和lzss演算法不是同一種演算法,先用哈夫曼再用lzss演算法壓縮後會發現經哈夫曼壓縮後再用lzss壓縮文件會變大,具體原因不明
lzss原理:
把編碼位置置於輸入數據流的開始位置。
在前向緩沖器中查找窗口中最長的匹配串
①
pointer
：=匹配串指針。
②
length
：=匹配串長度。
判斷匹配串長度length是否大於等於最小匹配串長度(min_length)
，
如果「是」：輸出指針，然後把編碼位置向前移動length個字元。
如果「否」：輸出前向緩沖存儲器中的第1個字元，然後把編碼位置向前移動一個字元。
如果前向緩沖器不是空的，就返回到步驟2。
例：編碼字元串如表03-05-3所示，編碼過程如表03-05-4所示。現說明如下：
「步驟」欄表示編碼步驟。
「位置」欄表示編碼位置，輸入數據流中的第1個字元為編碼位置1。
「匹配」欄表示窗口中找到的最長的匹配串。
「字元」欄表示匹配之後在前向緩沖存儲器中的第1個字元。
「輸出」欄的輸出為：
①
如果匹配串本身的長度length
>=
min_length，輸出指向匹配串的指針，格式為(back_chars，
chars_length)。該指針告訴解碼器「在這個窗口中向後退back_chars個字元然後拷貝chars_length個字元到輸出」。
②
如果匹配串本身的長度length
>=
min_length，則輸出真實的匹配串。
表:輸入數據流
位置
1234567891011
字元
aabbcbbaabc
表:編碼過程(min_length
=
2)
步驟位置匹配串輸出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc
『貳』 壓縮演算法原理
哈夫曼
哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。
哈夫曼演算法在改變任何符號二進制編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重復或序號的序列。
2.1 原理
我不打算探究哈夫曼編碼的所有實際的細節，但基本的原理是為每個符號找到新的二進製表示，從而通常符號使用很少的位，不常見的符號使用較多的位。
簡短的說，這個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數據的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是 ∑ N K =1 符號數 k , N 是分之中符號的數量，符號數 k 是符號 k出現的次數 ）
這棵樹有兩個目的：
1． 編碼器使用這棵樹來找到每個符號最優的表示方法
2． 解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數據位的時候自頂向底的遍歷樹，選擇基於數據流中的每個獨立位的分支，一旦一個到達葉子節點，解碼器知道一個完整的編碼已經讀出來了。
壓縮後的數據流是 24 位（三個位元組），原來是 80 位（ 10 個位元組）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對於大數據量來說，上面的哈夫曼樹就不佔太多比例了。
解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左 / 右分支，每次碰到一個葉子節點的時候，就可以將對應的位元組寫到解壓輸出流中，然後再從根開始遍歷。
2.2 實現
哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實現。
這個實現的基本缺陷是：
1． 慢位流實現
2． 相當慢的解碼（比編碼慢）
3． 最大的樹深度是 32 （編碼器在任何超過 32 位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數據大於 2 32位元組。
另一方面，這個實現有幾個優點：
1． 哈夫曼樹以一個緊密的形式每個符號要求 12 位（對於 8 位的符號）的方式存儲，這意味著最大的頭為 384 。
2． 編碼相當容易理解
哈夫曼編碼在數據有噪音的情況（不是有規律的，例如 RLE ）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。
『叄』 用huffman演算法實現「文件的壓縮與解壓」怎麼做啊
我寫過一個Huffman編碼，但只是生成了編碼表，沒做成壓縮，但可以利用查表做成文件壓縮，另外用的是C++，改成C的話比較容易，只要把動下內存分配就行了，想要的話,msn:[email protected]
『肆』 如何寫壓縮軟體，運用哈夫曼演算法實現
到文件壓縮大家很容易想到的就是rar,zip等我們常見的壓縮格式。然而，還有一種就是大家在學習數據結構最常見到的哈夫曼樹的數據結構，以前還不知道他又什麼用，其實他最大的用途就是用來做壓縮，也是一些rar,zip壓縮的祖先，稱為哈弗曼壓縮（什麼你不知道誰是哈弗曼，也不知道哈弗曼壓縮，不急等下介紹）。
隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。
特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。
一、什麼是哈弗曼壓縮
Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。
二、怎麼實現哈弗曼壓縮
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。
故我們得了解幾個概念：
1、二叉樹：在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。2、哈夫曼編碼(Huffman Coding)：是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。uffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。三、哈夫曼編碼生成步驟：
①掃描要壓縮的文件，對字元出現的頻率進行計算。
②把字元按出現的頻率進行排序，組成一個隊列。
③把出現頻率最低（權值）的兩個字元作為葉子節點，它們的權值之和為根節點組成一棵樹。
④把上面葉子節點的兩個字元從隊列中移除，並把它們組成的根節點加入到隊列。
⑤把隊列重新進行排序。重復步驟③④⑤直到隊列中只有一個節點為止。
⑥把這棵樹上的根節點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節點的哈夫曼編碼了。
既如 (a)、(b)、(c)、(d)幾個圖，就可以將離散型的數據轉化為樹型的了。
如果假設樹的左邊用0表示右邊用1表示，則每一個數可以用一個01串表示出來。
則可以得到對應的編碼如下：
1-->110
2-->111
3-->10
4-->0
每一個01串，既為每一個數字的哈弗曼編碼。
為什麼能壓縮：
壓縮的時候當我們遇到了文本中的1、2、3、4幾個字元的時候，我們不用原來的存儲，而是轉化為用它們的01串來存儲不久是能減小了空間佔用了嗎。（什麼01串不是比原來的字元還多了嗎？怎麼減少？）大家應該知道的，計算機中我們存儲一個int型數據的時候一般式佔用了2^32-1個01位，因為計算機中所有的數據都是最後轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有0和1嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。
比如：
1這個數字，用整數寫進計算機硬碟去存儲，佔用了2^32-1個二進制位
而如果用它的哈弗曼編碼去存儲，只有110三個二進制位。
效果顯而易見。
『伍』 求助：用java實現哈夫曼編碼壓縮與解壓縮演算法。
你好，由於內容比較多，先概述一下先。如圖所示，為我寫的一個壓縮軟體，原理是利用哈弗曼演算法實現的。我將資料整理好稍後就發到你郵箱，但在這里簡要說明一下代碼。
請看我的空間
http://hi..com/%D2%B6%BF%C6%C1%BC/blog
中的文章共5篇（太長了）
http://hi..com/%D2%B6%BF%C6%C1%BC/blog/item/93c35517bb528146f2de32fd.html
1.HuffmanTextEncoder類完成壓縮功能，可直接運行，壓縮測試用文本文件。
2.HuffmanTextDecoder類完成解壓縮功能，可直接運行，解壓縮壓縮後的文本文件。
3.BitReader,工具類，實現對BufferedInputStream的按位讀取。
4.BitWriter,工具類，實現按位寫入的功能。該類來自網路。
5.MinHeap<T>,模板工具類，實現了一個最小堆。生成Huffman樹時使用。
