HuffmanTree的浅析和在C#中的算法实现

      无论是在我们的开发项目中,还是在我们的日常生活中,都会较多的涉及到文件压缩。谈到文件压缩,可能会有人想问文件压缩到底是怎么实现的,实现的原理是什么,对于开发人员来说,怎么实现这样一个压缩的功能。

      接下来,我们就来了解一下文件压缩的相关知识。文件压缩是如何实现的?这个我们就得了解一下数据结构,因为文件在压缩的过程中会转化为数据流,那么如何将数据流进行对应的压缩,这个问题就得靠算法来实现。那么文件压缩的算法是什么呢?那就是HuffmanTree。

     提到HuffmanTree,我们就需要顺道讲讲数据结构和算法。在计算机中,数据结构和算法可以说是程序的灵魂。

     数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。按照视点的不同,我们将数据结构分为逻辑结构和物理结构。

         (1).逻辑结构:是指数据对象中数据元素之间的相互关系。逻辑结构包含:集合结构(集合结构中的数据元素除了同属于一个集合外,他们之间没有其他关系);线性结构(线性结构中的数据元素之间是一对一的关系);树形结构(树形结构的数据元素之间存在一种一对多的层次关系);图形结构(图形结构的数据元素是多对多的关系)。

         (2).物理结构:是指数据的逻辑结构在计算机中的存储形式。物理结构包含:顺序存储结构(是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的);链式存储结构(是指把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的)

     上面介绍了一下数据结构的分类,当然,说到HuffmanTree,那就需要提一下“树形结构”。

        树:是N(N大于或等于0)个节点的有限集合。现在介绍一下树的三种表示法:

       (1).双亲表示法(在每个节点中,附设一个指示器指示双亲节点到链表中的位置);

       (2).孩子表示法(每个节点有多个指针域,其中每个指针指向一个棵树的根节点,我们把这种方法叫做链表表示法);

       (3).孩子兄弟表示法(任意一棵树,它的第一个孩子如果存在就是唯一的,它的友兄弟如果存在也是唯一的,因此,我们设置两个指针,分别指向该节点的第一个孩子和此节点的又兄弟)。

     上面提到树,现在介绍一下二叉树。

       二叉树:是N(N大于或等于0)个节点的有限集合,该集合或者为空,或者有一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

     接下来介绍一下几种特殊的二叉树:

       (1).斜树:所有的节点都只有在左子树的二叉树叫做左斜树。所有节点都是只有右子树叫做右斜树。

       (2).满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树成为满二叉树。

      (3).完全二叉树:对一棵具有N个节点的二叉树按层序编号,如果编号为I(1大于或等于I小于或等于N)的节点与同样深度的满二叉树中编号为I的节点在二叉树中位置完全相同,则这棵二叉树成为完全二叉树。

    前面我首先介绍了数据结构的定义和分类,接着介绍了树,二叉树。最后让我们一起来具体的了解一下HuffmanTree。

      从树中的一个节点到另一个节点之间的分支构成两个节点之间的路径,路径上的分支数目称做路径长度。树的路径长度就是从树根到每一个节点的路径长度之和。节点的带权的路径长度为从该节点到跟之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和。

      HuffmanTree:带权路径长度WPL最小的二叉树称做赫夫曼树。(又称做:最优二叉树)

      赫夫曼编码:规定赫夫曼树的左分支代表0,又分支代表1,则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码。

      以上介绍了 HuffmanTree的相关概念知识,现在就需要将这个数据结构采用代码实现,接下来提供一段采用C#代码实现的 HuffmanTree。

      1.位流的基类:

    /// <summary>
    /// 位流的基类。
    /// </summary>
    /// <remarks>
    /// 一个字节流转换到一个位流的规则实现之间。
    /// </remarks>
    public abstract class BitStream
    {
        /// <summary>
        /// 在数据流上快速的获取最大位数
        /// </summary>
        public abstract int MaxReadAhead { get; set; }

        /// <summary>
        /// 从流中读取位。
        /// </summary>
        /// <param name="count">读取的比特数。</param>
        /// <returns>位为UInt32。</returns>
        public abstract uint Read(int count);

        /// <summary>
        /// 在流上查询数据
        /// </summary>
        /// <param name="count">查询的位数。</param>
        /// <returns>位为UInt32。</returns>
        /// <remarks>此方法不消耗位(即移动文件指针)。</remarks>
        public abstract uint Peek(int count);

        /// <summary>
        /// 从流中消耗比特,而不返回它们。
        /// </summary>
        /// <param name="count">消耗的比特数。</param>
        public abstract void Consume(int count);
    }

       2.哈夫曼树的实现:

    /// <summary>
    ///哈夫曼树的实现。
    /// </summary>
    /// <remarks>
    /// 创建一个查找表,将采取任何位序列(最大树深度的长度),指示输出符号。在WIM文件,在实践中,没有一块超过32768字节
    ///长度,所以我们经常会产生一个更大的查找表比它的数据编码。这使得异常快速符号查找O(1),但效率较低整体。
    /// </remarks>
    public sealed class HuffmanTree
    {
        // 每个符号的最大位
        private readonly int _numBits;

        // 最大符号
        private readonly int _numSymbols;

        private readonly uint[] _buffer;

        public HuffmanTree(uint[] lengths)
        {
            Lengths = lengths;
            _numSymbols = lengths.Length;

            uint maxLength = 0;
            for (var i = 0; i < Lengths.Length; ++i)
            {
                if (Lengths[i] > maxLength)
                {
                    maxLength = Lengths[i];
                }
            }

            _numBits = (int)maxLength;
            _buffer = new uint[1 << _numBits];

            Build();
        }

        public uint[] Lengths { get; set; }

        public uint NextSymbol(BitStream bitStream)
        {
            var symbol = _buffer[bitStream.Peek(_numBits)];

            // 我们可能在读,复位比特流的位置
            bitStream.Consume((int)Lengths[symbol]);

            return symbol;
        }

        private void Build()
        {
            var position = 0;

            //对于每一位长度…
            for (var i = 1; i <= _numBits; ++i)
            {
                // 检查每个符号
                for (uint symbol = 0; symbol < _numSymbols; ++symbol)
                {
                    if (Lengths[symbol] != i) continue;
                    var numToFill = 1 << (_numBits - i);
                    for (var n = 0; n < numToFill; ++n)
                    {
                        _buffer[position + n] = symbol;
                    }

                    position += numToFill;
                }
            }

            for (var i = position; i < _buffer.Length; ++i)
            {
                _buffer[i] = uint.MaxValue;
            }
        }
    }

      赫夫曼树和赫夫曼编码对于带权路径的二叉树做了一些了解,用于初步理解压缩原理。对于数据结构的理解,需要我们花费很多的时间,也需要我们在这些数据结构中做一个细致的分类。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

算法入门,其实可以像读小说一样有趣

我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅。

4104
来自专栏灯塔大数据

每周学点大数据 | No.25二叉搜索树回顾(二)

No.25期 二叉搜索树回顾(二) Mr. 王:既然提到了有序的状态,那么我们就来谈谈有根树的遍历问题。 小可:我知道,遍历就是访问一个数据集合中的所...

3356
来自专栏大数据和云计算技术

算法基础:优先队列

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第四篇《优先队列》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基础#...

3156
来自专栏机器学习和数学

[Tensorflow] TensorFlow之Hello World!(2)

TensorFlow入门的第一篇和大家聊了?graph图,op操作,node节点。对TensorFlow有了一个简单的认识,今天主要和大家分享的是TensorF...

3457
来自专栏机器学习算法全栈工程师

Java 机器学习库Smile实战(一)SVM

本文不会介绍SVM的基本原理,如果想了解SVM基本原理,请参阅相关书籍。 要使用Java机器学习库Smile,需首先在项目的Maven配置文件pom.xml中添...

38312
来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

381
来自专栏数据结构与算法

分块之区间修改与单点查询

给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值。 这是一道能用许多数据结构优化的经典题,可以用于不同数据结构训练。 数列分块就是把数列中每m个元...

3435
来自专栏用户2442861的专栏

腾讯2014校园招聘软件开发类笔试试题

http://blog.csdn.net/zs634134578/article/details/20938113

932
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

711
来自专栏mathor

并查集(Union Find)

 没想到有一天我也能搞懂并查集,orz......实际上本文算是《Algorithms》一书的读后感

881

扫码关注云+社区