/Files/dvb-dvb/HuffmanCode.rar這個(gè)是最新的huffman code (encoder and decoder) , 但是效率有待提升.
一直占cpu 50% , 掃描兩遍文件,一遍建立huffman code,另一遍,用二進(jìn)制替換,
1,有兩個(gè)問(wèn)題沒(méi)有解決
1,動(dòng)態(tài)建立huffman tree node value.僅僅掃描一遍,
2,根據(jù)node的值去排序得到frequence時(shí),這個(gè)值到底取1個(gè)byte,還是2個(gè)byte.
Huffman算法簡(jiǎn)介
Huffman算法是一種基于統(tǒng)計(jì)的壓縮方法。它的本質(zhì)就是對(duì)文本文件中的字符進(jìn)行重新編碼，對(duì)于使用頻率越高的字符，其編碼也越短。但是任何2個(gè)字符的編碼，是不能出現(xiàn)向前包含的。也就是說(shuō)字符A的編碼的前段，不可能為字符B的編碼。經(jīng)過(guò)編碼后的文本文件，主要包含2個(gè)部分：Huffman碼表部分和壓縮內(nèi)容部分。解壓縮的時(shí)候，先把Huffman碼表取出來(lái)，然后對(duì)壓縮內(nèi)容部分各個(gè)字符進(jìn)行逐一解碼,形成源文件。
由此可見(jiàn)，使用Huffman算法的關(guān)鍵是形成Huffman碼表。怎樣才能生成一個(gè)“使用頻率越高的字符，其編碼也越短”的碼表呢?這里就要用到 Huffman樹(shù)的數(shù)據(jù)結(jié)構(gòu)。當(dāng)把一棵Huffman樹(shù)生成后，碼表也就生成了。以下舉例說(shuō)明，假定我們的原始文本為"abcbbcccc"
Huffman樹(shù)生成步驟:
1.掃描源文件，對(duì)字符頻率進(jìn)行統(tǒng)計(jì)。
對(duì)于我們的樣例，統(tǒng)計(jì)結(jié)果是:a:1 b:3 c:5 (按頻率升序排列)
2.從上述隊(duì)列中取出頻率最低的2個(gè)節(jié)點(diǎn)，合并成一個(gè)頻率為2節(jié)點(diǎn)頻率之和的樹(shù)枝節(jié)點(diǎn)X，加入到原隊(duì)列中，加入后，繼續(xù)保持隊(duì)列按頻率升序排列.
3.重復(fù)步驟2，直到隊(duì)列中只有一個(gè)節(jié)點(diǎn)。
4.這樣，我們就形成了一棵Huffman樹(shù)。葉子節(jié)點(diǎn)為字符，從樹(shù)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑即為該字符的Huffman編碼。從一個(gè)節(jié)點(diǎn)導(dǎo)航到其左孩子，該段路徑為0，導(dǎo)航到右孩子，該段路徑為1.所以，a字符的編碼就是00,b字符的編碼為01,c字符的編碼為1，符合"使用頻率越高的字符，編碼越短"的要求。理論論證過(guò)程見(jiàn)<算法導(dǎo)論>P233
5.Huffman碼表生成后，原文本"abcbbcccc"就變成了0001101011111的位串，按每個(gè)字符占用2個(gè)byte計(jì)算，大小由原來(lái)的18個(gè)字節(jié)(9*2),共144個(gè)bit,變成了13個(gè)bit,2個(gè)字節(jié)。達(dá)到了壓縮的目的。
解壓縮過(guò)程:
解壓縮也分成2部分進(jìn)行，首先是根據(jù)壓縮文件中的Huffman碼表，在內(nèi)存中生成一棵Huffman樹(shù)，然后，根據(jù)Huffman樹(shù)，對(duì)壓縮內(nèi)容進(jìn)行解壓縮。比如如果壓縮內(nèi)容為位串0001101011111，那么從樹(shù)根節(jié)點(diǎn)起，因?yàn)榈谝粋€(gè)bit為0，先轉(zhuǎn)向左子樹(shù)，第二個(gè)bit為0,再轉(zhuǎn)向左子樹(shù),到達(dá)葉子a,所以解碼出來(lái)的第一個(gè)字符就是a,每次解壓一個(gè)字符，都從根節(jié)點(diǎn)起，根據(jù)bit流，向左或向右轉(zhuǎn)，直到到達(dá)葉子節(jié)點(diǎn)，也就是解壓出來(lái)的字符。一直重復(fù)此過(guò)程，直到所有的字符都被解壓縮。
壓縮文件格式
使用Huffman壓縮算法對(duì)文本文件壓縮后，就形成了一個(gè)壓縮文件，該壓縮文件包含2部分，一部分為Huffman碼表，也就是Huffman 樹(shù)，第二部分為根據(jù)碼表生成的內(nèi)容位串。如何設(shè)計(jì)Huffman樹(shù)的存儲(chǔ)格式呢?本文采用從上到下，從左到右分層遍歷節(jié)點(diǎn)，順序存儲(chǔ)的方式。如下圖:
也就是說(shuō)，對(duì)于前述的Huffman樹(shù)，其持久化形式為:0xfffe 0xfffe 0x0063 0x0061 0x0062,其中0xfffe代表樹(shù)枝節(jié)點(diǎn),而0x0061,0x0062,0x0063分別為a,b,c的Unicode碼。因?yàn)樗械臉?shù)枝節(jié)點(diǎn)的值都是0xfffe，所有樹(shù)枝節(jié)點(diǎn)都有2個(gè)孩子，節(jié)點(diǎn)排列方式是按從上到下，從左到右分層排列，所以能根據(jù)此持久化字節(jié)數(shù)組，把Huffman樹(shù)在內(nèi)存中重新生成。
另外為了升級(jí)版本，嵌入了magic number和version。
完整工程下載
本文涉及到的完整的eclipse工程，可以從這里下載。注:內(nèi)含測(cè)試樣例《平凡的世界》文本文件，體積較大，請(qǐng)使用下載工具下載。另外，本程序中采用了泛型，請(qǐng)?jiān)谥辽僭贘DK1.5版本上編譯運(yùn)行。
代碼簡(jiǎn)要說(shuō)明
1.HuffmanTextEncoder類(lèi)完成壓縮功能，可直接運(yùn)行，壓縮測(cè)試用文本文件。
2.HuffmanTextDecoder類(lèi)完成解壓縮功能，可直接運(yùn)行，解壓縮 壓縮后的文本文件。
3.BitReader,工具類(lèi)，實(shí)現(xiàn)對(duì)BufferedInputStream的按位讀取。
4.BitWriter,工具類(lèi)，實(shí)現(xiàn)按位寫(xiě)入的功能。該類(lèi)來(lái)自網(wǎng)絡(luò)。
5.MinHeap<T> ,模板工具類(lèi)，實(shí)現(xiàn)了一個(gè)最小堆。生成Huffman樹(shù)時(shí)使用。
壓縮效果
使用本程序?qū)Α镀椒驳氖澜纭纷鰤嚎s測(cè)試，壓縮前為文本文件，大小為1.7M,壓縮后為二進(jìn)制文件，大小接近1M（988,817byte）,而 zip壓縮后體積為920,997byte,比zip差，壓縮文件存儲(chǔ)格式待改善。另外，因?yàn)閺腍uffman壓縮算法的原理可知，該算法對(duì)字符重復(fù)率高的文本最有效，比如長(zhǎng)篇小說(shuō)或者英文小說(shuō)。
以上內(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
