/Files/dvb-dvb/HuffmanCode.rar這個是最新的huffman code (encoder and decoder) , 但是效率有待提升.
一直占cpu 50% , 掃描兩遍文件,一遍建立huffman code,另一遍,用二進制替換,
1,有兩個問題沒有解決
1,動態(tài)建立huffman tree node value.僅僅掃描一遍,
2,根據(jù)node的值去排序得到frequence時,這個值到底取1個byte,還是2個byte.
Huffman算法簡介
Huffman算法是一種基于統(tǒng)計的壓縮方法。它的本質(zhì)就是對文本文件中的字符進行重新編碼，對于使用頻率越高的字符，其編碼也越短。但是任何2個字符的編碼，是不能出現(xiàn)向前包含的。也就是說字符A的編碼的前段，不可能為字符B的編碼。經(jīng)過編碼后的文本文件，主要包含2個部分：Huffman碼表部分和壓縮內(nèi)容部分。解壓縮的時候，先把Huffman碼表取出來，然后對壓縮內(nèi)容部分各個字符進行逐一解碼,形成源文件。
由此可見，使用Huffman算法的關(guān)鍵是形成Huffman碼表。怎樣才能生成一個“使用頻率越高的字符，其編碼也越短”的碼表呢?這里就要用到 Huffman樹的數(shù)據(jù)結(jié)構(gòu)。當把一棵Huffman樹生成后，碼表也就生成了。以下舉例說明，假定我們的原始文本為"abcbbcccc"
Huffman樹生成步驟:
1.掃描源文件，對字符頻率進行統(tǒng)計。
對于我們的樣例，統(tǒng)計結(jié)果是:a:1 b:3 c:5 (按頻率升序排列)
2.從上述隊列中取出頻率最低的2個節(jié)點，合并成一個頻率為2節(jié)點頻率之和的樹枝節(jié)點X，加入到原隊列中，加入后，繼續(xù)保持隊列按頻率升序排列.
3.重復(fù)步驟2，直到隊列中只有一個節(jié)點。
4.這樣，我們就形成了一棵Huffman樹。葉子節(jié)點為字符，從樹根節(jié)點到葉子節(jié)點的路徑即為該字符的Huffman編碼。從一個節(jié)點導航到其左孩子，該段路徑為0，導航到右孩子，該段路徑為1.所以，a字符的編碼就是00,b字符的編碼為01,c字符的編碼為1，符合"使用頻率越高的字符，編碼越短"的要求。理論論證過程見<算法導論>P233
5.Huffman碼表生成后，原文本"abcbbcccc"就變成了0001101011111的位串，按每個字符占用2個byte計算，大小由原來的18個字節(jié)(9*2),共144個bit,變成了13個bit,2個字節(jié)。達到了壓縮的目的。
解壓縮過程:
解壓縮也分成2部分進行，首先是根據(jù)壓縮文件中的Huffman碼表，在內(nèi)存中生成一棵Huffman樹，然后，根據(jù)Huffman樹，對壓縮內(nèi)容進行解壓縮。比如如果壓縮內(nèi)容為位串0001101011111，那么從樹根節(jié)點起，因為第一個bit為0，先轉(zhuǎn)向左子樹，第二個bit為0,再轉(zhuǎn)向左子樹,到達葉子a,所以解碼出來的第一個字符就是a,每次解壓一個字符，都從根節(jié)點起，根據(jù)bit流，向左或向右轉(zhuǎn)，直到到達葉子節(jié)點，也就是解壓出來的字符。一直重復(fù)此過程，直到所有的字符都被解壓縮。
壓縮文件格式
使用Huffman壓縮算法對文本文件壓縮后，就形成了一個壓縮文件，該壓縮文件包含2部分，一部分為Huffman碼表，也就是Huffman 樹，第二部分為根據(jù)碼表生成的內(nèi)容位串。如何設(shè)計Huffman樹的存儲格式呢?本文采用從上到下，從左到右分層遍歷節(jié)點，順序存儲的方式。如下圖:
也就是說，對于前述的Huffman樹，其持久化形式為:0xfffe 0xfffe 0x0063 0x0061 0x0062,其中0xfffe代表樹枝節(jié)點,而0x0061,0x0062,0x0063分別為a,b,c的Unicode碼。因為所有的樹枝節(jié)點的值都是0xfffe，所有樹枝節(jié)點都有2個孩子，節(jié)點排列方式是按從上到下，從左到右分層排列，所以能根據(jù)此持久化字節(jié)數(shù)組，把Huffman樹在內(nèi)存中重新生成。
另外為了升級版本，嵌入了magic number和version。
完整工程下載
本文涉及到的完整的eclipse工程，可以從這里下載。注:內(nèi)含測試樣例《平凡的世界》文本文件，體積較大，請使用下載工具下載。另外，本程序中采用了泛型，請在至少在JDK1.5版本上編譯運行。
代碼簡要說明
1.HuffmanTextEncoder類完成壓縮功能，可直接運行，壓縮測試用文本文件。
2.HuffmanTextDecoder類完成解壓縮功能，可直接運行，解壓縮 壓縮后的文本文件。
3.BitReader,工具類，實現(xiàn)對BufferedInputStream的按位讀取。
4.BitWriter,工具類，實現(xiàn)按位寫入的功能。該類來自網(wǎng)絡(luò)。
5.MinHeap<T> ,模板工具類，實現(xiàn)了一個最小堆。生成Huffman樹時使用。
壓縮效果
使用本程序?qū)Α镀椒驳氖澜纭纷鰤嚎s測試，壓縮前為文本文件，大小為1.7M,壓縮后為二進制文件，大小接近1M（988,817byte）,而 zip壓縮后體積為920,997byte,比zip差，壓縮文件存儲格式待改善。另外，因為從Huffman壓縮算法的原理可知，該算法對字符重復(fù)率高的文本最有效，比如長篇小說或者英文小說。
以上內(nèi)容為轉(zhuǎn)載:
http://chencwf.googlepages.com/huffman
以下為自己的內(nèi)容:
DETAIL: 35:v:2f,p: 42.
INFO: Sort After.size = 0
DETAIL: 0:v:fffe,p:228,xx= 0,yy= 0.
DETAIL: 1:v:fffe,p: 92,xx= 1,yy= 0.0
DETAIL: 2:v:fffe,p: 42,xx= 2,yy= 0.00
DETAIL: 3:v:fffe,p: 19,xx= 3,yy= 0.000
DETAIL: 4:v:fffe,p: 9,xx= 4,yy= 0.0000
DETAIL: 5:v:fffe,p: 4,xx= 5,yy= 0.00000
DETAIL: 6:v:fffe,p: 2,xx= 6,yy= 0.000000
DETAIL: 7:v: 53,p: 1,xx= 7,yy= 0.0000000
DETAIL: 8:v: 47,p: 1,xx= 7,yy= 1.0000001
DETAIL: 9:v:fffe,p: 2,xx= 6,yy= 1.000001
DETAIL: 10:v: 3d,p: 1,xx= 7,yy= 2.0000010
DETAIL: 11:v: 3b,p: 1,xx= 7,yy= 3.0000011
DETAIL: 12:v: 6c,p: 5,xx= 5,yy= 1.00001
DETAIL: 13:v: 65,p: 10,xx= 4,yy= 1.0001
DETAIL: 14:v:fffe,p: 23,xx= 3,yy= 1.001
DETAIL: 15:v: 74,p: 11,xx= 4,yy= 2.0010
DETAIL: 16:v: d,p: 12,xx= 4,yy= 3.0011
DETAIL: 17:v:fffe,p: 50,xx= 2,yy= 1.01
DETAIL: 18:v:fffe,p: 24,xx= 3,yy= 2.010
DETAIL: 19:v:fffe,p: 12,xx= 4,yy= 4.0100
DETAIL: 20:v:fffe,p: 6,xx= 5,yy= 4.01000
DETAIL: 21:v: 66,p: 3,xx= 6,yy= 4.010000
DETAIL: 22:v: 67,p: 3,xx= 6,yy= 5.010001
DETAIL: 23:v: 63,p: 6,xx= 5,yy= 5.01001
DETAIL: 24:v: a,p: 12,xx= 4,yy= 5.0101
DETAIL: 25:v: 20,p: 26,xx= 3,yy= 3.011
DETAIL: 26:v:fffe,p:136,xx= 1,yy= 1.1
DETAIL: 27:v:fffe,p: 58,xx= 2,yy= 2.10
DETAIL: 28:v:fffe,p: 26,xx= 3,yy= 4.100
DETAIL: 29:v:fffe,p: 12,xx= 4,yy= 6.1000
DETAIL: 30:v:fffe,p: 6,xx= 5,yy= 6.10000
DETAIL: 31:v:fffe,p: 3,xx= 6,yy= 6.100000
DETAIL: 32:v: 7b,p: 1,xx= 7,yy= 6.1000000
DETAIL: 33:v: 70,p: 2,xx= 7,yy= 7.1000001
DETAIL: 34:v: 78,p: 3,xx= 6,yy= 7.100001
DETAIL: 35:v:fffe,p: 6,xx= 5,yy= 7.10001
DETAIL: 36:v: 61,p: 3,xx= 6,yy= 8.100010
DETAIL: 37:v: 4c,p: 3,xx= 6,yy= 9.100011
DETAIL: 38:v:fffe,p: 14,xx= 4,yy= 7.1001
DETAIL: 39:v: 64,p: 7,xx= 5,yy= 8.10010
DETAIL: 40:v: 9,p: 7,xx= 5,yy= 9.10011
DETAIL: 41:v:fffe,p: 32,xx= 3,yy= 5.101
DETAIL: 42:v:fffe,p: 16,xx= 4,yy= 8.1010
DETAIL: 43:v:fffe,p: 8,xx= 5,yy= 10.10100
DETAIL: 44:v:fffe,p: 4,xx= 6,yy= 10.101000
DETAIL: 45:v:fffe,p: 2,xx= 7,yy= 10.1010000
DETAIL: 46:v: 6d,p: 1,xx= 8,yy= 10.10100000
DETAIL: 47:v: 7d,p: 1,xx= 8,yy= 11.10100001
DETAIL: 48:v: 77,p: 2,xx= 7,yy= 11.1010001
DETAIL: 49:v:fffe,p: 4,xx= 6,yy= 11.101001
DETAIL: 50:v: 41,p: 2,xx= 7,yy= 12.1010010
DETAIL: 51:v: 29,p: 2,xx= 7,yy= 13.1010011
DETAIL: 52:v:fffe,p: 8,xx= 5,yy= 11.10101
DETAIL: 53:v:fffe,p: 4,xx= 6,yy= 12.101010
DETAIL: 54:v: 28,p: 2,xx= 7,yy= 14.1010100
DETAIL: 55:v: 6f,p: 2,xx= 7,yy= 15.1010101
DETAIL: 56:v: 73,p: 4,xx= 6,yy= 13.101011
DETAIL: 57:v:fffe,p: 16,xx= 4,yy= 9.1011
DETAIL: 58:v:fffe,p: 8,xx= 5,yy= 12.10110
DETAIL: 59:v: 75,p: 4,xx= 6,yy= 14.101100
DETAIL: 60:v: 23,p: 4,xx= 6,yy= 15.101101
DETAIL: 61:v: 22,p: 8,xx= 5,yy= 13.10111
asdfasdfasdf
