`
beike
  • 浏览: 362016 次
社区版块
存档分类
最新评论

关于Huffman 压缩

    博客分类:
  • Java
阅读更多

关于Huffman 压缩

0.原理
  Huffman编码是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保 持编码的唯一可解性。Huffman算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长 度)的和最小。


1.Huffman树

Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子:
比如有以下数据, ABFACGCAHGBBAACECDFGFAAEABBB
先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1)  括号里面的是统计次数

生成Huffman树:每次取最小的那两个节点(node)合并成一个节点(node),并且将累计数值相加作为新的接点的累计数值,最顶层的是根节点(root)  注:列表中最小节点的是指包括合并了的节点在内的所有节点,已经合并的节点不在列表中


运算的过程如下:
1:D+H(2)
2:DE+H(4)
3:F+G(6)
4:C+DEH(8)
5:B+FG(12)
6:A+CDEH(16)
7:ACDEH+BFG(28)


那么转化为Huffman树就是

        Huffman树            层数

          Root         
        ┌┴------┐
      ACDEH  BFG              1
      ┌┴---┐ ┌┴┐
    CDEH  A B  FG            2
    ┌┴--┐       ┌┴┐
  DEH   C       F  G          3
  ┌┴-┐
  DH  E                      4
┌┴┐
D    H                        5

取左面是1 右面是0 则有。
注:层数就是位数或者说是代码长度,权值=代码长度*该字的统计次数。

  代码          位数      权值
  A = 10          2        16
  B = 01          2        12
  C = 110        3        12
  D = 11111      5          5
  E = 1110        4          8
  F = 001        3          9
  G = 000        2          6
  H = 11110      5          5

可以看出Huffman代码是唯一可解的(uniquely decodable),如果你读到110就一定是C ,不会有任何一个编码是以110开始的。

 

如果不使用Huffman算法,而使用普通的编码,结果是什么呢?

        Huffman树            层数

          Root
        ┌┴┐
      ABCD    EFGH            1
  ┌┴┐      ┌┴┐
  AB  CD    EF  GH        2
┌┴┐┌┴┐┌┴┐ ┌┴┐
A  B C  D E  F G  H      3

取左面是1 右面是0 则有

  代码          位数      权值
  A = 111        3        24
  B = 110        3        18
  C = 101        3        12
  D = 100        3          3
  E = 011        3          6
  F = 010        3          9
  G = 001        3          9
  H = 000        3          3

利用Huffman编码得到的权值累计是 73,如果利用普通定长编码的话,则要用84字符长度。从这个比较,你可以看出,Huffman是怎么进行压缩的。


2.编码和解码
编码:将ABCDEFGH用Huffman树产生的编码对应着写到文件中,并且保留原始的Huffman树,主要是 编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树,每个Huffman树都必须有以下的结 构:code,char,left,right,probability(出现次数),通常情况是利用一个数组结构。因为在解码的时候只需要用到 code,所以只需要记录每个元素的编码就可以了。

解码:利用文件中保存的Huffman编码,一一对应,解读编码,把可变长编码转换为定长编码。

3.发展
由于Huffman编码需要扫描两次,第一次是统计数字,第二次是编码写文件,大大影响了速度,因此有人发明了enhanced Huffman aglorithm。这种算法只扫描一遍文件,动态产生Huffman树,即每读n个字节就重新编码一次Huffman树,以达到提高速度的目的。在解码 的过程中使用动态还原技术。

分享到:
评论

相关推荐

    huffman压缩解压缩

    huffman压缩解压缩 vc6.0

    Huffman压缩解压java实现

    Huffman编码是一种基于字符频率的无损数据压缩算法,由美国计算机科学家David A. Huffman在1952年提出。它的核心思想是构建一棵特殊的二叉树,即Huffman树,来对数据进行编码。在Java中实现Huffman编码,需要理解其...

    Huffman压缩和解压.doc

    Huffman压缩是一种基于概率的无损数据压缩算法,它通过构建最优二叉树(Huffman树)来实现。在给定的文档中,程序模拟了对小写26个英文字母进行Huffman压缩的过程。以下是对这个过程的详细解释: 1. **需求分析**:...

    huffman压缩 数据结构

    huffman 压缩文件 数据结构北邮

    Huffman压缩程序exe

    Huffman压缩程序exe文件,大学去年做的。

    Huffman编码对英文文本的压缩和解压缩

    ### Huffman编码对英文文本的压缩和解压缩 #### 概述 Huffman编码是一种广泛应用于数据压缩领域的编码方法,尤其适用于英文文本的压缩与解压缩。这种方法基于变长编码原理,通过对不同字符出现频率的统计,构建出...

    用c语言写的Huffman压缩程序

    在C语言中实现Huffman压缩涉及到几个关键步骤,包括字符频率统计、构建Huffman树、生成编码表以及对原始数据进行编码和解码。 1. **字符频率统计**:首先,我们需要读取输入文件(如test1.bmp和test2.bmp)并计算每...

    实验4 Huffman编码对英文文本的压缩和解压缩.doc

    Huffman 编码对英文文本的压缩和解压缩 本实验的目的是掌握 Huffman 编码的原理,并使用 VC++ 6.0 开发环境来实现对英文文本的压缩和解压缩。实验要求学生掌握 Huffman 编码的原理、VC++ 开发环境的使用、C 语言...

    Huffman压缩算法C语言实现

    Huffman压缩算法是一种高效的数据编码方法,主要用于无损数据压缩。该算法由David A. Huffman在1952年提出,其核心思想是利用字符出现频率的差异来创建一棵最优二叉树,使得频繁出现的字符能用较短的编码表示,而较...

    HUFFMAN解压缩工具

    哈夫曼(Huffman)编码是一种数据压缩算法,由美国计算机科学家戴维·艾尔·哈夫曼在1952年提出。这种编码方法基于字符出现频率,通过构建最优二叉树实现对数据的高效压缩。在哈夫曼编码中,频繁出现的字符会得到较...

    huffman压缩与解压缩

    哈夫曼编码(Huffman Coding)是一种数据压缩算法,由美国计算机科学家大卫·艾尔文·哈夫曼在1952年提出。这个算法基于一种称为哈夫曼树(Huffman Tree)的数据结构,也被称为最优二叉树。哈夫曼编码的主要目标是为...

    C++做的Huffman压缩解压算法

    本篇文章将详细探讨Huffman压缩与解压算法及其在C++中的实现。 一、Huffman编码的基本原理 1. 频率统计:首先,我们需要对输入的文本或二进制数据进行字符频率统计,找出出现最频繁的字符。 2. 构建Huffman树:...

    HUFFMAN 压缩

    哈夫曼(Huffman)压缩是一种数据编码方法,主要用于无损数据压缩,它基于字符频率构建最优前缀树,从而实现高效的数据存储。这个方法由大卫·哈夫曼在1952年提出,因此得名。在描述中提到的“效率很低,过程很慢”...

    huffman压缩文件

    初学者写的,huffman压缩文件。求指点,求喷!

    huffman数据压缩

    哈夫曼编码(Huffman Coding)是一种非常有效的无损数据压缩方法,由大卫·艾尔·哈夫曼在1952年提出。这个压缩算法是基于频率编码的原理,通过对输入数据中出现频率较高的字符赋予较短的编码,而频率较低的字符则...

    Huffman编码压缩,解压缩工具,Pyqt5,Python

    Huffman 压缩解压工具, 基于 pyqt5 图形程序开发框架,采用 python 实现了 Huffman 编码压缩/解压算法,实现了对二进制文件进行压缩编码,和解压缩译码功能,界面交互简单友好,易于操作。 详细说明:...

    Huffman 压缩解压缩 Java实现

    需要注意的是,Java实现的Huffman压缩解压缩不适用于二进制文件,因为二进制文件的字节分布与ASCII文档不同,直接应用ASCII字符频率统计可能会导致压缩效果不佳。对于二进制文件,通常需要先进行预处理,如使用字节...

    huffman压缩

    使用huffman编码对各种文档进行压缩,使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的...

    哈夫曼 huffman压缩算法

    在“哈夫曼 huffman压缩算法”的项目中,开发了一个基于Visual C++ (VC++)的Windows图形用户界面工程,用于实现文件的压缩和解压缩功能。这个实验设计旨在帮助大学计算机专业的学生深入理解数据结构,特别是树和图的...

    图形画huffman压缩程序

    【图形画Huffman压缩程序】是一款使用VC6.0 MFC框架开发的用户界面友好、交互性强的小型软件,它实现了著名的哈夫曼编码(Huffman Coding)算法,主要用于对TXT文本文件进行压缩,同时也支持其他类型的文件压缩。...

Global site tag (gtag.js) - Google Analytics