精华内容
下载资源
问答
  • Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。###哈夫曼原理 ###哈夫曼算法流程图 ###...

    ###概念

    哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

    ###哈夫曼原理

    6b6d15dce058dd248fb4e1ec2adac08a.png

    ###哈夫曼算法流程图

    5f4793ea88e77378923fc8e2762cd164.png

    ###哈夫曼树

    给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 树节点间的边相关的数叫做权。

    a31aafde9092c66d15a21dccc071ad76.png

    从树中的一个节点到另一个节点之间的分支构成两个点之间的路径,路径上的分支数目称作路径长度。

    图中二叉树a中,跟节点到D的路径长度就是4,b中根节点到D的路径长度为2。

    树的路径长度就是从树根到每一个节点的路径长度之和。二叉树a的路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

    如果考虑带权的节点,节点的带权的路径长度就是从该节点到树根之间的路径长度乘该节点的权。

    数的带权路径长度就是所有叶子节点的带权路径长度之和。

    带权路径长度(WPL)最小的二叉树称作哈夫曼树。

    ###如何构造哈夫曼树

    下面我们以【5、8、4、11、9、13】为例来画出哈夫曼树(数字大小代表权重大小,越大的权重越大)

    第一步:按从小到大排序。

    【5、8、4、11、9、13】→【4、5、8、9、11、13】

    第二步:选最小两个数画出一个树,最小数为4和5。

    给定的4、5、8、9、11、13为白色, 红色的9为4+5,与给定的白9无关,新序列为:【红9(含子节点4、5)、8、9、11、13】

    7c32921730e11bf4bbcd3d27c9b22767.png

    ####之后一直重复第一、第二步:排序然后取两个最小值。实际就是一个递归过程

    排序:

    427752598b7e8bb28559faf6dcbad286.png

    取两个最小数8和9:

    88301ca443a1051d66f1f46521af7b89.png

    排序

    1737bb7a7aa7bf7d77408aa4426a7797.png

    区两个最小数11和9

    bb816ae09eb87a575a611687ad4ef4f2.png

    排序,然后取两个最小数13和17:

    9fe015ce56c7a4c6734d7d0931184813.png

    取两个最小数20和30:

    9fb61279d0b9f2ea5b5734649302d171.png

    展开全文
  • 哈夫曼编码的理论依据是变字长编码理论。在变字长编码中,编码器...可以证明,按照概率出现大小的顺序,对输出码字分配不同码字长度的变字长编码方法,其输出码字的平均码长最短,与信源熵值最接近,编码方法最佳。
  • 哈弗曼编码介绍

    2018-05-27 20:38:24
    对于出现概率大元素编以短字长码,对于出现概率小元素编以长字长码,来实现平均码长最短。Huffman编码是一种应用广泛可变长编码方式,是二叉树一种特殊转化形式。利用哈夫曼树求得用于通信二进制...

    哈弗曼编码简介:哈夫曼编码是一种可变字长的无损编码方式。对于出现概率大的元素编以短字长的码,对于出现概率小的元素编以长字长的码,来实现平均码长最短。

    Huffman编码是一种应用广泛的可变长编码方式,是二叉树的一种特殊转化形式。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。哈弗曼树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。哈弗曼编码的原理是:将使用次数多的代码转换成长度较短的编码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。

    哈夫曼编码方法的具体过程是首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字。

    哈弗曼编码原理:哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树。因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用。

    众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码。以西文为例,例如我们要在计算机当中存储这样的一句话:I am a teacher 。就需要15个字节,也就是120个二进制位的数据来实现。

    与这种定长编码不同的是,哈夫曼编码是一种变长编码。它根据字符出现的概率来构造平均长度最短的编码。换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长。当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的。这就是哈夫曼编码实现数据压缩的基本原理。

    建立哈弗曼编码树

    哈夫曼(Huffman)编码的核心部分为哈夫曼编码树huffman coding tree)。对于所有可能的输入符号(通常对应为字节)在哈夫曼编码树上都有对应的一个叶节点,在叶节点的位置就是该符号的哈夫曼编码。具体来说,一个符号对应的哈夫曼编码就是从根节点开始,沿左字节点(0)或右子节点(1)前进,一直找到该符号叶节点为止的路径对应的二进制编码。同其他码词长度可变的编码一样,区别在于不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”(coding tree)的技术。

    算法步骤如下: 

    1)初始化,把n个字符根据符号概率的大小按由大到小顺序对符号进行排序。 

    2)对概率最小的两个符号按照递增(递减)排列组成一个新符号(节点),然后把这两个概率相加作为新的节点的概率。 

    3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列。

    4)重复第(2)步,直到概率相加等于1为止。 

    5)从编码树的根开始回溯到原始的符号,并将每一左分枝赋值为“1”,右分枝赋值为“0”。

    哈夫曼编码的算法实例

    下面我们以abcddbb为例,根据a,b,c,d 四个字符在原始数据串中出现的频率,构造静态哈夫曼编码树。

    统计结果如表所示:

    1 字符出现频率

    符号

    a

    b

    c

    d

    频率

    1/7

    3/7

    1/7

    2/7

    然后,按照前面提到的构造方法,经过表 2 的四个步骤,即可获得基于表 1 频率统计的哈夫曼编码树。

    2 建立哈弗曼编码树

    步骤1


    初始状态,将每个字符看作一颗只有一个叶子节点的字数,按出现几率排序。

    步骤2

     

    将出现几率最小的a、c组成一棵树,并继续按在信息中出现的几率排序。

    步骤3

     

    将 a、c 的父节点与出现几率次高的 d 节点组合成新的树,继续按几率进行排序。

    步骤4

     

    组合最后两个元素完成编码树构造。

    至此,我们建立起了给定符号串的哈夫曼编码树。经过编码 a:000,b:1,c:001,d:01。

    注意:霍夫曼编码不唯一,同一层上的结点,位置是可以互换的。哈夫曼树不唯一,所以,编码也不唯一。

    但是一旦哈夫曼树构造好了之后,哈夫曼编码是唯一的。


    霍夫曼编码的硬件实现

    霍夫曼编码的原理参考

    基于FPGA的Huffman编码并行实现及高速存储系统设计

    基于verilog实现哈夫曼编码的新方法

    展开全文
  • Xilinx哈夫曼编码 对一段数据序列进行哈夫曼编码,使得平均码长最短,输出各元素编码编码数据序列。 1. 设计要求 (1)组成序列元素是[0-9]这10个数字,每个数字其对应4位二进制数表示。比如5对应0101,9...
  • 哈夫曼编码是一种所得码字是异前置的变长码其平均码长最短被称为最 佳变长码也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2 从最小概率的两个消息开始编码并给予一定的编码规则如小概率 ...
  • 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得码字是异前置变长码其平均码长最短被称为...
  • PAGE / NUMPAGES 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得码字是异前置变长码,其平均码长最短,被称为最佳变长码,也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率两个消息...
  • 哈夫曼编码是一种所得码字是异前置的变长码其平均码长最短被称为最佳变长码也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率的两个消息开始编码并给予一定的编码规则如小概率的下...
  • 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得码字是异前置变长码其平均码长最短被称为...
  • 哈夫曼编码是一种所得码字是异前置的变长码其平均码长最短被称为最佳变长码也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率的两个消息开始编码并给予一定的编码规则如小概率的下...
  • Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。 本实验实现了如下功能: (1)产生[0 255]...
  • 哈夫曼编码是一种所得码字是异前置的变长码其平均码长最短被称为最佳变长码也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率的两个消息开始编码并给予一定的编码规则如小概率的下...
  • 在前面学习了信息熵,可以计算所有信息的平均码长,那么就可以根据这个标准来判断是否可以对信息进行压缩操作。这里典型代表是哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变...

    在前面学习了信息熵,可以计算所有信息的平均码长,那么就可以根据这个标准来判断是否可以对信息进行压缩的操作。这里典型的代表是哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。在图像压缩里经常会使用到它,这里先来学习一个字符的压缩例子:

    #python 3.7.4,opencv4.1
    #蔡军生 https://blog.csdn.net/caimouse/article/details/51749579
    #
    import numpy as np
    import cv2
    from matplotlib import pyplot as plt
    import queue
    
    #huffman节点结构
    class HuffmanNode(object):
        def __init__(self, left=None, right=None, root=None):
            self.left = left
            self.right = right
            self.root = root     # 上一个节点
        def children(self):
            return((self.left, self.right))
    #字母在将要压缩的数据里的频率统计表
    freq = [
        (8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'),
        (12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'),
        (6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'),
        (2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'), 
        (0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'), 
        (2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'),
        (1.974, 'y'), (0.074, 'z') ]
    #创建优先级队列,构造哈夫曼树表示频率表
    def create_tree(frequencies):
        p = queue.PriorityQueue() #创建优先级队列
        for value in frequencies:    # 1.创建每一个叶节点,添加到优先级队列
            p.put(value)            
    
        root = None
        while p.qsize() > 1:         # 2. 队列大于一个节点
            l, r = p.get(), p.get()  # 2a. 删除两个最高优先级的节点
            node = HuffmanNode(l, r, root) # 2b. 创建一个合并节点
            root = node
            
            p.put((l[0]+r[0], node)) # 2c. 节点添加到队列      
        return p.get()               # 3. 树已经合并完成,返回根节点
    
    node = create_tree(freq)
    print(node)
    
    # 递归下降地遍历树,
    #每个节点构造码表
    def walk_tree(node, prefix="", code={}):
        if isinstance(node[1].left[1], HuffmanNode):#左树递归
            walk_tree(node[1].left,prefix+"0", code)
        else:
            code[node[1].left[1]]=prefix+"0" #叶子
            
        if isinstance(node[1].right[1],HuffmanNode):#右树递归
            walk_tree(node[1].right,prefix+"1", code)
        else:
            code[node[1].right[1]]=prefix+"1"
        return(code)
    
    code = walk_tree(node)
    #按频率大小输出码表
    for i in sorted(freq, reverse=True):
        print(i[1], '{:6.2f}'.format(i[0]), code[i[1]])
        
    #
    cv2.waitKey(0)
    cv2.destroyAllWindows()
     
    

    结果输出如下:

    (100.03800000000001, <__main__.HuffmanNode object at 0x0000019EB0188F88>)

    e  12.70 100

    t   9.06 000

    a   8.17 1110

    o   7.51 1101

    i   6.97 1011

    n   6.75 1010

    s   6.33 0111

    h   6.09 0110

    r   5.99 0101

    d   4.25 11111

    l   4.03 11110

    c   2.78 01001

    u   2.76 01000

    m   2.41 00111

    w   2.37 00110

    f   2.23 00100

    g   2.02 110011

    y   1.97 110010

    p   1.93 110001

    b   1.49 110000

    v   1.04 001010

    k   0.75 0010111

    j   0.15 001011011

    x   0.15 001011010

    q   0.10 001011001

    z   0.07 001011000

     

     

    玩转人工智能库-深入浅出OpenCV
    https://edu.csdn.net/course/detail/26616

     

    Python游戏开发入门

    http://edu.csdn.net/course/detail/5690
     

    你也能动手修改C编译器

    http://edu.csdn.net/course/detail/5582

    展开全文
  • 下面引证一个定理,该定理保证了按字符出现概率分配码长,可使平均码长最短。 本期分析非常重要赫夫曼编码实际应用,在数据压缩与解压方面十分重要!从底层原理入手,切合编码实现。 涉及知识点 Java编程基础 ...

    前言

    赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长
    度最短的码字,有时称之为最佳编码,一般就称Huffman编码。下面引证一个定理,该定理保证了按字符出现概率分配码长,可使平均码长最短。

    本期分析非常重要的赫夫曼编码实际应用,在数据压缩与解压方面十分重要!从底层原理入手,切合编码实现。

    • 涉及知识点
      Java编程基础 Comparable类Java比较器
      数据结构中简单二叉树和赫夫曼树的构造原理

    由于篇幅过长,本篇先着重分析压缩原理,进而解压反向操作就会简单明了很多。

    • 原理解析
      之于赫夫曼编码,就是以字节为基本单位(一个字节byte为8位bit),表示范围为0-255,所有的字符或是文件都可以转化成字节数组byte[],然后统计每个字节出现的次数(权重),生成对应的赫夫曼树,不定长编码,出现次数多的都在赫夫曼树相对较高的节点上,进而它的赫夫曼编码就会相对较短,相反出现次数少的那些字节都处在赫夫曼树较低的节点上,进而它的赫夫曼编码就会相对较长(出现次数少,没关系),并且只有叶子结点来表示每个字节(有左右子树的不是),这样一来就不会有解析冲突(谁也不是谁的前缀,也不是谁的后缀),这样一来,一个字符串或一个文件的字节就会被压缩至比原来字节数更少,从而达到压缩的目的,接下来就实际操作一番

    • 前期准备
      前期需要先创建赫夫曼树结点基类。

    /**
     * Note类(一个字节对应一个Note对象)
     * 实现Comparable接口根据权重大小进行排序
     * @author Superb
     */
    class Note implements Comparable<Note>{
    	//存储的字节数据
    	Byte data;
    	//权重(该字节数据出现的次数)非常重要
    	int weight;
    	//左节点
    	Note left;
    	//右节点
    	Note right;
    	//构造器 每创建一个Node节点就要传入其字节数据以及权重
    	public Note(Byte data, int weight) {
    		super();
    		this.data = data;
    		this.weight = weight;
    	}
    	@Override
    	public String toString() {
    		return "Node [data=" + data + ", weight=" + weight + "]";
    	}
    	//重写compareTo方法
    	@Override
    	public int compareTo(Note o) {
    		//根据权重属性值 升序排列
    		return this.weight-o.weight;
    	}
    }
    
    • 统计每个字节出现的次数
      每个文件或是字符串都是由一个个字节组成,这里先对字节数组进行处理,减少耦合度。通过HashMap的特性统计每个字符出现的次数。
    	//成员变量 存每个byte出现的次数
    	private static Map<Byte,Integer> map = new HashMap<>();
    	/**
    	 * 通过Map统计各byte出现的次数生成Note对象返回List<Note>
    	 * @param bytes
    	 * @return List<Note>
    	 */
    	private static List<Note> getNotes(byte[] bytes){
    		//存储每个字节生成的Node结点对象
    		List<Note> list = new ArrayList<>();
    		//遍历byte数组
    		for (byte b : bytes) {
    			//如果map中还没有此字节,就设次数为1
    			if(map.get(b)==null) {
    				map.put(b, 1);
    			}
    			//如果map中已出现此字节,就+1
    			else {
    				map.put(b, map.get(b)+1);
    			}
    		}
    		//遍历整个map
    		for(Entry<Byte, Integer> entry : map.entrySet()) {
    			//为map中每个的字节创建Note结点,并传入字节数据和权重(出现次数),
    			list.add(new Note(entry.getKey(),entry.getValue()));
    		}
    		//返回,此时已包含所有结点对象
            return list;
    	}
    
    • 根据权重值生成对应的赫夫曼树
      赫夫曼树的生成法:每次把权值最小的两个二叉树合并,选择两个权值最小的a和b作为最底层节点,然后从List集合中移除a、b,但需要再添加一个a和b权值相加后的结点(此节点有左右子树,非叶子结点),一直循环到最后生成赫夫曼树。
      示例:
      在这里插入图片描述
    	/**
    	 * 传入集合生成赫夫曼树返回根结点
    	 * @param list
    	 * @return Note
    	 */
    	private static Note huffmanTree(List<Note> list) {
    		Note left = null;
    		Note right = null;
    		Note parent = null;
    		//循环遍历List集合中的结点,只要不为空就继续
    		while(list.size()>1) {
    			//对所有结点进行排序,前面已实现Comparable接口,调用Collections工具类即可排序。
    			Collections.sort(list);
    			//0和1位置的结点权值最小,分别赋值给左右结点
    			left = list.get(0);
    			right = list.get(1);
    			//并生成它们的父结点,(权值相加,字节数据为空,因为最后不是叶子结点)
    			parent = new Note(null,left.weight+right.weight);
    			//连接左右孩子
    			parent.left = left;
    			parent.right = right;
    			//从集合中移除已经生成的结点
    			list.remove(left);
    			list.remove(right);
    			//添加新的父类结点
    			list.add(parent);
    		}
    		//遍历结束 返回根结点 此时已生成带权路径长度最优的赫夫曼树
    		return parent;
    	}
    
    • 根据赫夫曼树生成对应赫夫曼编码表
      每个叶子结点对应一个Note对象,从根节点出发,往左为0,往右为1,深入遍历生成每个叶子结点的对应赫夫曼编码。
      编码表非常重要,压缩之后要跟压缩文件一同保存,因为它是还原解压的唯一依照!
    	//成员变量 各byte对应的字符串二进制码
    	private static Map<Byte,String> huffmanCodes = new HashMap<>();
    	/**
    	 * 递归生成各Byte对应的字符串二进制码
    	 * @param note 根结点
    	 * @param str 0代表往左子树遍历 1代表往右子树遍历
    	 * @param sb
    	 */
    	private static void getCodes(Note note,String str,StringBuilder sb) {
    		//额外定义sb2接收每次递归生成的上层编码sb,不直接对sb进行操作,从而不影响全局变量sb
    		StringBuilder sb2 = new StringBuilder(sb);
    		//每次递归深入下一层先加上每一层的编码(左0右1)
    		sb2.append(str);
    		//先判不为空 再继续
    		if(note!=null) {
    			//如果数据为空,说明不是叶子结点,不是byte字节结点
    			if(note.data==null) {
    				//继续左右递归遍历 往左走+0 往右走+1
    				getCodes(note.left, "0",sb2);
    				getCodes(note.right, "1",sb2);
    			}
    			//如果不为空,说明是叶子结点,已递归生成其赫夫曼编码
    			else {
    				//存到map中 key=结点byte值 value=对应赫夫曼编码
    				huffmanCodes.put(note.data, sb2.toString());
    			}
    		}
    	}
    	/**
    	 * 赫夫曼树转赫夫曼编码表(重载)
    	 * 调用上述方法,并返回生成的赫夫曼编码表(每个字节byte对应一个编码)
    	 * @param note
    	 * @return
    	 */
    	private static Map<Byte,String> getCodes(Note note) {
    		getCodes(note,"",new StringBuilder());
    		//返回每个字节byte对应的赫夫曼编码:0110010(由0和1排列组合形成)
    		return huffmanCodes;
    	}
    
    • 根据赫夫曼编码表对元数据进行压缩
    	/**
    	 * 传入压缩前byte[]和对应Huffman编码表生成压缩后的byte[]
    	 * @param bytes 对应的就是需要压缩的文件或字符串
    	 * @param huffmanCodes 赫夫曼编码表
    	 * @return byte[] 返回压缩后的byte数组
    	 */
    	private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes) {
    		StringBuilder sb = new StringBuilder();
    		//遍历元byte数组
    		for(byte b : bytes) {
    			//去编码表中匹配每个字节,并将其编码连接一起到sb
    			sb.append(huffmanCodes.get(b));
    		}
    		//此时sb里面存储的就是压缩后的二进制数据(全部由01组成),但此时仍是用字符串进行存储,一个字符两个字节。
    		//此时的sb字符串比元数据要大得多,所以不能用字符串存二进制数据,还是要以byte数组(sb中每八个字符转化为一个字节)的形式。
    		//创建一个长度适宜的byte数组
    		byte[] byteZip = new byte[(sb.length()+7)/8];//绝对够用
    		int count = 0;
    		//遍历 每八个字符一循环
    		for (int i = 0; i < sb.length(); i+=8) {
    			//如果是最后一次循环,字符串长度很可能不是八的整数倍,从而不足八位,额外处理。
    			if(count==byteZip.length-1) {
    				byteZip[count] = (byte)Integer.parseInt(sb.substring(i),2);
    				break;
    			}
    			//如果不是最后一次循环 就每八个字符生成一个byte
    			byteZip[count++] = (byte)Integer.parseInt(sb.substring(i,i+8),2);
    		}
    		//返回生成byte[] 此时已经是压缩完毕的byte数组,字节远小于压缩前。
    		return byteZip;
    	}
    

    文件解压专用,将文件转换成byte数组,再将压缩后的byte转换成文件

    	/**
    	 * 传入压缩后的byte[]和生成的huffman编码表生成指定路径下的压缩文件
    	 * @param bytesZip
    	 * @return void
    	 * @throws IOException 
    	 */
    	private static void bytesZipDstFile(byte[] bytesZip,Map<Byte,String> huffmanCodes,String dstFile) throws IOException {
    		//读取文件
    		FileOutputStream fos = new FileOutputStream(dstFile);
    		//加缓冲流
    		BufferedOutputStream bos = new BufferedOutputStream(fos);
    		//转对象流
    		ObjectOutputStream oos = new ObjectOutputStream(bos);
    		//将压缩后的数据写出到byte数组
    		oos.writeObject(bytesZip);
    		//刷新
    		oos.flush();
    		//将赫夫曼编码表也写出到指定路径下
    		oos.writeObject(huffmanCodes);
    		//刷新
    		oos.flush();
    		//关闭流
    		oos.close();
    		
    		bos.close();
    	}
    	
    	/**
    	 * 传入文件路径返回此文件的byte[] 压缩调用
    	 * @param srcFile
    	 * @return byte[]
    	 * @throws IOException
    	 */
    	private static byte[] srcFileBytes(String srcFile) throws IOException {
            
            FileInputStream fis = new FileInputStream(srcFile);
    
            BufferedInputStream bis = new BufferedInputStream(fis);
            //创建适宜长度数组
            byte[] bytes = new byte[bis.available()];
            //读取目标路径文件到byte数组
            bis.read(bytes);
            //关闭流
            bis.close();
            
            return bytes;
    	}
    
    • 整合代码
      压缩字节数组byte[]
    	/**
    	 * 数据压缩 传入需要解压的字节数组
    	 * @param bytes
    	 * @return byte[] 压缩并返回压缩后的字节数组
    	 */
    	public static byte[] huffmanZip(byte[] bytes) {
    		//统计每个字符出现的次数返回list
    		List<Note> listNote = getNotes(bytes);
    		//生成对应Huffman树返回根结点
    		Note note = huffmanTree(listNote);
    		//根据Huffman树生成对应Huffman编码表
    		Map<Byte,String> huffmanCodes = getCodes(note);
    		//压缩并返回
    		return zip(bytes,huffmanCodes);
    	}
    

    压缩指定路径文件

    	/**
    	 * 文件压缩
    	 * @param srcFile 目标文件
    	 * @param zipFile 压缩文件
    	 * @throws IOException
    	 */
    	public static void zipFile(String srcFile,String zipFile) throws IOException {
    		//读入目标文件返回byte[]
    		byte[] bytes = srcFileBytes(srcFile);
    		//传入压缩前的byte[]返回压缩后的byte[]
    		byte[] bytesZip = huffmanZip(bytes);
    		//传入压缩后的byte[]和生成的huffman编码表生成指定路径下的压缩文件
    		bytesZipDstFile(bytesZip,huffmanCodes,zipFile);
    	}
    

    测试

    压缩G盘Huffman目录下的一个文本
    在这里插入图片描述

    测试代码

    	//压缩测试
    	@Test
    	public void test1() {
    		String srcFile = "G://Huffman/Java.txt";
    		String zipFile = "G://Huffman/爪哇.zip";
    		try {
    			zipFile(srcFile,zipFile);
    			System.out.println("压缩成功");
    		} catch (IOException e) {
    			e.printStackTrace();
    		}
    	}
    

    测试结果
    在这里插入图片描述
    大小对比
    在这里插入图片描述

    ↓↓↓↓↓↓ 基于赫夫曼编码的数据压缩部分完结,下面是解压部分链接 ↓↓↓↓↓↓

    数据结构——赫夫曼编码实现数据压缩与解压原理剖析,附源码(下)

    展开全文
  • Verilog上机实验题目4:哈夫曼编码

    千次阅读 2019-04-16 21:41:18
    相关文章: [Verilog上机实验题目1:8位数字显示简易频率计] ...要求对一段数据序列进行哈夫曼编码,使得平均码长最短,输出各元素编码编码数据序列。 组成序列元素是[0-9]这10个数字,每个数字其对应...
  • 霍夫曼编码,Huffman

    千次阅读 2005-12-08 19:11:00
    下面引证一个定理,该定 理保证了按字符出现概率分配码长,可使平均码长最短。 定理:在变字长编码中,如果码字长度严格按照对应符号出现概率大小逆序排列,则其平 均码字长度为最小。 现在通过一个实例来
  • Huffman编解码算法及matlab实现

    热门讨论 2011-11-22 11:40:55
    霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编码算法。其编码思想是将较长的编码码字分配给较小概率的信源输出符号,而将较短的编码码字分配给较大概率的信源输出。文章详细描述了Huffman编解码...
  • 哈夫曼编码是依据信源字符出现的概率大小来构造代码,对出现概率较大的信源字符,给予较短码长,而对于出现概率较小的信源字符,给予较长的码长,最后使得编码的平均码字最短。其的编码步骤如下:(1)将信源符号...
  • 编码算法

    千次阅读 2019-07-16 21:34:22
    信息熵为信源无损编码平均码长的下限(最短码长) 公式理解:编码一个符号最佳bit长度是-logP,P是这个符号出现概率;一段信息长度就是所有符号长度求期望。 熵编码的基本思想: 尽可能减少信源冗余...
  • 编码概念

    2020-01-29 16:28:27
    信息熵为信源无损编码平均码长的下限(最短码长) 公式理解:编码一个符号最佳bit长度是-logP,P是这个符号出现概率;一段信息长度就是所有符号长度求期望。 熵编码的基本思想: 尽可能减少信源冗余...
  • 目录序最优性(Optimality)二元Huffman码Huffman平均码长和最优性证明 元Huffman码与源扩展序这篇文章主要是对教材第二个chapter讨论。...当初在学习时候,一直有个疑问——单独来论最短平均码长,Huf...
  • Hufman算法C#实现代码

    2009-02-13 13:45:01
    所有可能的惟一可译码中,此码的平均码长最短。 下面给出二元 Huffman 码的编码方法,算法步骤如下: i). 将q 个信源符号按概率分布 Pi 的大小,从大到小排列: P1 >= P2 >= P3 >= ... >= Pq ii). 用0 和1 分别...
  • Huffman编码属于无损压缩编码,且所编得的码为即时码,虽然编码方式不唯一,但是平均码长是确定且最短的。该编码方式广泛用在JPEG、MPEG等各种标准中、 Huffman码的原理非常简单,就是给概率大的码字分配短码,而给...
  •  平均码长=每个码长*频度 流水线计算    流水线周期值等于最慢那个指令周期  流水线执行时间=首条指令执行时间+(指令总数-1)*流水线周期值  流水线吞吐率=任务数/完成时间  流水线加速比=不采用流水线...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

平均码长最短的编码是