ts,ps,mpeg2 decoder and analysis

分析工具,免费下载.

  IT博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  40 随笔 :: 0 文章 :: 168 评论 :: 0 Trackbacks

Huffman算法简介

Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但是任何2个字符的编码,是不能出现向前包含的。也就是说字符A的编码的前段,不可能为字符B的编码。经过编码后的文本文件,主要包含2个部分:Huffman码表部分和压缩内容部分。解压缩的时候,先把Huffman码表取出来,然后对压缩内容部分各个字符进行逐一解码,形成源文件。

由此可见,使用Huffman算法的关键是形成Huffman码表。怎样才能生成一个“使用频率越高的字符,其编码也越短”的码表呢?这里就要用到 Huffman树的数据结构。当把一棵Huffman树生成后,码表也就生成了。以下举例说明,假定我们的原始文本为"abcbbcccc"

Huffman树生成步骤:

1.扫描源文件,对字符频率进行统计。

对于我们的样例,统计结果是:a:1  b:3 c:5 (按频率升序排列)

 

2.从上述队列中取出频率最低的2个节点,合并成一个频率为2节点频率之和的树枝节点X,加入到原队列中,加入后,继续保持队列按频率升序排列.

3.重复步骤2,直到队列中只有一个节点。

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树的存储格式呢?本文采用从上到下,从左到右分层遍历节点,顺序存储的方式。如下图:

也就是说,对于前述的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
posted on 2009-05-25 09:27 TS,MPEG2,dvbc专家 阅读(1653) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。