文档章节

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

彭泽0902
 彭泽0902
发布于 2016/11/24 18:47
字数 1862
阅读 5
收藏 0
点赞 0
评论 0

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

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

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

© 著作权归作者所有

共有 人打赏支持
彭泽0902
粉丝 0
博文 44
码字总数 57771
作品 0
武汉
高级程序员
哈夫曼树|构建|哈夫曼编码

在学习《数据结构》课程的时候就涉及HuffmanTree,当时没有什么算法设计的概念,就是参照着伪代码慢慢敲写、调试、重复。最终还是理解看懂了,不过也是花费了很多的时间。最近在《算法设计与...

掬一捧 ⋅ 2012/09/16 ⋅ 2

HuffmanTre----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

木木侠 ⋅ 2016/08/20 ⋅ 0

HuffmanTree----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

科技小能手 ⋅ 2017/11/12 ⋅ 0

C#读取文件夹中的文件操作浅析

C#读取文件夹中的文件操作浅析 C#读取文件夹中的文件操作是怎么样子的呢?那么本文就向你介绍这方面的内容,希望对你有所帮助。 C#读取文件夹的操作是如何进行的呢?首先让我们来看啊可能:读...

长平狐 ⋅ 2013/01/06 ⋅ 0

数据结构,Huffman算法,里面如何选择最小的重的算法有疑问?

void select(HuffmanTree ht,int n, int s1, int *s2) { int i; int min; for(i=1; i<=n; i++) { if((*ht)[i].parent == 0) { min = i; i = n+1;//break } } for(i=1; i<=n; i++) { if((*ht)......

DBZ002 ⋅ 2016/11/16 ⋅ 0

推荐系统遇上深度学习(十三)--linUCB方法浅析及实现

上一篇中介绍了Bandit算法,并介绍了几种简单的实现,如 Epsilon-Greedy算法,Thompson sampling算法和UCB算法。 但是传统的实现方法存在很大的缺陷,主要是缺乏用附加信息刻画决策过程的机制...

石晓文 ⋅ 06/11 ⋅ 0

数据结构之哈夫曼树和编码器的构造

在最近的自学数据结构的过程中,为加深树的理解,码了一个二叉树编码器,请多多指教: #include #define MAXBIT100 //最大子树 #define MAXVALUE10000 //最大值 #define MAXLEAF30 //最大编码数 ...

云时之间 ⋅ 2017/11/15 ⋅ 0

Java系列文章(全)

JVM JVM系列:类装载器的体系结构 JVM系列:Class文件检验器 JVM系列:安全管理器 JVM系列:策略文件 Java垃圾回收机制 深入剖析Classloader(一)--类的主动使用与被动使用 深入剖析Classloader(二...

www19 ⋅ 2017/07/04 ⋅ 0

逃脱Asp.Net MVC框架的枷锁,使用Razor视图引擎

更多背景参看 前传:Razor视图引擎浅析 后续: eLiteWeb框架MVC(Model-View-Command) 机制解析 为什么要这么做? 1. Asp.Net MVC 其实也不是太好 2. 我有自己的敏捷Web框架, 仍然想用Razor引擎...

予沁安 ⋅ 2012/11/26 ⋅ 33

做跨界的跳跃,不惧怕学习,不惧怕失败 —— 阿里云 MVP 裔隽专访

丰富的经历让他意识到:技术没有银弹,人生也没有。 让我们来听听 阿里云 MVP 裔隽的专访: 因为皮亚杰,差点考了儿童心理学的硕士 受父亲的影响,比较喜欢电脑。 作为70后,我学电脑还是比较...

花肉酱 ⋅ 05/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 31分钟前 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 2

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

创建新用户和授予MySQL中的权限教程

导读 MySQL是一个开源数据库管理软件,可帮助用户存储,组织和以后检索数据。 它有多种选项来授予特定用户在表和数据库中的细微的权限 - 本教程将简要介绍一些选项。 如何创建新用户 在MySQL...

问题终结者 ⋅ 昨天 ⋅ 0

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部