数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

杨俊明 2010-12-03 21:51:00 浏览726
展开阅读全文

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义

1、路径 Path

简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的分支,比如下图中的红色分支(A->C->B与C->D->E->F)

            图1

 

2、路径长度(Path Length)

即路径中的分支个数,比如上图(a)中的路径长度为2,上图(b)中的路径长度为3

3、结点的权重(Weight of Node)

在一些特定应用中,有时候要刻意区分节点之间的重要程度(或优先程度),比如认为A节点比B节点要重要(更优先),可以给这些节点增加一个int型的属性值weight,用该值来标明这种重要性,这就是结点的权重.

          图2

4、结点的带权(重)路径长度(Weight Path Length of Node):

从该节点到树的节点的路径长度*该结点的权重,得到的结果就是这个东东

上图中

节点1的带权路径长度为 1 * 2 = 2;

节点2的带权路径长度为 2 * 2 = 4;

节点3的带权路径长度为 3 * 2 = 6;

节点4的带权路径长度为 4 * 2 = 8;

 

5、树的带权(重)路径长度

树中的每个节点均按4中的定义计算自身的带权路径长度,然后把得到的结果加在一起,就是整颗树的带权路径长度。

上图(即图2)中,树的带权路径长度为 2 + 4 + 6 + 8 = 20


如果给定4个节点,其权重值分别是1,2,3,4,那么构造一颗完全二叉树的方法有很多种,如下图:

上图显示,(c)树的带权路径总长最小(为19),而其它树的带权路径均为20,ok,它就是传说中的哈夫曼树,可通俗的理解为:

给定一组带权重的节点,用它们来构造完全二叉树,最终整颗树的带权路径(总)长度最小的即为啥夫曼树。(当然,这是根据我的理解给出的民间山寨定义,官方定义大家自己去看“数据结构与算法”这本书吧,上面有一堆数学符号,对于不喜欢数字的同学们,估计看起来很晕)

 

啥夫曼树的构造算法:

1、在给定的带权叶节点中,找出权重最小的二个(通常为了方便,可以先将叶节点按权重从小到大先排好,这样只需要取前面二项即可),然后添加一个临时节点作为这二个节点的父节点(其权重为这二个叶节点的权重之合)

2、将刚才处理过的二个节叶点去掉,然后把新增加的临时节点与剩下的叶节点放在一起做同样的处理,即:从新节点和叶节点的集合中,继续找到权重最小的二个,再继续增加新节点,做第1中的处理

3、重复以上过程,直到每个叶节点都处理完。

假如我们现在有权重为1,2,3,4的一组叶节点,上述过程图解为:

c#的算法实现:

先回顾上一篇提到的二个重要知识点:

1、由二叉树的数学特性4知:

对于一棵非空二叉树,如果度为0的结点数目为x,度为2的结点数目为y,则有 x = y +1(即y = x-1)

也就是说全部节点总数为 x+y = x + (x-1) = 2*x-1

2、完全二叉树,可以方便的使用顺序存储(即用线性结构的数组或List<T>来存储)

Huffman树的节点类Node.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 哈夫曼树
{
    public class Node
    {
        private int weight;//权重值
        private int lChild;//左子节点的序号
        private int rChild;//右子节点的序号
        private int index;//本节点的序号

        public int Weight 
        {
            get { return weight; }
            set { weight = value; }
        }

        public int LChild 
        {
            get { return this.lChild; }
            set { lChild = value; }
        }

        public int RChild 
        {
            get { return this.rChild; }
            set { rChild = value; }
        }

        public int Index 
        {
            get { return this.index; }
            set { index = value; }
        }

        public Node() 
        {
            weight = 0;
            lChild = -1;
            rChild = -1;
            index = -1;
        }

        public Node(int w, int lc, int rc, int p) 
        {
            weight = w;
            lChild = lc;
            rChild = rc;
            index = p;
        }
    }
}

 

HuffmanTree.cs(注:下面这段代码的Create算法在运行效率上也许并非最高的,但很容易理解)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 哈夫曼树
{
    public class HuffmanTree
    {
        private List<Node> _tmp;
        private List<Node> _nodes;

        public HuffmanTree(params int[] weights)
        {
            if (weights.Length < 2)
            {
                throw new Exception("叶节点不能少于2个!");
            }

            int n = weights.Length;

            Array.Sort(weights);

            //先生成叶子节点,并按weight从小到大排序
            List<Node> lstLeafs = new List<Node>(n);
            for (int i = 0; i < n; i++)
            {
                var node = new Node();
                node.Weight = weights[i];
                node.Index = i;
                lstLeafs.Add(node);
            }


            //创建临时节点容器
            _tmp = new List<Node>(2 * n - 1);

            //真正存放所有节点的容器
            _nodes = new List<Node>(_tmp.Capacity);

            _tmp.AddRange(lstLeafs);
            _nodes.AddRange(_tmp);
        }

        /// <summary>
        /// 构造Huffman树
        /// </summary>
        public void Create()
        {
            while (this._tmp.Count > 1)
            {
                var tmp = new Node(this._tmp[0].Weight + this._tmp[1].Weight, _tmp[0].Index, _tmp[1].Index, this._tmp.Max(c => c.Index) + 1);
                this._tmp.Add(tmp);
                this._nodes.Add(tmp);

                //删除已经处理过的二个节点
                this._tmp.RemoveAt(0);
                this._tmp.RemoveAt(0);


                //重新按权重值从小到大排序
                this._tmp = this._tmp.OrderBy(c => c.Weight).ToList();
            }
        }

        /// <summary>
        /// 测试输出各节点的关键值(调试用)
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < _nodes.Count; i++)
            {
                var n = _nodes[i];
                sb.AppendLine("index:" + i + ",weight:" + n.Weight.ToString().PadLeft(2, ' ') + ",lChild_index:" + n.LChild.ToString().PadLeft(2, ' ') + ",rChild_index:" + n.RChild.ToString().PadLeft(2, ' '));
            }
            return sb.ToString();
        }
    }
}

测试一下:

using System;

namespace 哈夫曼树
{
    class Program
    {
        static void Main(string[] args)
        {
            HuffmanTree tree = new HuffmanTree(2,1,4,3);
            tree.Create();

            Console.WriteLine("最终树的节点值如下:");
            Console.WriteLine(tree.ToString());
            Console.ReadLine();
        }
    }
}

输出结果如下:

最终树的节点值如下:
index:0,weight: 1,lChild_index:-1,rChild_index:-1
index:1,weight: 2,lChild_index:-1,rChild_index:-1
index:2,weight: 3,lChild_index:-1,rChild_index:-1
index:3,weight: 4,lChild_index:-1,rChild_index:-1
index:4,weight: 3,lChild_index: 0,rChild_index: 1
index:5,weight: 6,lChild_index: 2,rChild_index: 4
index:6,weight:10,lChild_index: 3,rChild_index: 5

 输出结果也许并不直观,对照下面这张图就明白了

哈夫曼编码(Huffman Encoding)

先扯貌似不相干的话题,在电报传输中,通常要对传输的内容进行编码(因为电报发送时只用0,1表示,所以需要将ABCDE这类字符最终变成0与1的组合,这就涉及到如何将字符集[A-Z]与[0,1]组合一一对应的问题)

假设现在有电文内容:AAAABBBCCD 需要编码后转送,现在要一套编码方案

首先很容易想到下面的这种定长编码方案,每个字符用2位数字表示,比如:

A->00
B->01
C->10
D->11
那么AAAABBBCCD最终的编码为00,00,00,00,01,01,01,10,10,11(注:这里加逗号是为了看得更直观,实际编码中并不需要)

但电报砖家们,提出了另一种更短的不定长编码方案:

A->0
B->10
C->111
D->110

按这种编码方案,AAAABBBCCD最终的编码为:0,0,0,0,10,10,10,111,111,110

把这二种方案的编码列在一起对比一下:

00,00,00,00,01,01,01,10,10,11 (不算逗号共20位)

0,0,0,0,10,10,10,111,111,110 (不算逗号共19位)

砖家果然是砖家!
仔细分析一下,会发现这种“不定长”的编码方案要想解码成功,要有一个重要的前提:任何一个编码,都不能是其它编码的前缀!否则解码时就会出现歧义。

比如:如果C编码为10,D编码为101,A编码为1,B编码为01

现在接收到了一个 10101,那么到底是解码为 CCA,还是DB呢?

现在揭晓哈夫曼编码的秘密

就刚才举例的AAAABBBCCD而言,电文中仅包含A,B,C,D这个字符,如果把它们看作叶节点,并且考虑到权重(D出现次数最小,权重认为最低;C出现次数比D高,因此权重高于D,其它类推),这样我们就有了一组带权重的叶节点(A-权重4,B-权重3,C-权重2,D-权重1),用它们来构造一颗哈夫曼树:

同时,我们把有分支做一个约定:向左的分支对应为数字0,向右的分支对应为数字1,这样从节点到每个子节点的路径就能得到一串数字。

即: A->0,B->10,C->110,D->111 ,这就是一种编码!

另外应该注意到,对于二叉树,某一个确定的叶节点只可能在一个唯一的分支上(即不可能一个叶节点即在这个分支上,又在其它分支上),这就保证了每个叶节点得到的编码都不可能是其它编码的前缀。

OK,寻找哈夫曼编码的问题最终就转化成了哈夫曼树的构造问题,问题得到解决了。(学会了哈夫曼编码,也许我们能跟某些冰雪聪明的MM们玩点另类告白的小游戏,发一串数字过去,然后配一张图,看她懂不懂你的心意,如果她能成功解出背后的含义是ILOVEYOU,然后回发一串吉祥数字给你,那么...恭喜你!)

网友评论

登录后评论
0/500
评论
杨俊明
+ 关注