/Files/dvb-dvb/HuffmanCode.rar这个是最新的huffman code (encoder and decoder) , 但是效率有待提升.
一直占cpu 50% , 扫描两遍文件,一遍建立huffman code,另一遍,用二进制替换,
1,有两个问题没有解决
1,动态建立huffman tree node value.仅仅扫描一遍,
2,根据node的值去排序得到frequence时,这个值到底取1个byte,还是2个byte.
Huffman算法简介
Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但是任何2个字符的编码,是不能出现向前包含的。也就是说字符A的编码的前段,不可能为字符B的编码。经过编码后的文本文件,主要包含2个部分:Huffman码表部分和压缩内容部分。解压缩的时候,先把Huffman码表取出来,然后对压缩内容部分各个字符进行逐一解码,形成源文件。
由此可见,使用Huffman算法的关键是形成Huffman码表。怎样才能生成一个“使用频率越高的字符,其编码也越短”的码表呢?这里就要用到 Huffman树的数据结构。当把一棵Huffman树生成后,码表也就生成了。以下举例说明,假定我们的原始文本为"abcbbcccc"
Huffman树生成步骤:
1.扫描源文件,对字符频率进行统计。
对于我们的样例,统计结果是:a:1 b:3 c:5 (按频率升序排列)
![](file:///D:/download/code/buildffmpeg/huffman_2/chencwf/huffman4_files/huf1-medium.jpg)
2.从上述队列中取出频率最低的2个节点,合并成一个频率为2节点频率之和的树枝节点X,加入到原队列中,加入后,继续保持队列按频率升序排列.
![](file:///D:/download/code/buildffmpeg/huffman_2/chencwf/huffman4_files/huf2-medium.jpg)
3.重复步骤2,直到队列中只有一个节点。
![](file:///D:/download/code/buildffmpeg/huffman_2/chencwf/huffman4_files/huf3-medium.jpg)
4.这样,我们就形成了一棵Huffman树。叶子节点为字符,从树根节点到叶子节点的路径即为该字符的Huffman编码。从一个节点导航到其左孩子,该段路径为0,导航到右孩子,该段路径为1.所以,a字符的编码就是00,b字符的编码为01,c字符的编码为1,符合"使用频率越高的字符,编码越短"的要求。理论论证过程见<算法导论>P233
5.Huffman码表生成后,原文本"abcbbcccc"就变成了0001101011111的位串,按每个字符占用2个byte计算,大小由原来的18个字节(9*2),共144个bit,变成了13个bit,2个字节。达到了压缩的目的。
解压缩过程:
解压缩也分成2部分进行,首先是根据压缩文件中的Huffman码表,在内存中生成一棵Huffman树,然后,根据Huffman树,对压缩内容进行解压缩。比如如果压缩内容为位串0001101011111,那么从树根节点起,因为第一个bit为0,先转向左子树,第二个bit为0,再转向左子树,到达叶子a,所以解码出来的第一个字符就是a,每次解压一个字符,都从根节点起,根据bit流,向左或向右转,直到到达叶子节点,也就是解压出来的字符。一直重复此过程,直到所有的字符都被解压缩。
压缩文件格式
使用Huffman压缩算法对文本文件压缩后,就形成了一个压缩文件,该压缩文件包含2部分,一部分为Huffman码表,也就是Huffman 树,第二部分为根据码表生成的内容位串。如何设计Huffman树的存储格式呢?本文采用从上到下,从左到右分层遍历节点,顺序存储的方式。如下图:
![](file:///D:/download/code/buildffmpeg/huffman_2/chencwf/huffman4_files/huf4-medium.jpg)
也就是说,对于前述的Huffman树,其持久化形式为:0xfffe 0xfffe 0x0063 0x0061 0x0062,其中0xfffe代表树枝节点,而0x0061,0x0062,0x0063分别为a,b,c的Unicode码。因为所有的树枝节点的值都是0xfffe,所有树枝节点都有2个孩子,节点排列方式是按从上到下,从左到右分层排列,所以能根据此持久化字节数组,把Huffman树在内存中重新生成。
另外为了升级版本,嵌入了magic number和version。
完整工程下载
本文涉及到的完整的eclipse工程,可以从这里下载。注:内含测试样例《平凡的世界》文本文件,体积较大,请使用下载工具下载。另外,本程序中采用了泛型,请在至少在JDK1.5版本上编译运行。
代码简要说明
1.HuffmanTextEncoder类完成压缩功能,可直接运行,压缩测试用文本文件。
2.HuffmanTextDecoder类完成解压缩功能,可直接运行,解压缩 压缩后的文本文件。
3.BitReader,工具类,实现对BufferedInputStream的按位读取。
4.BitWriter,工具类,实现按位写入的功能。该类来自网络。
5.MinHeap<T> ,模板工具类,实现了一个最小堆。生成Huffman树时使用。
压缩效果
使用本程序对《平凡的世界》做压缩测试,压缩前为文本文件,大小为1.7M,压缩后为二进制文件,大小接近1M(988,817byte),而 zip压缩后体积为920,997byte,比zip差,压缩文件存储格式待改善。另外,因为从Huffman压缩算法的原理可知,该算法对字符重复率高的文本最有效,比如长篇小说或者英文小说。
以上内容为转载:
http://chencwf.googlepages.com/huffman
以下为自己的内容:
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