精华内容
下载资源
问答
  • 用C++进行哈夫曼编码计算信源熵及编码效率 统计各种概率
  • 哈夫曼编码

    千次阅读 2020-12-21 17:08:34
    上一篇文章中提到数据结构:哈夫曼树,今天接着学习由哈夫曼提出编码方式,一种程序算法 简称:哈夫曼编码 在线转码工具:https://tool.lu/hexconvert/ 一、什么是哈夫曼编码? 与哈夫曼树一样,会不会有小伙伴对...

    上一篇文章中提到数据结构:哈夫曼树,今天接着学习由哈夫曼提出编码方式,一种程序算法 简称:哈夫曼编码

    在线转码工具:https://tool.lu/hexconvert/

    一、什么是哈夫曼编码?

    与哈夫曼树一样,会不会有小伙伴对哈夫曼编码很陌生,有疑惑

    问题疑惑
    1.哈夫曼编码是做什么的?有什么用?
    2.为什么要使用哈夫曼编码?使用别的编码行不行?

    哈夫曼编码是做什么的?有什么用?

    • 哈夫曼(Huffman)编码算法

      它是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法:根据文本字符出现的频 率,重新对字符进行编码

      那么就会有小伙伴说:什么是数据压缩?什么是字符编码?

    • 字符编码压缩介绍

      在我们的世界里,我们可以看到漂亮的图像、好听的声音、震撼的视频等等这些精彩内容。但是对于计算机说,它的世界里只有二进制的 0 和 1。
      在这里插入图片描述
      因此在数字电子电路中,逻辑门的实现直接应用了二进制,因此现代的计算机和依赖计算机的设备里都用到二进制。

    那么在二进位电脑系统中,存储的单位有:bit、kb、mb、gb

    bit 电脑记忆体中最小的单位,每一bit 只代表0 或 1 的数位讯号
    在这里插入图片描述
    Byte由八个 bits 所组成,可代表:字元(AZ)、数字(09)、或符号(,.?!%&±*/)
    在这里插入图片描述
    当记忆体容量过大时,位元组(byte)这个单位就不够用,因此就有千位元组的单位KB出现,以下乃个记忆体计算单位之间的相关性:

    • 1 Byte = 8 Bits
    • 1 KB = 1024 Bytes
    • 1 MB = 1024 KB
    • 1 GB = 1024 MB
      我们现在在计算机上看到的一切的图像、声音、视频等内容,都是由二进制的方式进行存储的
      在这里插入图片描述
      简单来讲,我们把信息转化为二进制的过程可以称之为编码

    编码方式从长度上来分大致可以分为两个大类:

    • 定长编码表明:段与段之间长度相同,没说明是多长。
    • 变长编码表明:段与段之间的长度不相同,不定义具体有多长。

    请注意!这里并没有标明是多长!这会导致无法区分编码信息与文件内容的分离!造成乱码!

    • 自然语言的分隔问题

       民可使由之不可使知之 ——_出自《论语 第八章 泰伯篇》_
      

    这么一串十个字要如何去分隔并解释呢?
    断法解释一:

    民可使由之,不可使知之。
    解释:你可以去驱使你的民众,但不可让他们知道为什么(不要去教他们知识)
    

    断法解释二:

    	民可,使由之;不可,使知之。
    解释:民众可以做的,放手让他们去做;不会做的,教会他们如何去做(又或:不可以去做的,让他们明白为何不可以)
    

    显然,以上的文字是以某种定长或变长的方式组合在一起的,但是关于它们如何分隔的信息则被丢弃了,于是在解释时就存在产生歧义可能了。

    举个栗子,假如我们对 「pig」 进行自定义编码,使用定长编码,为了方便,采用了十进制,原理与二进制是一样的。
    在这里插入图片描述

    假设我们现在有文件,内容是:00080008

    假如定长 2 位是唯一的编码方案,用它去解码就会得到:「pipi」
    假如定长 4 位是唯一的编码方案,用它去解码就会得到:「ii」

    在这里插入图片描述
    如果文件的内容并没有暗示它使用了何种编码!就会出现解释时存在产生歧义。

    这就好比孔夫子写下“民可使由之不可使知之”时

    并没有暗示它是5|5分隔(民可使由之|不可使知之)

    还是暗示它是2|3|2|3分隔(民可|使由之|不可|使知之)。

    其实当我们有字节这一基本单位后,我们就可以说得更具体:如定长一字节或者定长二字节。

    比如说ASCII码它是最早也是最简单的一种字符编码方案:使用定长一字节来表示一个字符

    • 示例编码认识差异

    其实现在我们的计算机的世界里编码总已经有很多种格式

    比如常见的: ASCII 、 Unicode 、 GBK 、 GB2312 、 GB18030 、 UTF-8 、 UTF-16 等等。
    在这里插入图片描述

    • ASCII编码介绍

    我们都知道在计算机的世界里只有二进制0和1,通过不同的排列组合,可以使用 0 和 1 就可以表示世界上所有的东西。

    是不是有我们中国"太极"的感觉。

    ——“太极生两仪,两仪生四象,四象生八卦
    

    而在计算机中:一字节 = 八位二进制数(二进制有0和1两种状态)
    因此一字节可以组合出二百五十六种状态。

    如果这二百五十六种状态每一个都对应一个符号,就能通过一字节的数据表示二百五十六个字符。

    美国人于是就制定了一套编码(其实就是个字典),描述英语中的字符和这八位二进制数的对应关系,这被称为 ASCII 码。
    在这里插入图片描述
    随着时代的发展,不仅美国人要对他们的英文进行编码,我们中国人也要对汉字进行编码。

    而早期的 ASCII 码的方案只有一个字节,对我们汉字文化而言是远远不够的

    • 编码的发展

    这点可怜的空间拿到中国来,它能编码的汉字量也就小学一年级的水平。

    这也就导致了不同的需求推动了发展,各种编码方案都出来了,彼此之间的转换也带来了诸多的问题。采用某种统一的标准就势在必行了,于是乎天上一声霹雳,Unicode登场!

    Unicode早期是作为定长二字节方案出来的。它的理论编码空间一下达到了64k

    不过对于可以只需要使用到一个字节的ASCII 码就可以表示的美国人来讲,让他们使用 Unicode ,多少还是不是很愿意的。

    比如 「he」 两个字符,用 ASCII 只需要保存成 6865 ( 16 进制),现在则成了 00680065 ,前面多的那两个 0 (用作站位)。

    基本上可以说是毫无意义,用 Unicode 编码的文本,原来可能只有 1KB 大小,现在要变成 2KB ,体积成倍的往上涨。

    可是更糟糕的事还在后头,我们中文可是字符集里面的大头。

    1.“茴字有四种写法”——上大人孔乙己
    2.据说有些新近整理的汉语字典收录的汉字数量已经高达10万级别!
    

    如果还是定长的方案,眼瞅着就要奔着四字节而去了,容量与效率的矛盾在这时候开始激化。

    • 容量与效率的矛盾

      1).所谓容量,这里指用几个字节表示一个字符,显然用的字节越多,编码空间越大,能表示更多不同的字符,也即容量越大。

      2).所谓效率,当表示一个字符用的字节越多,所占用的存储空间也就越大,换句话说,存储(乃至检索)的效率降低了。
      在这里插入图片描述
      如果说效率是阴,那么容量就是阳。
      我没还没忘记自小学语文老师就开始教导的,写作文要遥相呼应

    • 莫尔斯电码图

    看如图所示你就会发现,字母e只用了一个点(dot)来编码
    在这里插入图片描述
    其它字母可能觉得不公平,为啥我们就要录入那么多个点和划(dash)才行呢?这里面其实是有统计规律支撑的。e出现的概率是最大的

    • z你能想到什么?

       zoo大概很多人能想到,厉害一点可能还能想到zebra(斑马),Zuckerberg(扎克伯格),别翻		字典!你还能想到更多不?
      
    • e你能想到什么?

       含有的e的单词则多了去了。zebra中不就有个e吗,Zuckerberg中还两个e呢
      

    所以我们希望频率越高的词,编码越短,这样最终才能最大化压缩存储文本数据的空间。

    为什么要使用哈夫曼编码?使用别的编码行不行?

    上面提到常见的信息处理方式:定长编码与变长编码

    假设当前有一句话:i like like like java do you like a java(共40个字符,包括空格)

    • 那么按照定长编码处理,那么会变成什么呢?
      在这里插入图片描述
      我们发现最后存在计算机中(二进制)长度是:三百五十九
    • 那么按照变长编码处理,那么会变成什么呢?
      在这里插入图片描述
      假设我们将这串10010110100…发给别人,但是没有说明解码的方式,这时就会出现解释时存在产生歧义。

    比如说可能翻译成:"a a a aa a ",所以我们需要说明字符编码不能是其他字符编码的前缀,即不能匹配重复的编码。

    • 那么按照哈夫曼处理,那么会变成什么呢?
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      相比定长编码二进制的长度:三百五十九,哈夫曼二进制长度为:一百三十三

    那么相比定长编码二进制的长度优化了多少呢?:(359-133)/359=62.9%

    我们再将哈夫曼二进制转码对应的byte字符
    在这里插入图片描述
    那么相比原字符长度优化了多少呢?:(40-17)/40 = 57.5%

    一下将原字符40位变成17位, 这样的情况下,是不是我们想要的

    二、解析哈夫曼编码执行思路与过程

    上面我们采用"i like like like java do you like a java",做例子分析,那么我们现在分析分析哈夫曼编码思路

    1. 将字符串里的字符进行统计个数并转为Byte[]数组
    2. 根据字符的出现次数构建一颗哈夫曼树、次数为权值
    3. 根据哈夫曼树进行自定义哈夫曼编码实现
    4. 将原字符的所有哈夫曼编码构建成编码串
    5. 根据编码串进行补码->反码->原码构建新字符

    三、统计字符出现次数并构建哈弗曼树

    图解思路分析

    1. 获取传输的字符串:“i like like like java do you like a java”
    2. 获取各个字符对应的个数:d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9
    3. 按照上面的字符出现的次数构建成一颗哈夫曼树,出现的个数作为权值

    构建哈夫曼树的步骤思路

    • 将数列进行从小到大排序
    • 新数列的每个数看成最简单根节点的二叉树
    • 取出权值最小的两颗二叉树组成新的二叉树,为两最小的树之和
    • 将新二叉树以跟节点的权重值再次从小到大排序,不断重复步骤
      在这里插入图片描述

    构建哈夫曼树的代码思路

    • Node{data:存放数据,weight:权重,left和right}
    • 得到"i like like like java do you like a java"对应byte[]数组
    • 编写方法,将准备构建赫夫曼树的Node节点放到List:Node[data=97, weight=
      5],Node[data=32,weight = …
    • 通过List创建对应的哈夫曼树

    体现获取各个字符对应的个数:d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9

    比如说字符:a 应该是Node[data=‘a’, weight= 5],data为什么会是97而不是a?

    因为底层:字母等于ASCII数字

    构建哈夫曼树的代码实现
    那么第一步:创建节点Node{data:存放数据,weight:权重,left和right}

    class Nodedata implements Comparable<Nodedata>{
    
        Byte data; //存放数据(字符)本身,比如'a' =>97 '' =>32
        int weight; //权值,表示字符出现的次数
        Nodedata left;
        Nodedata right;
        public Nodedata(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
        @Override
        public int compareTo(Nodedata o) {
            return this.weight - o.weight;
        }
        @Override
        public String toString() {
            return "Nodedata[" +"data=" + data + ", weight=" + weight +']';
        }
    }
    

    第二步:得到"i like like like java do you like a java"对应byte[]数组

    public static void main(String[] args) {
         
         //得到`"i like like like java do you like a java"`对应byte[]数组
         String content = "i like like like java do you like a java";
         byte[] contentBytes = content.getBytes();
         System.out.println(contentBytes.length);
    }
    

    第三步:编写方法,将准备构建赫夫曼树的Node节点放到List

    private static List<Nodedata> getNodes(byte[] bytes){
        //1.创建一个ArrayList
        List<Nodedata> nodeslist = new ArrayList<Nodedata>();
        //2.遍历bytes,统计每一个byte出现的次数->map[key,value]
        Map<Byte,Integer> map = new HashMap<>();
        for(byte b :bytes){
            Integer items = map.get(b);
            if(items == null){
                map.put(b,1);
            }else{
                map.put(b, items + 1);
            }
        }
        //3.把每个键值对转为Node 对象,并放入nodeslist集合里
        for(Map.Entry<Byte,Integer> temp :map.entrySet()){
            nodeslist.add(new Nodedata(temp.getKey(),temp.getValue()));
        }
        return nodeslist;
    }
    

    第四步:通过List创建对应的哈夫曼树

    private static Nodedata createHaffman(List<Nodedata> nodedataList){
        while(nodedataList.size() >1){
            //排序从小到大
             Collections.sort(nodedataList);
             /**
             *  操作思路 
             *  1.取出两个权值最小的节点二叉树 
             *  2.根据两个权值最小的二叉树构建成一个新的二叉树
             *  3.删除原先两个权值最小的节点二叉树
             *  4.将新的二叉树放入队列,并构建新的队列
             *  5.新的队列进行从小到大排序
             */
             //取出第一个权值最小的二叉树
             Nodedata leftNode = nodedataList.get(0);
             //取出第二个权值最小的二叉树
             Nodedata rightNode = nodedataList.get(1);
             //根据两个权值最小的二叉树构建成一个新的二叉树 同时构建连接
             Nodedata parentNode  = new Nodedata(null,leftNode.weight + rightNode.weight);
             parentNode.left = leftNode;
             parentNode.right = rightNode;
             //删除原先两个权值最小的节点二叉树
             nodedataList.remove(leftNode);
             nodedataList.remove(rightNode);
             //将新的二叉树放入队列,并构建新的队列
             nodedataList.add(parentNode);
         }
        return nodedataList.get(0);
    }
    

    测试检查是否满足代码思路

    检查是否Byte[]长度:40

    public static void main(String[] args) {
         
         //得到`"i like like like java do you like a java"`对应byte[]数组
         String content = "i like like like java do you like a java";
         byte[] contentBytes = content.getBytes();
         System.out.println("byte[]数组长度为:"+contentBytes.length);
    }
    
    运行结果如下:
    byte[]数组长度为:40
    

    检查字符个数:d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9

    public static void main(String[] args) {
         
         //将准备构建哈弗曼树的Node节点放到List:Node[data=97, weight= 5],Node[data=32,weight = .....
        List<Nodedata> datalist = getNodes(contentBytes);
        for(Nodedata data : datalist){
            System.out.println(data);
        }
    }
    运行结果如下:
    Nodedata[data=32, weight=9]
    Nodedata[data=97, weight=5]
    Nodedata[data=100, weight=1]
    Nodedata[data=101, weight=4]
    Nodedata[data=117, weight=1]
    Nodedata[data=118, weight=2]
    Nodedata[data=105, weight=5]
    Nodedata[data=121, weight=1]
    Nodedata[data=106, weight=2]
    Nodedata[data=107, weight=4]
    Nodedata[data=108, weight=4]
    Nodedata[data=111, weight=2]
    

    在这里插入图片描述
    Nodedata 节点添加前序遍历,添加哈弗曼树方法

    class Nodedata implements Comparable<Nodedata>{
    
         //省略实体类代码
         //前序遍历方法
         public void preOrder(){
            System.out.println(this);
            if(this.left != null){
               this.left.preOrder();
            }
            if(this.right != null){
               this.right.preOrder();
            }
        }
    }
    
    private static void preOrder(Nodedata root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("哈弗曼树为空!");
        }
    }
    

    检查前序遍历哈弗曼树,查看是否图一致:40->17->8->4->4->2->2->9…

    在这里插入图片描述

    public static void main(String[] args) {
         
         //获取哈弗曼树的根节点
         Nodedata root = createHaffman(datalist);
         //遍历哈弗曼树
         preOrder(root);
    }
    运行结果如下:
    Nodedata[data=null, weight=40]
    Nodedata[data=null, weight=17]
    Nodedata[data=null, weight=8]
    Nodedata[data=108, weight=4]
    Nodedata[data=null, weight=4]
    Nodedata[data=106, weight=2]
    Nodedata[data=111, weight=2]
    Nodedata[data=32, weight=9]
    Nodedata[data=null, weight=23]
    Nodedata[data=null, weight=10]
    Nodedata[data=97, weight=5]
    Nodedata[data=105, weight=5]
    Nodedata[data=null, weight=13]
    Nodedata[data=null, weight=5]
    Nodedata[data=null, weight=2]
    Nodedata[data=100, weight=1]
    Nodedata[data=117, weight=1]
    Nodedata[data=null, weight=3]
    Nodedata[data=121, weight=1]
    Nodedata[data=118, weight=2]
    Nodedata[data=null, weight=8]
    Nodedata[data=101, weight=4]
    Nodedata[data=107, weight=4]
    

    那么我们前面分析了如何将字符转为哈弗曼树的思路与代码

    下面看看如何将根据哈夫曼树进行构成自定义哈夫曼编码。

    四、根据哈夫曼树自定义哈夫曼编码

    • 根据哈夫曼树我们来自定义编码规则:向左为0、向右为1
    • 这样根据上面如图所示,定义的字符编码如下:[o: 0011 u: 11001 d: 11000 y: 11010 i: 101 a:
      100 k: 1111 e: 1110 j: 0010 V: 11011 I: 000 (空格):01]
      在这里插入图片描述
      有没有发现哈弗曼树的节点编码它是前缀编码:不是是其他字符编码的前缀,即匹配不到重复的编码。

    根据哈夫曼树自定义哈夫曼编码代码思路分析

    • 使用StringBuilder记录所经过的路径:'a’的路径是:1->1->0
    • 使用Key:Value 键值的方式存放对应的字符:路径;比如:(a:1000)、(j:0010)、(o:0011)
    • 字符特点:data !=null (属于叶子节点)
    • 假设查询字符v的路径,发现左递归不符合后还需要进行右递归判断

    根据哈夫曼树自定义哈夫曼编码代码实现

    //将哈夫曼编码以Key:Vale形式存放
    //比如说32->01 97->100 100->11000 等等[形式]
    static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();
    //2.在生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder 存储某个叶子结点的路径
    static StringBuilder stringBuilder = new StringBuilder();
    
    /**
     * 1.功能:将传入的node结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合 * @param node 传入节点
     * @param code 路径:左节点是0 右节点是1
     * @param stringBuilder 用于拼接路径
     */
     private static void getCodes(Nodedata node,String code,StringBuilder stringBuilder){
        StringBuilder str = new StringBuilder(stringBuilder);
        //将code加入到str 总
        str.append(code);
        if(node!=null){
            //字符特点:`data !=null `(属于叶子节点)
            if(node.data ==null){//(属于非叶子节点)
             //向左递归
             getCodes(node.left,"0",str);
             //向右递归
             getCodes(node.right,"1",str);
        }else{
             //`使用Key:Value 键值`的方式存放对应的`字符:路径;`比如:`(a:110)、(j:0000)、(o:1000)`
             huffmanCodes.put(node.data,str.toString());
         }
      }    
    }
    

    我们优化一下代码,实现传入根节点就可以返回哈夫曼编码

    private static Map<Byte,String> getCodes(Nodedata node){
         //根节点为空则不做处理
         if(node == null){
            return null;
         }
         //向左递归
         getCodes(node.left,"0",stringBuilder);
         //向右递归
         getCodes(node.right,"1",stringBuilder);
         return huffmanCodes;
    }
    

    我们进行运行测试看看,是否欲思路一致生成编码

    public static void main(String[] args) {
    
        //将哈夫曼树生成哈夫曼编码
        //getCodes(root,"",stringBuilder);
        
        //执行优化代码
        getCodes(root);
    }
    
    运行结果如下:
    生成的哈夫曼编码表:{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    

    注意:不同的排序方式会生成不同的哈弗曼树,所造成的哈夫曼编码也不一样,但WPL是一致

    五、将原字符的所有哈夫曼编码构建成编码串

    我们将"i like like like java do you like a java"字符串,即生成对应的哈夫曼编码数据(如下)
    在这里插入图片描述
    将原字符串转为编码串思路分析

    • 将字符串"i like like like java do you like a java"转为对应的Byte[]数组
    • 使用StringBuilder追加存储byte字符的对应字符路径

    将原字符串转为编码串思路分析代码实现

    private static void zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
         //1.利用huffmanCodes将bytes 转成赫夫曼编码对应的字符串
         StringBuilder stringBuilder = new StringBuilder();
         //遍历bytes数组
         for(byte b: bytes) {
            stringBuilder.append(huffmanCodes.get(b));
         }
         System.out.printf("stringBuilder=" + stringBuilder.toString());
         System.out.print("\n stringBuilder的长度=" + stringBuilder.length());
    }
    

    代码测试

    public static void main(String[] args) {
    
        //得到`"i like like like java do you like a java"`对应byte[]数组
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("byte[]数组长度为:"+contentBytes.length);
        //将准备构建哈弗曼树的Node节点放到List:Node[data=97, weight= 5],Node[data=32,weight = .....
        List<Nodedata> datalist = getNodes(contentBytes);
        //获取哈弗曼树的根节点
        Nodedata root = createHaffman(datalist);
        //将哈夫曼树生成哈夫曼编码Key:Value
        getCodes(root);
        //将Byte[]数组转为自定义的哈夫曼编码字符路径
        zip(contentBytes,huffmanCodes);
    }
    
    运行结果如下:
    byte[]数组长度为:40
    stringBuilder=1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    stringBuilder的长度=133
    

    我们将"i like like like java do you like a java"

    转为编码串相比之前定长编码优化了多少呢?:(359-133)/359=62.9%
    在这里插入图片描述

    六、将编码串进行补码->反码->原码构建新字符

    那么如何将长度一百三十三的二进制串转为新的字符呢?

    在讲编码串进行补码->反码->原码构建新字符前,先解释了解了解不同的进制

    相同的数字有不同的样子

    在计算机的世界中就分两种人:认识二进制和不认识二进制
    

    上面我们介绍到我们看到的漂亮的图像、好听的声音、震撼的视频等等这些精彩内容。但是对于计算机说,它的世界里只有二进制的 0 和 1。
    在这里插入图片描述

    • 所有数字在计算机底层都以二进制形式存在
    • 对于整数有不同表达方式:二进制、十进制、八进制、十六进制
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      二进制与十进制的说明
      我们使用Byte字符的二进制做演示,首先我们直观一点举例正数说明
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      以此类推…那么十进制转二进制该怎么做呢?来看看规律
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      有没有发现?从右开始往左是20(二的零次方)、21(二的一次方)、22(二的平方)、23(二的三次方)
      在这里插入图片描述
      根据前面知识点,你知道:01101110的十进制是多少么?

    在这里插入图片描述
    那么我们说Byte表示 -128 ~127 ,那么0和1 是怎么表示正数和负数的呢?
    在这里插入图片描述
    我们现在知道二进制的最高位:0 正数 1-负数 ,那么对于整数还要提提三个码:原码、反码、补码
    在这里插入图片描述
    那么我们思考一下:在计算机中: -14 是什么样的呢?

    接下来看看负数的解析图:十进制:14、二进制:00001110
    在这里插入图片描述
    那么我们现在反推一下:10111011 转为十进制是多少呢?

    • 我们刚刚提到计算机底层都以补码方式存储
    • 我们刚刚观察知道最高位: 0 - 正数、1-负数
    • 而负数则是补码的形式,那么思路反推:补码->反码->原码
      在这里插入图片描述
      接下来我相信大家都了解了什么是原码、反码、补码了

    上面我们将字符串"i like like like java do you like a java" 转为了自定义的哈弗曼编码串
    在这里插入图片描述
    接下来我们创建Byte[] huffmanCodeBytes,处理哈夫曼编码串,以八位为一组对应一个Byte 放入huffmanCodeBytes中
    在这里插入图片描述
    在这里插入图片描述

    转为新字符代码的思路分析

    • 每八位对应一个Byte,所以133 % 8,使用循环每次 i + 8
    • 因为每次 i + 8 所以需要使用变量index 记录对应的第几位Byte
    • 使用(byte)Integer.parInt(string,radix)转码

    转为新字符代码的代码实现

    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1.利用huffmanCodes将bytes 转成赫夫曼编码对应的字符串
         StringBuilder stringBuilder = new StringBuilder();
         //遍历bytes数组
         for(byte b: bytes) {
            stringBuilder.append(huffmanCodes.get(b));
         }
         //2.1010100010111111...思路:补码->反码->原码->转成Byte
         int len;
         if(stringBuilder.length() %8 == 0){
             len = stringBuilder.length() /8;
         }else{
             len = stringBuilder.length() /8 + 1;
         }
         //3.创建存储压缩后的byte数组
         byte[] huffmanCodeBytes = new byte[len];
         int index = 0;//记录是第几个byte
         for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长+8
             String strByte;
             if(i+8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder .substring(i);
             }else {
                strByte = stringBuilder .substring(i, i + 8);
             }
             //将strByte转成一个byte ,放入到huffmanCodeBytes
             huffmanCodeBytes[index] = (byte)Integer .parseInt(strByte, 2);
             index++;
        }
        return huffmanCodeBytes;
    }
    
    public static void main(String[] args) {
        //得到`"i like like like java do you like a java"`对应byte[]数组
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("byte[]数组长度为:"+contentBytes.length);
        
        //将准备构建哈弗曼树的Node节点放到List:Node[data=97, weight= 5],Node[data=32,weight = .....
        List<Nodedata> datalist = getNodes(contentBytes);
        
        //获取哈弗曼树的根节点
        Nodedata root = createHaffman(datalist);
        
        //将哈夫曼树生成哈夫曼编码
        getCodes(root);
        
        byte[] huffmanCodeBy =zip(contentBytes,huffmanCodes);
        System.out.println(Arrays.toString(huffmanCodeBy));
    }
    
    运行结果如下:
    byte[]数组长度为:40
    [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    

    在这里插入图片描述
    那么相比原字符长度优化了多少呢?:(40-17)/40 = 57.5%

    一下将原字符40位变成17位

    七、封装直接返回新符号Byte[]方法

    根据前面的分析,我们调用的方法比较多也比较臃肿,每次测试需要

    • 将字符串转为Byte数组,并统计个数
    • 根据字符出现次数作为权重,构建哈弗曼树
    • 根据哈弗曼树生成自定义哈弗曼编码
    • 将原字符的所有哈夫曼编码构建成编码串
    • 根据编码串进行补码->反码->原码构建新字符

    现在呢,我们将封装这些方法方便我们调用,我们的目的是获取到新字符组

    //使用一个方法将需要的方法疯转起来,方便调用
    private static  byte[] haffmanZip(byte[] bytes){
        //将准备构建哈弗曼树的Node节点放到List:Node[data=97, weight= 5],Node[data=32,weight = .....
         List<Nodedata> datalist = getNodes(bytes);
         //根据字符出现次数作为权重,构建哈弗曼树
         //获取哈弗曼树的根节点 
         Nodedata root = createHaffman(datalist);
         //根据哈夫曼树进行自定义哈夫曼编码实现
         Map<Byte,String> huffmanCodes = getCodes(root);
         //将原字符的所有哈夫曼编码构建成编码串
         //根据编码串进行补码->反码->原码构建新字符
         byte[] huffmanCodeBy =zip(bytes,huffmanCodes);
         return huffmanCodeBy;
    }
    
    public static void main(String[] args) {
    
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("byte[]数组长度为:"+contentBytes.length);
        byte[] huffmanCodeBy =haffmanZip(contentBytes);
        System.out.println(Arrays.toString(huffmanCodeBy));
        System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);
    }
    
    
    运行结果如下:
    byte[]数组长度为:40
    [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    压缩后的byte[]数组长度为:17
    

    八、将新字符解码转为原字符串

    我们已经将"i like like like java do you like a java"包括空格在内的四十个字符

    压缩成[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]只有十七位的新字符。

    那么假如我们将这串新字符发给对方

    对方如何解码成"i like like like java do you like a java"呢?
    在这里插入图片描述
    [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]是怎么来的?

    • 将长度为133的编码串 % 8 再进行补码->反码->原码

    那么我们现在获取到新字符后需要使用逆向思维获取原补码

    我们可以使用Integer.toBinaryString()方法将byte转成二进制

    /**
     *将一个byte转成-个二进制的字符串 
     * @param b
     * @return
     */
    private static String byteToBitString(byte b) {
        //使用变量保存b
         int temp = b;//将b转成int
         String str = Integer.toBinaryString(temp);
         return str;
    }
    

    我们使用 -1 进行测试这个方法看看

    //测试一把byteToBitString方法
    System.out.println(byteToBitString((byte)-1));
    
    运行结果如下:
    str=11111111111111111111111111111111
    

    很遗憾,我们发现返回的是int 的32位补码。注意是:补码

    按理说我们应该是从133 % 8获取的新字符,现在应该也是转为8位的补码,而不是32位

    /**
     *将一个byte转成-个二进制的字符串 * @param b
     * @return
     */
    private static String byteToBitString(byte b) {
        //使用变量保存b
     int temp = b;//将b转成int
     String str = Integer.toBinaryString(temp);
     return str.substring(str.length() -8);
    }
    

    那么现在就可以了吗?其实并不然还有一个补位的问题!比如说我现在输入 1
    在这里插入图片描述
    当是正数的时候,当前stu =1 则需要补位、否则是无法完成截取操作的

    /**
     *将一个byte转成-个二进制的字符串 * @param b
     * @return
     */
    private static String byteToBitString(byte b) {
         //使用变量保存b
         int temp = b;//将b转成int
         //如果是正数我们还存在补高位
         temp |= 256;
         String str = Integer.toBinaryString(temp);
         return str.substring(str.length() -8);
    }
    
    运行结果如下:
    00000001
    

    ???

    可能会有小伙伴会问到 temp |=256 是什么意思???为什么要|=256
    在这里插入图片描述
    这就涉及到知识点二进制的运算符了,两个二进制对应位为0时该位为0,否则为1
    在这里插入图片描述
    这样我们输入十进制:1 的时候,才能进行截取长度,否则不满足

    /**
     *将一个byte转成-个二进制的字符串
     * @param flag 标志是否需要补高位、如果是最后一个字节则无需补高位
     * @param b 传入的byte
     * @return 返回b对应的二进制串(按补码返回)
     */
     private static String byteToBitString(boolean flag,byte b) {
         //使用变量保存b
         int temp = b;//将b转成int
         if(flag){
            //如果是正数我们还存在补高位
            temp |= 256;
         }
         String str = Integer.toBinaryString(temp);
         if(flag){
           return str.substring(str.length() -8);
         }else{
           return str;
         }
    }
    

    根据八位为一组的思路,就会发现最后一个byte字节就无需补高位

    • 将新字符解码转为原字符串思路分析
    • 找到记录原字符byte转为自定义哈夫曼编码Map
    • 使用StringBuilder记录新字符组的补码
    • 根据自定义哈夫曼编码Map反获取(编码:字符)组成新map
    • 根据StringBuilder匹配新map获取对应字符

    第一步:使用StringBuilder记录新字符组的补码

    /**
     *  @param huffmanCodes 哈夫曼编码表map
     * @param huffmanBytes 哈夫曼得到的字节数组
     * @return就是原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //1.使用StringBuilder记录新字符组的补码
        StringBuilder stringBuilder =new StringBuilder();
        //循环记录
        for (int i=0;i<huffmanBytes.length;i++){
             byte b = huffmanBytes[i];
             //最后一个字符无需补位
             boolean flag = (i == huffmanBytes.length -1?true:false);
             stringBuilder.append(byteToBitString(!flag,b));
         }
         System.out.println("新字符组的补码串:"+stringBuilder.toString());
         System.out.println("新字符组的补码串长度:"+stringBuilder.length());
         return null;
     }
    
    public static void main(String[] args) {
    
        /得到`"i like like like java do you like a java"`对应byte[]数组
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("原byte[]数组长度为:"+contentBytes.length);
        byte[] huffmanCodeBy =haffmanZip(contentBytes);
        System.out.println("n开始进行哈夫曼编码压缩==============================n");
        System.out.println("压缩后的新字符数组:"+Arrays.toString(huffmanCodeBy));
        System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);
        decode(huffmanCodes,huffmanCodeBy);
    }
    
    运行结果如下:
    原byte[]数组长度为:40
    原字符数组经过自定义编码后的编码串:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    原字符数组经过自定义编码后的编码串长度:133
    
    开始进行哈夫曼编码压缩==============================
    
    压缩后的新字符数组:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    压缩后的byte[]数组长度为:17
    新字符组的补码串:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    新字符组的补码串长度:133
    

    第二步:找到记录原字符byte转为自定义哈夫曼编码Map、根据自定义哈夫曼编码Map反获取(编码:字符)组成新map

    /**
     * * @param huffmanCodes 哈夫曼编码表map
     * @param huffmanBytes 哈夫曼得到的字节数组
     * @return就是原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
         //1.使用StringBuilder记录新字符组的补码
         StringBuilder stringBuilder =new StringBuilder();
         //循环记录
         for (int i=0;i<huffmanBytes.length;i++){
            byte b = huffmanBytes[i];
            //最后一个字符无需补位
            boolean flag = (i == huffmanBytes.length -1?true:false);
            stringBuilder.append(byteToBitString(!flag,b));
         }
         //找到记录原字符byte转为自定义哈夫曼编码Map、根据自定义哈夫曼编码Map反获取原字符
         Map<String,Byte> map =new HashMap<String, Byte>();
         for(Map.Entry<Byte,String> item:huffmanCodes.entrySet()){
              map.put(item.getValue(),item.getKey());
         }
         System.out.println("根据自定义哈夫曼编码Map反获取(编码:字符)组成新map = "+map);
         return null;
     }
     
    运行结果如下:
    
    根据自定义哈夫曼编码Map反获取(编码:字符)组成新map = {000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106} 
    

    第三步:根据StringBuilder匹配新map获取对应字符

    在这里插入图片描述
    在这里插入图片描述

    /**
     * * @param huffmanCodes 哈夫曼编码表map
     * @param huffmanBytes 哈夫曼得到的字节数组
     * @return就是原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //1.使用StringBuilder记录新字符组的补码
         StringBuilder stringBuilder =new StringBuilder();
         //循环记录
         for (int i=0;i<huffmanBytes.length;i++){
            byte b = huffmanBytes[i];
            //最后一个字符无需补位
            boolean flag = (i == huffmanBytes.length -1?true:false);
            stringBuilder.append(byteToBitString(!flag,b));
         }
            //找到记录原字符byte转为自定义哈夫曼编码Map、根据自定义哈夫曼编码Map反获取原字符
         Map<String,Byte> map =new HashMap<String, Byte>();
         for(Map.Entry<Byte,String> item:huffmanCodes.entrySet()){
             map.put(item.getValue(),item.getKey());
         }
            //根据StringBuilder匹配新map获取对应字符
         List<Byte> list =new ArrayList<>();
         for (int j=0;j<stringBuilder.length();){    
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while(flag){
              String key =stringBuilder.substring(j,j+count);
              b = map.get(key);
              if(b == null){
                   count++;
              }else{
                   flag = false;
              }
            }
            list.add(b);
            j +=count;
         }
          //当for循环结束后,list就存放了字符串"i like like like java do you like a java"的所有字符
         //把集合里的数据放入byte[]中返回 byte[] b = new byte[list.size()];
         for (int k =0;k<b.length; k++){
                b[k]=list.get(k);
         }
         return b;
    }
    
    public static void main(String[] args) {
    
        /得到`"i like like like java do you like a java"`对应byte[]数组
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println("原byte[]数组长度为:"+contentBytes.length);
        byte[] huffmanCodeBy =haffmanZip(contentBytes);
        System.out.println("n开始进行哈夫曼编码压缩==============================n");
        System.out.println("压缩后的新字符数组:"+Arrays.toString(huffmanCodeBy));
        System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);
        byte[] source = decode(huffmanCodes,huffmanCodeBy);
        System.out.println("新字符数组经过根据新map获取对应字符:"+new String(source));
    }
    
    运行结果如下:
    
    根据自定义哈夫曼编码Map反获取(编码:字符)组成新map = {000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}
    新字符数组经过根据新map获取对应字符:i like like like java do you like a java
    

    九、最佳实践文件压缩与解压

    我们将这个图片文件,进行压缩实践看看
    在这里插入图片描述
    思路:读取文件–>得到哈夫曼编码表–>完成压缩

    /**
     *@paramsrcFile 希望压缩文件的全路径
     *@param dstFile 压综后将文件放到哪个目录
    */
    public static void zipFile(String srcFile, String dstFile) {
         //创建输出流
         OutputStream os = null;
         //对象输出流
         ObjectOutputStream oos;
         //创建文件的输入流
         FileInputStream is = null;
         try {
                //创建文件的输入流
             is = new FileInputStream(srcFile);
             //创建一个和源文 件大小一样的byte[ ]
             byte[] b = new byte[is.available()];
             //读取文件
             is.read(b);
             //直接对文件压缩
             byte[] bytes = haffmanZip(b);
             //创建文件的输出流,存放压缩文件
             os = new FileOutputStream(dstFile);
             //创建一个和文件流关联的ObjectOutputStream;
             oos = new ObjectOutputStream(os);
             //以对象流的方写入哈夫曼编码,为了方便恢复
             oos.writeObject(huffmanCodes);
         } catch (Exception e) {
                System.out.println(e.getMessage());
         } finally {
             try {
                is.close();
                oos.close();
                os.close();
             }catch (Exception e) {
                System.out.println(e.getMessage());
             }
        }
    }
    
    public static void main(String[] args) {
        //测试压编文件
        String srcFile = "d://src. bmp";
        String dstFile = "d://dst.zip";
        zipFile(srcFile, dstFile);
        System. out . println("压编文件ok~~");
    }
    

    在这里插入图片描述

    会出现无法打开并解压的方式,为什么呢?

    因为我们自定义属于自己的的压缩方式,所以解压也要用我们自己的方式去解压

    源文件大小:598kb
    压缩后的文件大小:76kb

    那么接下来我们编写自己的解压方式把

    思路:读取压缩文件(数据和哈弗曼编码表)–>完成解压

    //编写一个方法,完成对压缩文件的解压
    /**
     * @param zipFile 准备解压的文件
     * @param dstFile 将文件解压到哪个路径
    */
    public static void unZipFile(String zipFile, String dstFile) {
         //定义文件输入流
         InputStream is = null;
         //对象输出流
         ObjectInputStream ois = null;
         //创建输出流
         OutputStream os = null;
         try {
             //创建文件的输入流
             is = new FileInputStream(zipFile);
             //创建一个和文件流关联的ObjectOutputStream;
             ois = new ObjectInputStream(is);
             //读取byte数组 huffmanbytes
             byte[] huffmanBytes = (byte[])ois.readObject();
             //获取哈夫曼编码表
             Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
             //解码
             byte[] bytes =decode(huffmanCodes,huffmanBytes);
             //将恢复的原byte数组写入文件
             os = new FileOutputStream(dstFile);
             os.write(bytes);
         } catch (Exception e) {
                System.out.println(e.getMessage());
         } finally {
             try {
                os.close();
                ois.close();
                is.close();
             }catch (Exception e) {
                System.out.println(e.getMessage());
             }
        }
    }
    
    public static void main(String[] args) {
        
        //测试解压文件
        String zipFile = "d://dst. zip";
        String dstFile = "d://src2. bmp";
        unZipFile(zipFile, dstFile) ;
    }
    

    在这里插入图片描述

    展开全文
  • 这个代码是用C/C++实现哈夫曼编码并将编码输出。 文本为操作者输入,,对各字符进行频率统计,然后进行哈夫曼编码,并将编码结果输出,同时可求得平均码长。
  • 请依据哈夫曼编码的方法对如下的字符进行编码,并计算产生的码流的编码压缩效率: 练习一:“abcdaabbccaaabbbcfaaaabbbccdffeeeaaabbbcccdefabcde” 练习二:“i am a student i study iot subject in guangzhou ...
  • 静态哈夫曼编码的C++实现。

         哈夫曼编码分为动态和静态之分。静态哈夫曼编码需要统计和计算每个字段的权重(比如文本'A'字母出现的次数),效率会很低,特别是压缩大文件,基本是不现实的。只是,理解静态哈夫曼编码是基础,理解压缩和解压思想。

         本文使所使用的算法和构建思路跟我们通常的数据结构和算法书本里面的介绍思路是一致的,这个思路也是最原始和直观的,比较容易理解,本质上是一个经典的贪心算法例子。就是每次从各个子树中(原始的单个元素我们也看成是一棵只有root节点的一棵树),选择2个权重最大的或者权重最小,最大或者最小的为左子树,次大或者次小的为右子树,左右子树合并成一课树。当然,合并过程中出现的子树,它的权重是左右子树的权重之和。这样如此循环往复选取,直到最后只有一棵树,即生成哈夫曼编码树。有了编码树,每个叶子节点的编码也就明显了。压缩过程就是编码位域替换文本字段,解压缩就是扫描编码树和文件的位域,如果是0走到左子树,如果是1走到右子树,到了叶子节点,那么就解压出一个文本字段了。如此循环,即完整的解压出全部内容。

          为了完整理解该思路,我这边的实现并没有考虑效率等,完全模拟编解码的最原始的思路来实现,这样非常便于理解。实现思路是把字段的出现次数(权重)按从小到大排序,每次选择2个最小的构成二叉树,如此循环直到只剩最后一棵二叉树,即编码树。每个字段都是一个字节,为0-255的数字。

          创建二叉树后,这里需要遍历2遍编码树,才可以获取到每个字段的编码,关于这点,如果有效率更高的遍历方法,多谢告知。如下是实现代码。

    #include "HanfuMan.h"
    
    #define TEST_DATA_LEN 16
    
    void InsertSort(PDATA_INFO pDataInfo,int len,unsigned char data,unsigned short dataTimes);
    
    BOOL TestHanfuMan()
    {
    	BOOL bRet = FALSE;
    	unsigned char *p = (unsigned char*)new unsigned char[TEST_DATA_LEN];
    	if(!p)
    	{
    		return FALSE;
    	}
    	memset(p,0,TEST_DATA_LEN);
    
    	srand(time(NULL));
    	for(int i=0;i<TEST_DATA_LEN;i++)
    	{
    		p[i] = rand()%256; //随机生成数据内容
    	}
    
    	//统计0-255之间每个数字出现的次数
    	unsigned short times[256] = {0};
    	for(int i=0;i<TEST_DATA_LEN;i++)
    	{
    		times[p[i]]++; 
    	}
    
    	int count = 0;//统计有出现的数字个数
    	for(int i=0;i<256;i++)
    	{
    		if(times[i])
    		{
    			count++;
    		}
    	}
    
    	PDATA_INFO pDataInfo = (PDATA_INFO)new DATA_INFO[count];
    	if(!pDataInfo)
    	{
    		goto RET;
    	}
    	memset(pDataInfo,0,count*sizeof(DATA_INFO));
    
    	int len = 0;
    	for(int i=0;i<256;i++)
    	{
    		if(times[i])
    		{
    			//使用插入排序,把0-255之间出现的数字的次数进行从小到大排序
    			InsertSort(pDataInfo,len,i,times[i]);
    			len++;
    		}
    	}
    
    	PHANFUMAN_TREE tree = CreateHanfuManTree(pDataInfo,len);
    	EnumHanfuManCode(tree);
    	DestroyTree(tree);
    
    RET:
    	if(pDataInfo)
    	{
    		delete [] pDataInfo;
    	}
    	if(p)
    	{
    		delete [] p;
    	}
    
    	return bRet;
    }
    
    void InsertSort(PDATA_INFO pDataInfo,int len,unsigned char data,unsigned short dataTimes)
    {
    	if(0 == len)
    	{
    		pDataInfo[0].data = data;
    		pDataInfo[0].times = dataTimes;
    		return;
    	}
    
    	int inserIndex = 0;
    	//使用插入排序
    	for(inserIndex=0;inserIndex<len;inserIndex++)
    	{
    		if(dataTimes >= pDataInfo[inserIndex].times)
    		{
    			continue;
    		}
    		break;
    	}
    
    	for(int i=len-1;i>=inserIndex;i--)
    	{
    		memcpy(&pDataInfo[i+1],&pDataInfo[i],sizeof(DATA_INFO));
    	}
    	//插入新数据
    	pDataInfo[inserIndex].data = data;
    	pDataInfo[inserIndex].times = dataTimes;
    }
    
    void InsertSortTree(PHANFUMAN_TREE *pSubTree,int subTreeCount,PHANFUMAN_TREE insertTree)
    {
    	if(0 == subTreeCount)
    	{
    		pSubTree[0] = insertTree;
    		return;
    	}
    
    	int inserIndex = 0;
    	//使用插入排序
    	for(inserIndex=0;inserIndex<subTreeCount;inserIndex++)
    	{
    		if(insertTree->weight >= (pSubTree[inserIndex])->weight)
    		{
    			continue;
    		}
    		break;
    	}
    
    	for(int i=subTreeCount-1;i>=inserIndex;i--)
    	{
    		pSubTree[i+1] = pSubTree[i];
    	}
    	//插入新数据
    	pSubTree[inserIndex] = insertTree;
    }
    
    void RefreshSubTrees(PHANFUMAN_TREE *pSubTree,int subTreeCount,PHANFUMAN_TREE mergeTree)
    {
    	for(int i=2;i<subTreeCount;i++)
    	{
    		pSubTree[i-2] = pSubTree[i];
    	}
    	
    	//插入排序,按照权重的从小到大顺序排序
    	InsertSortTree(pSubTree,subTreeCount-2,mergeTree);
    }
    
    //合并2棵子树,pSubTree1的权重默认比pSubTree2的小
    PHANFUMAN_TREE MergeTree(PHANFUMAN_TREE pLeftSubTree,PHANFUMAN_TREE pRightSubTree)
    {
    	PHANFUMAN_TREE mergeRoot = new HANFUMAN_TREE;
    
    	if(!mergeRoot)
    	{
    		return NULL;
    	}
    
    	mergeRoot->data = 0;
    
    	pLeftSubTree->parent = mergeRoot;
    	mergeRoot->weight = pLeftSubTree->weight;
    	//pLeftSubTree 默认不为空
    	if(pRightSubTree)
    	{
    		mergeRoot->weight += pRightSubTree->weight;
    		pRightSubTree->parent = mergeRoot;
    	}
    
    	mergeRoot->parent = NULL;
    	mergeRoot->left = pLeftSubTree;
    	mergeRoot->right = pRightSubTree;
    
    	return mergeRoot;
    }
    
    //创建新树,用于创建叶子节点
    PHANFUMAN_TREE CreateLeaf(PDATA_INFO pDataInfo)
    {
    	PHANFUMAN_TREE leafTree = new HANFUMAN_TREE;
    
    	if(!leafTree)
    	{
    		return NULL;
    	}
    
    	leafTree->data = pDataInfo->data;
    	leafTree->weight = pDataInfo->times;
    
    	leafTree->parent = NULL;
    	leafTree->left = NULL;
    	leafTree->right = NULL;
    
    	return leafTree;
    }
    
    //创建哈夫曼编码树
    PHANFUMAN_TREE CreateHanfuManTree(PDATA_INFO pDataInfo,int len)
    {
    	if(len<=0)
    	{
    		return NULL;
    	}
    
    	int dataIndex = 0;
    	//最多只可能出现len+1/2个子树,用于保存编码过程可能出现的全部子树的根节点指针
    	PHANFUMAN_TREE *pSubTree = (PHANFUMAN_TREE*) new PHANFUMAN_TREE[(len+1)/2];
    	PHANFUMAN_TREE root = NULL;
    	int subTreeCount = 0; //子树的个数
    	HANFUMAN_SELECT_HELPER  selectHelper;
    
    	memset(pSubTree,0,sizeof(PHANFUMAN_TREE)*((len+1)/2));
    
    	while(dataIndex<len)
    	{
    		//对比数组中剩余未编码的数据和各个子树选择2个权重最小的,如果权重相同,优先选择子树中的
    		//由于数组和子树都已经按照从小到大的顺序,因此直接选取对比即可
    		if(subTreeCount>=2)
    		{
    			selectHelper.firstMinIndex = 0;
    			selectHelper.secondMinIndex = 1;	
    		}
    		else
    		{
    			if(subTreeCount>=1)
    			{
    				selectHelper.firstMinIndex = 0;
    			}
    		}
    
    		if(-1 == selectHelper.firstMinIndex)
    		{
    			selectHelper.firstMinIndex = dataIndex;
    			selectHelper.firstMinType = INDEX_TYPE_INFO;
    			if(++dataIndex<len)
    			{
    				selectHelper.secondMinIndex = dataIndex++;
    				selectHelper.secondMinType = INDEX_TYPE_INFO;
    			}
    		}
    		else
    		{
    			if(pDataInfo[dataIndex].times < (pSubTree[selectHelper.firstMinIndex])->weight)
    			{
    				selectHelper.secondMinIndex = selectHelper.firstMinIndex;
    
    				selectHelper.firstMinIndex = dataIndex;
    				selectHelper.firstMinType = INDEX_TYPE_INFO;
    
    				if( (++dataIndex<len) && ( pDataInfo[dataIndex].times < (pSubTree[selectHelper.secondMinIndex])->weight  ) )
    				{
    					selectHelper.secondMinIndex = dataIndex++;
    					selectHelper.secondMinType = INDEX_TYPE_INFO;
    				}
    			}
    			else
    			{
    				if( (-1==selectHelper.secondMinIndex) || (pDataInfo[dataIndex].times < (pSubTree[selectHelper.secondMinIndex])->weight))
    				{
    					selectHelper.secondMinIndex = dataIndex++;
    					selectHelper.secondMinType = INDEX_TYPE_INFO;
    				}
    			}
    		}//至此,已经选择出了2个最小权重的
    
    		if(INDEX_TYPE_TREE == selectHelper.firstMinType && INDEX_TYPE_TREE == selectHelper.secondMinType)
    		{
    			//合并2棵子树
    			PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],pSubTree[1]);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			RefreshSubTrees(pSubTree,subTreeCount,mergeTree);
    
    			subTreeCount--;
    		}
    		if(INDEX_TYPE_TREE == selectHelper.firstMinType && INDEX_TYPE_INFO == selectHelper.secondMinType)
    		{
    			PHANFUMAN_TREE newLeaf = CreateLeaf(&pDataInfo[selectHelper.secondMinIndex]);
    			if(!newLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],newLeaf);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			for(int i=1;i<subTreeCount;i++)
    			{
    				pSubTree[i-1] = pSubTree[i];
    			}
    
    			InsertSortTree(pSubTree,subTreeCount-1,mergeTree);//插入子树后,子树的数量不变
    		}
    		if(INDEX_TYPE_INFO == selectHelper.firstMinType && INDEX_TYPE_INFO == selectHelper.secondMinType)
    		{
    			PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    			if(!leftLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE rightLeaf = CreateLeaf(&pDataInfo[selectHelper.secondMinIndex]);
    			if(!leftLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,rightLeaf);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			InsertSortTree(pSubTree,subTreeCount,mergeTree);
    			subTreeCount++; //插入子树后,子树的数量+1
    		}
    		if(INDEX_TYPE_INFO == selectHelper.firstMinType && INDEX_TYPE_TREE == selectHelper.secondMinType)
    		{
    			if(-1 == selectHelper.secondMinIndex)
    			{
    				PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    				if(!leftLeaf)
    				{
    					exit(0);
    				}
    				PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,NULL);
    				if(!mergeTree)
    				{
    					exit(0);
    				}
    				InsertSortTree(pSubTree,subTreeCount,mergeTree);
    				subTreeCount++; 
    			}
    			else
    			{
    				PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    				if(!leftLeaf)
    				{
    					exit(0);
    				}
    				PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,pSubTree[selectHelper.secondMinIndex]);
    				if(!mergeTree)
    				{
    					exit(0);
    				}
    				for(int i=1;i<subTreeCount;i++)
    				{
    					pSubTree[i-1] = pSubTree[i];
    				}
    
    				InsertSortTree(pSubTree,subTreeCount-1,mergeTree);
    			}
    		}
    
    		selectHelper.Init();
    	}
    
    	//合并sub trees
    	while(subTreeCount>1)
    	{
    		//合并2棵子树
    		PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],pSubTree[1]);
    		if(!mergeTree)
    		{
    			exit(0);
    		}
    		RefreshSubTrees(pSubTree,subTreeCount,mergeTree);
    
    		subTreeCount--;
    	}
    
    	//最后子树中只剩下一课,这棵树即为编码树
    	PHANFUMAN_TREE tree = pSubTree[0];
    	delete [] pSubTree;
    	
    	return tree;
    }
    
    //释放树
    void DestroyTree(PHANFUMAN_TREE tree)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	DestroyTree(tree->left); //刪除左子树
    	DestroyTree(tree->right);//删除右子树
    
    	delete tree; //删除根节点
    	tree = NULL;
    }
    
    //通过叶子的父节点向上
    void PrintHanfuManCode(PHANFUMAN_TREE tree,int *codeLen)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	PHANFUMAN_TREE parent = tree->parent;
    	if(!parent)
    	{
    		return;
    	}
    
    	PrintHanfuManCode(parent,codeLen);
    	if(parent->left == tree)
    	{
    		(*codeLen)++;
    		printf("0");
    	}
    	else
    	{
    		(*codeLen)++;
    		printf("1");
    	}
    }
    
    
    //通过二次遍历编码树,枚举得到每个data的哈夫曼编码
    void EnumHanfuManCode(PHANFUMAN_TREE tree)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	//叶子节点
    	if(!tree->left && !tree->right)
    	{
    		int codeLen = 0;
    		printf("data value = 0x%2x    HanfuMan Code = ",tree->data);
    		PrintHanfuManCode(tree,&codeLen);
    		printf("   CodeLen = %d\r\n",codeLen);
    		return;
    	}
    	
    	if(tree->left)
    	{
    		EnumHanfuManCode(tree->left);
    	}
    
    	if(tree->right)
    	{
    		EnumHanfuManCode(tree->right);
    	}
    }
          头文件内容如下:

         

    #ifndef _HANFUMAN_H_
    #define _HANFUMAN_H_
    
    typedef struct _t_HANFUMAN_TREE
    {
    	unsigned char data;    //编码的数据值,0-255之间,如果不是叶子节点,设置为0
    	unsigned short weight; //编码数字的权重,可以是出现的概率,这里使用data出现的次数
    
    	_t_HANFUMAN_TREE* parent;
    	_t_HANFUMAN_TREE* left;
    	_t_HANFUMAN_TREE* right;
    }HANFUMAN_TREE,*PHANFUMAN_TREE;
    
    
    #define INDEX_TYPE_TREE 0x00
    #define INDEX_TYPE_INFO 0x01
    
    typedef struct _t_HANFUMAN_SELECT_HELPER
    {
    	_t_HANFUMAN_SELECT_HELPER()
    	{
    		Init();
    	}
    	void Init()
    	{
    		firstMinIndex = -1;
    		secondMinIndex = -1;
    		firstMinType = INDEX_TYPE_TREE; //默认值为子树类型
    		secondMinType = INDEX_TYPE_TREE; //默认值为子树类型
    	}
    	int firstMinIndex; 
    	int secondMinIndex;
    	unsigned char firstMinType;
    	unsigned char secondMinType;
    }HANFUMAN_SELECT_HELPER,*PHANFUMAN_SELECT_HELPER;
    
    typedef struct _t_DATA_INFO
    {
    	unsigned char data;  
    	unsigned short times; //data出现的次数
    }DATA_INFO,*PDATA_INFO;
    
    BOOL TestHanfuMan();
    
    //创建哈夫曼编码树
    PHANFUMAN_TREE CreateHanfuManTree(PDATA_INFO pDataInfo,int len);
    void EnumHanfuManCode(PHANFUMAN_TREE tree);
    void DestroyTree(PHANFUMAN_TREE tree);
    
    #endif
             测试例子如下:

    #include <Windows.h>
    #include <stdio.h>
    #include "HanfuMan.h"
    
    
    int main(int agrc,char* argv[])
    {
    	TestHanfuMan();
    	
    	getchar();
    	return 0;
    }

        


    展开全文
  • 静态哈夫曼编码的C++实现--使用哈夫曼编码树压缩和解压缩。

          压缩就是位域的操作,假设A对应0000,B对应1111,则AB压缩后为00001111即为0x0F,AB原本为2个字节,压缩后变为1个字节。其它数据类似一样的压缩操作即可。

          解压缩就是取出每一个位,如果是0,则走到哈夫曼编码树的左孩子,如果是1,则走到哈夫曼编码树的右孩子,接着判断是否走到了叶子节点,如果是,输出叶子节点对应的编码值即可。依次类推,解压出全部数据。

          如下的代码只是为了更好的演示压缩和解压过程,基本没有太多考虑效率等问题。

          

    #ifndef _HANFUMAN_H_
    #define _HANFUMAN_H_
    
    typedef struct _t_HANFUMAN_TREE
    {
    	unsigned char data;    //编码的数据值,0-255之间,如果不是叶子节点,设置为0
    	unsigned short weight; //编码数字的权重,可以是出现的概率,这里使用data出现的次数
    
    	_t_HANFUMAN_TREE* parent;
    	_t_HANFUMAN_TREE* left;
    	_t_HANFUMAN_TREE* right;
    }HANFUMAN_TREE,*PHANFUMAN_TREE;
    
    #define MAX_CODE_BYTES 16
    
    #define INDEX_TYPE_TREE 0x00
    #define INDEX_TYPE_INFO 0x01
    
    typedef struct _t_HANFUMAN_SELECT_HELPER
    {
    	_t_HANFUMAN_SELECT_HELPER()
    	{
    		Init();
    	}
    	void Init()
    	{
    		firstMinIndex = -1;
    		secondMinIndex = -1;
    		firstMinType = INDEX_TYPE_TREE; //默认值为子树类型
    		secondMinType = INDEX_TYPE_TREE; //默认值为子树类型
    	}
    	int firstMinIndex; 
    	int secondMinIndex;
    	unsigned char firstMinType;
    	unsigned char secondMinType;
    }HANFUMAN_SELECT_HELPER,*PHANFUMAN_SELECT_HELPER;
    
    typedef struct _t_DATA_INFO
    {
    	unsigned char data;  
    	unsigned short times; //data出现的次数
    }DATA_INFO,*PDATA_INFO;
    
    typedef struct _t_HANFUMAN_CODE_ITEM
    {
    	unsigned char data[MAX_CODE_BYTES]; //最长表示MAX_CODE_BYTES*8长度的编码位域  
    	unsigned short codeLen;//编码的位域长度
    }HANFUMAN_CODE_ITEM,*PHANFUMAN_CODE_ITEM;
    
    BOOL TestHanfuMan();
    
    //创建哈夫曼编码树
    PHANFUMAN_TREE CreateHanfuManTree(PDATA_INFO pDataInfo,int len);
    void EnumHanfuManCode(PHANFUMAN_TREE tree);
    void DestroyTree(PHANFUMAN_TREE tree);
    
    #endif

    #include <Windows.h>
    #include <iostream>
    #include <stdlib.h>
    #include <time.h>
    
    #include "HanfuMan.h"
    
    #define TEST_DATA_LEN 16
    
    void InsertSort(PDATA_INFO pDataInfo,int len,unsigned char data,unsigned short dataTimes);
    //哈夫曼编码,返回值为编码后的数据位数 一个字节有8位
    int HanfuManEncode(unsigned char* data,int dataLen,unsigned char **encodeData);
    //哈夫曼解压缩,返回值为解压缩后的数据字节数
    int HanfuManDecode(PHANFUMAN_TREE tree,unsigned char* data,int dataBitLen,unsigned char **decodeData);
    
    //编码表,用于0-255之间
    static HANFUMAN_CODE_ITEM g_HanfuManCodeTable[256] = {0};
    
    BOOL TestHanfuMan()
    {
    	BOOL bRet = FALSE;
    	unsigned char *p = (unsigned char*)new unsigned char[TEST_DATA_LEN];
    	if(!p)
    	{
    		return FALSE;
    	}
    	memset(p,0,TEST_DATA_LEN);
    
    	srand(time(NULL));
    	for(int i=0;i<TEST_DATA_LEN;i++)
    	{
    		p[i] = rand()%256; //随机生成数据内容
    	}
    
    	//统计0-255之间每个数字出现的次数
    	unsigned short times[256] = {0};
    	for(int i=0;i<TEST_DATA_LEN;i++)
    	{
    		times[p[i]]++; 
    	}
    
    	int count = 0;//统计有出现的数字个数
    	for(int i=0;i<256;i++)
    	{
    		if(times[i])
    		{
    			count++;
    		}
    	}
    
    	PDATA_INFO pDataInfo = (PDATA_INFO)new DATA_INFO[count];
    	if(!pDataInfo)
    	{
    		goto RET;
    	}
    	memset(pDataInfo,0,count*sizeof(DATA_INFO));
    
    	int len = 0;
    	for(int i=0;i<256;i++)
    	{
    		if(times[i])
    		{
    			//使用插入排序,把0-255之间出现的数字的次数进行从小到大排序
    			InsertSort(pDataInfo,len,i,times[i]);
    			len++;
    		}
    	}
    
    	PHANFUMAN_TREE tree = CreateHanfuManTree(pDataInfo,len);
    	EnumHanfuManCode(tree);
    
    	unsigned char *pEncode = NULL;
    	int encodeBitLen = HanfuManEncode(p,TEST_DATA_LEN,&pEncode); //编码数据
    	printf("Bytes Before encode = %d Bytes Arter encode = %d\r\n",TEST_DATA_LEN,(encodeBitLen+7)/8);
    
    	unsigned char *pDecode = NULL;
    	int decodeByteLen = HanfuManDecode(tree,pEncode,encodeBitLen,&pDecode);
    
    	if(decodeByteLen != TEST_DATA_LEN)
    	{
    		printf("Decode Fail...Len is not match\r\n");
    	}
    	else
    	{
    		if(memcmp(p,pDecode,TEST_DATA_LEN))
    		{
    			printf("Decode Fail... Decode data fail\r\n");
    		}
    		else
    		{
    			printf("Decode Success\r\n");
    		}
    	}
    
    	if(!pEncode)
    	{
    		delete []pEncode;
    		pEncode = NULL;
    	}
    	if(!pDecode)
    	{
    		delete []pDecode;
    		pDecode = NULL;
    	}
    
    	DestroyTree(tree);
    
    RET:
    	if(pDataInfo)
    	{
    		delete [] pDataInfo;
    	}
    	if(p)
    	{
    		delete [] p;
    	}
    
    	return bRet;
    }
    
    //哈夫曼编码,返回值为编码后的数据位数 一个字节有8位
    int HanfuManEncode(unsigned char* data,int dataLen,unsigned char **encodeData)
    {
    	if(!data || dataLen<=0)
    	{
    		return 0;
    	}
    
    	//存储编码后的数据
    	*encodeData = (unsigned char *)new unsigned char[dataLen*8];
    	if(!*encodeData)
    	{
    		return 0;
    	}
    	memset(*encodeData,0,(dataLen*8)*sizeof(unsigned char));
    
    	int byteIndex = 0;
    	int bitIndexOfByte = 7;
    
    	unsigned char bitHelper[8] = {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};
    
    	for(int i=0;i<dataLen;i++) 
    	{
    		for(int j=0;j<(g_HanfuManCodeTable[data[i]]).codeLen;j++)
    		{
    			int codeByteIndex = j/8;
    			int codeBitIndexOfByte = j%8;
    			if((g_HanfuManCodeTable[data[i]]).data[codeByteIndex] & bitHelper[codeBitIndexOfByte])
    			{
    				(*encodeData)[byteIndex] |= bitHelper[bitIndexOfByte];
    			}
    			//达到了一个字节,则需要设置下一个字节当中的位域
    			if(-1 == --bitIndexOfByte)
    			{
    				byteIndex++;
    				bitIndexOfByte = 7;
    			}
    		}
    	}
    
    	return byteIndex*8 + (7 - bitIndexOfByte);
    }
    
    //哈夫曼解压缩,返回值为解压缩后的数据字节数
    int HanfuManDecode(PHANFUMAN_TREE tree,unsigned char* data,int dataBitLen,unsigned char **decodeData)
    {
    	if(!data || dataBitLen<=0)
    	{
    		return 0;
    	}
    
    	//存储解码后的数据
    	*decodeData = (unsigned char *)new unsigned char[dataBitLen];
    	if(!*decodeData)
    	{
    		return 0;
    	}
    	memset(*decodeData,0,(dataBitLen)*sizeof(unsigned char));
    
    	int decodeIndex = 0;
    	unsigned char bitHelper[8] = {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};
    
    	PHANFUMAN_TREE pTree = tree;
    
    	for(int i=0;i<dataBitLen;i++)
    	{
    		int codeByteIndex = i/8;
    		int codeBitIndexOfByte = i%8;
    		if(data[codeByteIndex] & bitHelper[7-codeBitIndexOfByte])
    		{
    			pTree = pTree->right; //如果是1,走到右子树
    		}
    		else
    		{
    			pTree = pTree->left; //如果是0,走到左子树
    		}
    
    		//叶子节点,则输出解码数据
    		if(!pTree->left && !pTree->right)
    		{
    			(*decodeData)[decodeIndex++] = pTree->data;
    			pTree = tree;
    		}
    	}
    
    	return decodeIndex;
    }
    
    void InsertSort(PDATA_INFO pDataInfo,int len,unsigned char data,unsigned short dataTimes)
    {
    	if(0 == len)
    	{
    		pDataInfo[0].data = data;
    		pDataInfo[0].times = dataTimes;
    		return;
    	}
    
    	int inserIndex = 0;
    	//使用插入排序
    	for(inserIndex=0;inserIndex<len;inserIndex++)
    	{
    		if(dataTimes >= pDataInfo[inserIndex].times)
    		{
    			continue;
    		}
    		break;
    	}
    
    	for(int i=len-1;i>=inserIndex;i--)
    	{
    		memcpy(&pDataInfo[i+1],&pDataInfo[i],sizeof(DATA_INFO));
    	}
    	//插入新数据
    	pDataInfo[inserIndex].data = data;
    	pDataInfo[inserIndex].times = dataTimes;
    }
    
    void InsertSortTree(PHANFUMAN_TREE *pSubTree,int subTreeCount,PHANFUMAN_TREE insertTree)
    {
    	if(0 == subTreeCount)
    	{
    		pSubTree[0] = insertTree;
    		return;
    	}
    
    	int inserIndex = 0;
    	//使用插入排序
    	for(inserIndex=0;inserIndex<subTreeCount;inserIndex++)
    	{
    		if(insertTree->weight >= (pSubTree[inserIndex])->weight)
    		{
    			continue;
    		}
    		break;
    	}
    
    	for(int i=subTreeCount-1;i>=inserIndex;i--)
    	{
    		pSubTree[i+1] = pSubTree[i];
    	}
    	//插入新数据
    	pSubTree[inserIndex] = insertTree;
    }
    
    void RefreshSubTrees(PHANFUMAN_TREE *pSubTree,int subTreeCount,PHANFUMAN_TREE mergeTree)
    {
    	for(int i=2;i<subTreeCount;i++)
    	{
    		pSubTree[i-2] = pSubTree[i];
    	}
    	
    	//插入排序,按照权重的从小到大顺序排序
    	InsertSortTree(pSubTree,subTreeCount-2,mergeTree);
    }
    
    //合并2棵子树,pSubTree1的权重默认比pSubTree2的小
    PHANFUMAN_TREE MergeTree(PHANFUMAN_TREE pLeftSubTree,PHANFUMAN_TREE pRightSubTree)
    {
    	PHANFUMAN_TREE mergeRoot = new HANFUMAN_TREE;
    
    	if(!mergeRoot)
    	{
    		return NULL;
    	}
    
    	mergeRoot->data = 0;
    
    	pLeftSubTree->parent = mergeRoot;
    	mergeRoot->weight = pLeftSubTree->weight;
    	//pLeftSubTree 默认不为空
    	if(pRightSubTree)
    	{
    		mergeRoot->weight += pRightSubTree->weight;
    		pRightSubTree->parent = mergeRoot;
    	}
    
    	mergeRoot->parent = NULL;
    	mergeRoot->left = pLeftSubTree;
    	mergeRoot->right = pRightSubTree;
    
    	return mergeRoot;
    }
    
    //创建新树,用于创建叶子节点
    PHANFUMAN_TREE CreateLeaf(PDATA_INFO pDataInfo)
    {
    	PHANFUMAN_TREE leafTree = new HANFUMAN_TREE;
    
    	if(!leafTree)
    	{
    		return NULL;
    	}
    
    	leafTree->data = pDataInfo->data;
    	leafTree->weight = pDataInfo->times;
    
    	leafTree->parent = NULL;
    	leafTree->left = NULL;
    	leafTree->right = NULL;
    
    	return leafTree;
    }
    
    //创建哈夫曼编码树
    PHANFUMAN_TREE CreateHanfuManTree(PDATA_INFO pDataInfo,int len)
    {
    	if(len<=0)
    	{
    		return NULL;
    	}
    
    	int dataIndex = 0;
    	//最多只可能出现len+1/2个子树,用于保存编码过程可能出现的全部子树的根节点指针
    	PHANFUMAN_TREE *pSubTree = (PHANFUMAN_TREE*) new PHANFUMAN_TREE[(len+1)/2];
    	PHANFUMAN_TREE root = NULL;
    	int subTreeCount = 0; //子树的个数
    	HANFUMAN_SELECT_HELPER  selectHelper;
    
    	memset(pSubTree,0,sizeof(PHANFUMAN_TREE)*((len+1)/2));
    
    	while(dataIndex<len)
    	{
    		//对比数组中剩余未编码的数据和各个子树选择2个权重最小的,如果权重相同,优先选择子树中的
    		//由于数组和子树都已经按照从小到大的顺序,因此直接选取对比即可
    		if(subTreeCount>=2)
    		{
    			selectHelper.firstMinIndex = 0;
    			selectHelper.secondMinIndex = 1;	
    		}
    		else
    		{
    			if(subTreeCount>=1)
    			{
    				selectHelper.firstMinIndex = 0;
    			}
    		}
    
    		if(-1 == selectHelper.firstMinIndex)
    		{
    			selectHelper.firstMinIndex = dataIndex;
    			selectHelper.firstMinType = INDEX_TYPE_INFO;
    			if(++dataIndex<len)
    			{
    				selectHelper.secondMinIndex = dataIndex++;
    				selectHelper.secondMinType = INDEX_TYPE_INFO;
    			}
    		}
    		else
    		{
    			if(pDataInfo[dataIndex].times < (pSubTree[selectHelper.firstMinIndex])->weight)
    			{
    				selectHelper.secondMinIndex = selectHelper.firstMinIndex;
    
    				selectHelper.firstMinIndex = dataIndex;
    				selectHelper.firstMinType = INDEX_TYPE_INFO;
    
    				if( (++dataIndex<len) && ( pDataInfo[dataIndex].times < (pSubTree[selectHelper.secondMinIndex])->weight  ) )
    				{
    					selectHelper.secondMinIndex = dataIndex++;
    					selectHelper.secondMinType = INDEX_TYPE_INFO;
    				}
    			}
    			else
    			{
    				if( (-1==selectHelper.secondMinIndex) || (pDataInfo[dataIndex].times < (pSubTree[selectHelper.secondMinIndex])->weight))
    				{
    					selectHelper.secondMinIndex = dataIndex++;
    					selectHelper.secondMinType = INDEX_TYPE_INFO;
    				}
    			}
    		}//至此,已经选择出了2个最小权重的
    
    		if(INDEX_TYPE_TREE == selectHelper.firstMinType && INDEX_TYPE_TREE == selectHelper.secondMinType)
    		{
    			//合并2棵子树
    			PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],pSubTree[1]);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			RefreshSubTrees(pSubTree,subTreeCount,mergeTree);
    
    			subTreeCount--;
    		}
    		if(INDEX_TYPE_TREE == selectHelper.firstMinType && INDEX_TYPE_INFO == selectHelper.secondMinType)
    		{
    			PHANFUMAN_TREE newLeaf = CreateLeaf(&pDataInfo[selectHelper.secondMinIndex]);
    			if(!newLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],newLeaf);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			for(int i=1;i<subTreeCount;i++)
    			{
    				pSubTree[i-1] = pSubTree[i];
    			}
    
    			InsertSortTree(pSubTree,subTreeCount-1,mergeTree);//插入子树后,子树的数量不变
    		}
    		if(INDEX_TYPE_INFO == selectHelper.firstMinType && INDEX_TYPE_INFO == selectHelper.secondMinType)
    		{
    			PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    			if(!leftLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE rightLeaf = CreateLeaf(&pDataInfo[selectHelper.secondMinIndex]);
    			if(!leftLeaf)
    			{
    				exit(0);
    			}
    			PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,rightLeaf);
    			if(!mergeTree)
    			{
    				exit(0);
    			}
    			InsertSortTree(pSubTree,subTreeCount,mergeTree);
    			subTreeCount++; //插入子树后,子树的数量+1
    		}
    		if(INDEX_TYPE_INFO == selectHelper.firstMinType && INDEX_TYPE_TREE == selectHelper.secondMinType)
    		{
    			if(-1 == selectHelper.secondMinIndex)
    			{
    				PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    				if(!leftLeaf)
    				{
    					exit(0);
    				}
    				PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,NULL);
    				if(!mergeTree)
    				{
    					exit(0);
    				}
    				InsertSortTree(pSubTree,subTreeCount,mergeTree);
    				subTreeCount++; 
    			}
    			else
    			{
    				PHANFUMAN_TREE leftLeaf = CreateLeaf(&pDataInfo[selectHelper.firstMinIndex]);
    				if(!leftLeaf)
    				{
    					exit(0);
    				}
    				PHANFUMAN_TREE mergeTree = MergeTree(leftLeaf,pSubTree[selectHelper.secondMinIndex]);
    				if(!mergeTree)
    				{
    					exit(0);
    				}
    				for(int i=1;i<subTreeCount;i++)
    				{
    					pSubTree[i-1] = pSubTree[i];
    				}
    
    				InsertSortTree(pSubTree,subTreeCount-1,mergeTree);
    			}
    		}
    
    		selectHelper.Init();
    	}
    
    	//合并sub trees
    	while(subTreeCount>1)
    	{
    		//合并2棵子树
    		PHANFUMAN_TREE mergeTree = MergeTree(pSubTree[0],pSubTree[1]);
    		if(!mergeTree)
    		{
    			exit(0);
    		}
    		RefreshSubTrees(pSubTree,subTreeCount,mergeTree);
    
    		subTreeCount--;
    	}
    
    	//最后子树中只剩下一课,这棵树即为编码树
    	PHANFUMAN_TREE tree = pSubTree[0];
    	delete [] pSubTree;
    	
    	return tree;
    }
    
    //释放树
    void DestroyTree(PHANFUMAN_TREE tree)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	DestroyTree(tree->left); //刪除左子树
    	DestroyTree(tree->right);//删除右子树
    
    	delete tree; //删除根节点
    	tree = NULL;
    }
    
    //通过叶子的父节点向上
    void PrintHanfuManCode(PHANFUMAN_TREE tree,int *codeLen,unsigned char data)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	PHANFUMAN_TREE parent = tree->parent;
    	if(!parent)
    	{
    		return;
    	}
    
    	PrintHanfuManCode(parent,codeLen,data);
    	if(parent->left == tree)
    	{
    		(*codeLen)++;
    		printf("0");
    		//默认值就是为0,因此编码表元素不需要设置数据,长度增加1个位域即可
    		g_HanfuManCodeTable[data].codeLen++;
    	}
    	else
    	{
    		(*codeLen)++;
    		printf("1");
    		//需要设置编码表元素的第g_HanfuManCodeTable[data].codeLen位为1
    		int byteIndex = g_HanfuManCodeTable[data].codeLen/8;
    		int bitIndexOfByte = g_HanfuManCodeTable[data].codeLen%8;
    		unsigned char bitHelper[8] = {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80};
    		g_HanfuManCodeTable[data].data[byteIndex] |= bitHelper[bitIndexOfByte];
    		g_HanfuManCodeTable[data].codeLen++;
    		//如果某个字段的编码位域为1101,则设置后,g_HanfuManCodeTable[data].data[0]第1位为1,第二位为1,第三位为0,第四为为1,即1011
    		//如果某个字段的编码位域为1011 1111 1101,则设置后,g_HanfuManCodeTable[data].data[0] = 1111 1101
    		//g_HanfuManCodeTable[data].data[1] = 0000 1011 即保存的顺序和我们阅读的顺序刚好相反了
    	}
    }
    
    
    //通过二次遍历编码树,枚举得到每个data的哈夫曼编码
    void EnumHanfuManCode(PHANFUMAN_TREE tree)
    {
    	if(!tree)
    	{
    		return;
    	}
    
    	//叶子节点
    	if(!tree->left && !tree->right)
    	{
    		int codeLen = 0;
    		printf("data value = 0x%2x    HanfuMan Code = ",tree->data);
    		PrintHanfuManCode(tree,&codeLen,tree->data);
    		printf("   CodeLen = %d\r\n",codeLen);
    		return;
    	}
    	
    	if(tree->left)
    	{
    		EnumHanfuManCode(tree->left);
    	}
    
    	if(tree->right)
    	{
    		EnumHanfuManCode(tree->right);
    	}
    }
    #include <Windows.h>
    #include <stdio.h>
    #include "HanfuMan.h"
    
    
    int main(int agrc,char* argv[])
    {
    	TestHanfuMan();
    	
    	getchar();
    	return 0;
    }

             这里,是通过随机生成的压缩数据,测试数据大小  #define TEST_DATA_LEN 16。测试结果如下:

             

    展开全文
  • 哈夫曼编码是一种变长的字符编码方式,常用于对指定的字符集进行数据压缩,压缩率在 20%~90%。1. 问题描述现在有一个包含 5 个字符的字符表 {A,B,C,D,E},各字符出现的频率统计如表 1 所示。表 1:各字符出现的频率...

    哈夫曼编码是一种变长的字符编码方式,常用于对指定的字符集进行数据压缩,压缩率在 20%~90%。

    1. 问题描述

    现在有一个包含 5 个字符的字符表 {A,B,C,D,E},各字符出现的频率统计如表 1 所示。

    表 1:各字符出现的频率统计

    字符

    出现概率

    字符

    出现概率

    字符

    出现概率

    A

    0.35

    C

    0.2

    E

    0.15

    B

    0.1

    D

    0.2

    需要构造一种有效率的编码类型,使用该编码表达以上字符表内容时可以产生平均长度最短的位串。在对由 n 个字符组成的文本进行编码过程中,有两种编码方式,即定长编码和变长编码。

    对于定长编码而言,会为每个字符赋予一个长度固定为 m(m≥log2n) 的位串,我们常用的标准 ASCII 码就是采用定长编码策略对字符集进行编码的。长度各异的编码,其中出现频率较高的字符,采用长度较短的编码表示,出现频率较低的字符,采用长度较长的编码表示。著名的摩尔斯电码就是采用这种策略进行编码的。

    通常情况下,与定长编码相比,变长编码可以有效减少表示同一字符集所需的编码长度,提升编码效率。但是,为了使用变长编码策略,需要解决在定长编码模式下不会遇到的一个问题,就是前缀码问题。对每一个字符规定一个 0-1 串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀,这种编码称为前缀码。

    有了前缀码,我们可以在编码完成的位串中准确定位每个属于字符集的字符,通过简单扫描一个位串,直到得到某个等于字符集中字符的位串后,将该字符替换之前的位串,重复以上操作,即可根据位串恢复原来的文本。本节所讲的哈夫曼编码就是一种前缀码。

    2. 哈夫曼树

    为了对某字母表构造一套二进制的前缀码,可以借助二叉树。将树中所有的左向边都标记为0,所有的右向边都标记为 1。通过记录从根节点到字符所在的叶子节点的简单路径上的所有 0-1 标记来获得表示该字符的编码。

    用于表示二进制前缀码的二叉树每个叶子节点对应一个字符,非叶子节点不对应任何字符。由于二叉树叶子节点之间没有互联的简单路径,所以依据这种二叉树生成的编码序列为前缀码,即字符集中各个字符对应的前缀各不相同。

    对于给定的字符集和字符表而言,每个字符的出现频率可以确定,我们怎么才能构造一棵二叉树,将较短的编码分配给高频字符,将较长的编码分配给低频字符呢?用贪心算法可以实现这个目标。

    这个算法由戴维·哈夫曼(David Huffman)发明,因此,能达到这个目标的二叉树称为哈夫曼树。

    具体算法如下:

    初始化 n 个单节点的树,并为它们标上字母表中的字符。把每个字符出现的频率记在其对应的根节点中,用来标记各个树的权重,即树的权重等于树中所有叶子节点的概率之和。

    重复下面的步骤,直到只剩一颗单独的树。找到两棵权重最小的树,若两棵树权重相同,可任选其一,分别把它们作为新二叉树的左右子树,并把其权重之和作为新的权重记录在新树的根节点中。

    用上述算法构造出的二叉树即为哈夫曼树。根据哈夫曼树获取的编码称为哈夫曼编码。

    在初始状态,构造图 1 所示的根节点集合。

    3-20062212460b20.gif

    图 1:初始化根节点示意图

    此时,我们将节点 B 和 E 合并成一棵新的子树,如图 2 所示。

    3-200622124R2V6.gif

    图 2:合并节点B和E后示意图

    合并节点 B 和 E 之后,重新排序根节点,合并两个权值最小的节点,即节点 C 和 D,如图 3 所示。

    3-20062212502Q95.gif

    图 3:合并节点 C 和 D 后示意图

    之后,合并由节点 B 和 E 组成的树的根节点和节点 A,如图 4 所示。

    3-200622125534315.gif

    图 4:合并由节点 B 和 E 组成的树的根节点和节点 A 后示意图

    最后,获取剩余的两个节点,得到结果哈夫曼树,如图 5 所示。

    3-200622125K22b.gif

    图 5:结果哈夫曼树示意图

    获得哈夫曼树后,根据沿着结果哈夫曼树的左侧分支编 0,沿着右侧分支编 1,可以得到字符表中的各个字符的对应编码如表 2 所示。

    表 2:对应编码

    字符

    出现概率

    哈夫曼编码

    字符

    出现概率

    哈夫曼编码

    A

    0.35

    11

    D

    0.2

    01

    B

    0.1

    100

    E

    0.15

    101

    C

    0.2

    00

    至此,字符集编码问题得到解决。根据给定的字符出现的概率和求得的各字符对应的编码长度,若采用上述编码策略,每个字符的平均位长度为:

    2 * 0.35 + 3 * 0.1 + 2 * 0.2 + 2 * 0.2 + 3 * 0.15 = 2.25

    若采用定长编码策略,则表示上面字符表中的每个字符至少需要用 3 位编码来表示。因此,针对这一实例,哈夫曼编码的实现的压缩率为:

    [(3 - 2.25) / 3] * 100% = 25%

    综上,若采用哈夫曼编码,我们表达该字符集时比采用定长编码策略可以少占用 25% 的存储空间。

    3. 贪心选择性质

    二叉树 T 表示字符集 C 的一个最优前缀码,证明可以对 T 作适当修改后得到一棵新的二叉树 T'',在 T'' 中 x 和 y 是最深叶子节点且为兄弟,同时 T'' 表示的前缀码也是 C 的最优前缀码。设 b 和 c 是二叉树 T 的最深叶子,且为兄弟。设 f(b)≤f(c),f(x)≤f(y)。

    由于 x 和 y 是 C 中具有最小频率的两个字符,有 f(x)≤f(b),f(y)≤f(c)。首先,在树 T 中交换叶子 b 和 x 的位置得到 T',然后在树 T' 中交换叶子 c 和 y 的位置,得到树 T'',如图 6 所示。由于 T 是字符集 C 的最优前缀码,因此可知 B(T)≤B(T'')。

    3-200622130529126.gif

    图 6:贪心选择性质证明示意图

    由此可知,树 T 和 T' 的前缀码的平均码长之差为:

    3-200622130QR00.gif

    因此,可得出 B(T)≥B(T′)。

    同理,可计算树 T' 和 T'' 的前缀平均码长只差为:

    3-20062213092M50.gif

    因此,可得出 B(T′)≥B(T′′)。

    综上,可根据以下两个不等式得出最终结论:

    3-20062213204Y29.gif

    因此,T′′ 表示的前缀码也是最优前缀码,且 x 和 y 具有相同的码长,同时,仅最优一位编码不同。

    4. 最优子结构性质

    二叉树 T 表示字符集 C 的一个最优前缀码,x 和 y 是树 T 中的两个叶子且为兄弟,z 是它们的父亲。若将 z 当作是具有频率 f(z)=f(x)+f(y) 的字符,且定义树 T' 表示字符集 C'=C-{x,y}∪{z} 的一个最优前缀码。

    因此,有:

    1) c∈C−{x,y},dT(c)=dT'(c)=>f(c)dT(c)=f(c)dT'(c)

    2) f(x)dT(x)+f(y)dT(y)=f(x)+f(y)+f(z)dT'(z)

    B (T)=B(T′)+f(x)+f(y) 如果 T' 不是 C' 的最优前缀码,假定 T'' 是 C' 的最优前缀码,那么显然 T'' 是比 T 更优的前缀码,这与前提条件相矛盾,故 T' 所表示的 C' 的前缀码是最优的。

    根据上述论证,生成哈夫曼树的策略具备贪心选择性质和最优子结构性质,因此,生成的哈夫曼树所对应的编码为最优前缀码。

    5. 参考实现

    实现代码如下:

    # Huffman Encoding

    # 树节点定义

    class Node:

    def __init__(self,pro):

    self.left = None

    self.right = None

    self.parent = None

    self.pro = pro

    def isLeft(self): # 判断左子树

    return self.parent.left == self

    #create nodes创建叶子节点

    def createNodes(pros):

    return [Node(pro) for pro in pros]

    #create Huffman-Tree创建Huffman树

    def createHuffmanTree(nodes):

    queue = nodes[:]

    while len(queue) > 1:

    queue.sort(key=lambda item:item.pro)

    node_left = queue.pop(0)

    node_right = queue.pop(0)

    node_parent = Node(node_left.pro + node_right.pro)

    node_parent.left = node_left

    node_parent.right = node_right

    node_left.parent= node_parent

    node_right.parent= node_parent

    queue.append(node_parent)

    queue[0].parent= None

    return queue[0]

    # Huffman编码

    def huffmanEncoding(nodes,root):

    codes = [''] * len(nodes)

    for i in range(len(nodes)):

    node_temp = nodes[i]

    while node_temp != root:

    if node_temp.isLeft():

    codes[i] = '0' + codes[i]

    else:

    codes[i] = '1' + codes[i]

    node_temp = node_temp.parent

    return codes

    if __name__ == '__main__':

    #letters = ['A','B','C','D','E']

    #pros = [35,10,20,20,15]

    letters_pros = [('B', 10), ('E', 15), ('C', 20), ('D', 20), ('A', 35)]

    nodes = createNodes([item[1] for item in letters_pros])

    root = createHuffmanTree(nodes)

    codes = huffmanEncoding(nodes, root)

    for item in zip(letters_pros, codes):

    print('Label:%s pro:%-2d Huffman Code:%s'%(item[0][0],item[0][1],item[1]))

    最终的输出结果为:

    Label:B pro:10 Huffman Code: 100

    Label:E pro:15 Huffman Code: 101

    Label:C pro:20 Huffman Code: 00

    Label:D pro:20 Huffman Code: 01

    Label:A pro:35 Huffman Code: 11

    展开全文
  • 举例理解哈夫曼树与哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼
  • 详细描述了哈夫曼树的构造方法,同时推广到三元哈夫曼编码,并用C语言于VC++上实现
  • 香农编码 哈夫曼编码 费诺编码的比较 文章目录哈夫曼编码编码步骤例子优点缺点费诺编码编码步骤例子优点缺点香农编码编码步骤例子优点缺点参考 备注:本文除了例子与数据,其他内容均为整合网络资源。 哈夫曼编码 ...
  • 哈夫曼编码习题

    千次阅读 2019-11-07 19:57:45
    假设用于通信的电文仅由8个字母组成,字母在电文中出现的...请为这8个字母设计哈夫曼编码。 表格形式: NO. data parent Lchild Rchild 0 0.07(A) 10 NULL NULL 1 0.19(B) 12 ...
  • 哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次越少的字符编码越长。为了演示哈夫曼编码...
  • 哈夫曼编码的实现

    万次阅读 多人点赞 2016-08-08 21:13:17
    而我对哈夫曼编码的理解也仅仅局限在其用于编码领域,可以提高数据传输效率,或者是用于压缩文件?这些可能并不准确,我没有细细的去查证。 哈夫曼编码可以通过构建哈夫曼树来得到。 我们用一个简单的例子,来简单...
  • 哈夫曼编码理解

    千次阅读 2016-04-28 15:39:49
    哈夫曼编码 哈夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过程为  i.以每个字符的出现频率作为关键字构建最小优先队列;  ii.去除关键字最小的两个结点生成子树,根结点的...
  • Huffman Tree,中文名是哈夫曼树或霍夫曼树,它是最优二叉树。 引入 如果有一篇文章,由若干个字符构成。每个ABC…Z都由7位编码,文章有1w个字符,那么有7w位进行编码。一个字节8位,首位是0。需要占用1W个字节。 ...
  • 图像哈夫曼编码程序

    2012-12-20 22:14:49
    对其中一幅图像进行哈夫曼编码,然后用它对另外一幅图像进行编码并计算码长
  • 哈夫曼树&哈夫曼编码

    千次阅读 2018-06-11 20:38:38
    哈夫曼树也是最优二叉树,首先我们来看哈夫曼树的定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。先再解释一下什么是带权...
  • 哈夫曼编码,保证正确的同时提高了效率 是一种二进制最短前缀编码 带权最短路径最短的树–哈夫曼树,可以用优先队列(底层实质上是堆)实现 对于输入的n个带权结点,初始为 n个只有根结点的树 每次选择权最小的两个...
  • 对26个英文字母(已知它们的概率分布)进行了哈夫曼编码,并计算了编码效率。有助于大家理解哈夫曼编码以及信息论的相关知识哦。
  • 哈夫曼树原本是为哈夫曼编码服务的一种数据结构,又称最优二叉树,哈夫曼编码常被使用在数据的压缩和解压缩技术之中。本文详细介绍了哈夫曼树的概念,并且提供了Java实现,最后又介绍了哈夫曼编码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,456
精华内容 1,782
关键字:

哈夫曼编码效率