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 条评论
登录 后参与评论

相关文章

来自专栏Hongten

对于一个运行时间为100n*n的算法,要使其在同一台机器上,在比一个运行时间为2^n的算法运行的很快,n的最小值是多少

653
来自专栏深度学习与计算机视觉

理解ResNet结构与TensorFlow代码分析

该博客主要以TensorFlow提供的ResNet代码为主,但是我并不想把它称之为代码解析,因为代码和方法,实践和理论总是缺一不可。 github地址,其中...

5487
来自专栏owent

线段树相关问题 (引用 PKU POJ题目) 整理

如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

562
来自专栏大数据挖掘DT机器学习

机器学习--决策树(ID3)算法及案例

1 基本原理 决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,每个分支路径代表某个可能的属性值,每个叶结点...

2846
来自专栏小樱的经验随笔

线段树入门总结

线段树的入门级 总结       线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。       对于...

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

数据结构 数组和广义表以及树的基本概念

2-1 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分) 1...

1778
来自专栏机器学习算法原理与实践

文本主题模型之LDA(二) LDA求解之Gibbs采样算法

    本文是LDA主题模型的第二篇,读这一篇之前建议先读文本主题模型之LDA(一) LDA基础,同时由于使用了基于MCMC的Gibbs采样算法,如果你对MCM...

703
来自专栏大数据智能实战

基于MTCNN的人脸自动对齐技术原理及其Tensorflow实现测试

        人脸识别是计算机视觉研究领域的一个热点。而人脸识别包含了诸多步骤,其实现技术流程如下图所示(摘自http://www.techshino.com...

7225
来自专栏机器学习原理

深度学习——RNN(3)

1805
来自专栏null的专栏

简单易学的机器学习算法——Gibbs采样

一、Gibbs采样概述 前面介绍的Metropolis-Hastings采样为从指定分布中进行采样提供了一个统一的框架,但是采样的效率依赖于指定的分布的选择,若...

3509

扫码关注云+社区