精华内容
下载资源
问答
  • 哈夫曼编码(前缀编码)理解
    千次阅读
    2019-11-25 21:43:19

    5,6,2,9,7

     

    哈夫曼编码

     

    比如文字内容”ABCDEF”,通过二进制数据表示这里写图片描述

    传输数据为:“000001010011100101”按照3位一分来译码即可,但可以想象假如文字多了,数据量也是相当的大。

    所以需要前缀编码(就是最短数据进行传输)来进行编码(哈夫曼思想)
    前缀编码:设计长短不等的编码,必须是任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码

    因为每个字母的出现频率是不同的,我们假设给每个字母分配权值:A:27,B:8,C:15,D:15,E:30,F:5,首先按照它们的权值进行构造哈夫曼树

    将所有权值左分支改为0,右分支改为1. 就是前缀。
     

    更多相关内容
  • 哈夫曼树与哈夫曼编码(前缀编码)理解

    万次阅读 多人点赞 2017-11-21 14:30:11
    哈夫曼树又称最优二叉树,是带权路径长度(WPL)最短的树,可以构造最优编码,用于数据传输,数据压缩等方向 下面是二叉树和哈夫曼树二、概念 路径:树中一个结点到另一个结点之间的分支序列构成两个结点间的路径 ...

    一、哈夫曼树定义及用途

    哈夫曼树又称最优二叉树,是带权路径长度(WPL)最短的树,可以构造最优编码,用于数据传输,数据压缩等方向

    下面是二叉树和哈夫曼树

    这里写图片描述

    二、概念

    • 路径:树中一个结点到另一个结点之间的分支序列构成两个结点间的路径
    • 路径长度:路径上的分支数目
    • 树的路径长度:树根到每个结点的路径长度的和
    • 结点带权路径长度:结点到树根的路径长度与结点的权的乘积
    • 树的带权路径长度:树中所以叶子结点的带权路径长度之和(WPL)
    • 最优二叉树:在叶子个数n以及各叶子的权值确定的条件下,树的带权路径长度WPL最小的二叉树

    三、哈夫曼树的构造(以下举例以5,6,2,9,7森林为例)

    1、根据给定的n个权值(W1,W2,W3….)构造n棵二叉树的集合F={T1,T2,T3..}其中每棵二叉树Ti只有一个带权为Wi的根结点,其左右子树为空

    这里写图片描述

    2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,它俩的双亲的权值是它俩权值之和(如下图出现两个7,不用担心,不管哪个7和6匹配都不会有问题)

    这里写图片描述

    3、通过(2)得到两棵构成新的二叉树

    4、重复(2)(3)操作,直到最后为一棵树为止,这棵树便是哈夫曼树

    这里写图片描述


    这里写图片描述


    这里写图片描述


    四、哈夫曼编码

    哈夫曼最大的目的是为了解决当你远距离通信(电报)的数据传输的最优化问题

    比如文字内容”ABCDEF”,通过二进制数据表示

    这里写图片描述

    传输数据为:“000001010011100101”按照3位一分来译码即可,但可以想象假如文字多了,数据量也是相当的大,而且某写字出现的频率都是不同的“中文的,了,….”频率大

    所以需要前缀编码来进行编码(哈夫曼思想)

    前缀编码:设计长短不等的编码,必须是任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码

    因为每个字母的出现频率是不同的,我们假设给每个字母分配权值:A:27,B:8,C:15,D:15,E:30,F:5,首先按照它们的权值进行构造哈夫曼树

    这里写图片描述

    将所有权值左分支改为0,右分支改为1.

    这里写图片描述

    得到相应字符的的传输数据

    这里写图片描述

    下面是通过哈夫曼编码得到,可以看出,频率高的字符数据变的少,这样如果在很多字符下,会大大减少存储率和传输成本

    • 原编码二进制串:000001010011100101
    • 新编码二进制串:01100110100111000
    展开全文
  • 前缀编码:如果在一个编码方案中,任何一个编码都不是其他任何编码的前缀(最左子串),则称该编码是前缀编码。 分析: 如上图,不等长编码方案1是前缀编码; 分析如下:在不等长编码方案1中,a,b,c,d为四...

    前缀编码:

    如果在一个编码方案中,任何一个编码都不是其他任何编码的前缀(最左子串),则称该编码是前缀编码。

    前缀编码怎么判断

    如上图,不等长编码方案1是前缀编码;

    分析如下:

    在不等长编码方案1中,a,b,c,d为四个字符,其对应编码0,10,110,111中,任意一个编码(四个里面随便选)都不是其他任何编码的前缀,比如选择a的编码0进行比对,你会发现 10,110,111都不以0为前缀(都不以0开头)。 

     

    如上图,不等长编码方案2不是前缀编码;

    分析如下:

    四个编码中,随便选一个,如果选0,会发现01,010都是以0为前缀,所以不符合前缀编码的定义,分析结束。

    不知道大家有没有隐约有种意识,等长编码一定是前缀编码!

    例如两位编码,00,01,10,11就是,同理,三位、四位...n位。

    前缀编码作用 :

    前缀编码可以保证对压缩文件进行解码时不产生二义性,确保正确解码。

    公号众陆小马获取更多资料。

    哈夫曼编码:

    对于一颗具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的路径上,各分支的赋值分别构成一个二进制串,该二进制串就成为哈夫曼编码。

    哈夫曼编码的主要思想:

    在进行数据压缩时,为了使压缩后的数据文件尽可能短,可以采用不定长编码。

    其基本思想是:

    未出现次数较多的字符编以较短的编码,为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码,可以利用哈夫曼树来设计二进制编码。

    哈夫曼树满足两条性质:

    性质1  哈夫曼树是前缀编码。

    性质2  哈夫曼树是最有前缀编码。

    对于包含n个数据字符的文件,分别以它们出现的次数为权值构造哈夫曼树,则利用该树对应的哈夫曼编码对文件进行编码,能使该文件压缩后对应的二进制文件的长度最短。

     

    展开全文
  • 哈夫曼树,哈夫曼编码

    千次阅读 2021-08-02 14:33:58
    基础概念 结点的度:二叉树结点的分支数目, 也就是孩子结点的个数。比如,度为1,表示有一个节点; 度为2,表示有两个结点... 哈夫曼树至少是满二叉树, 或者完全二叉树。 权值:每一个叶子结点,都设置一个值,...

    基础概念

    结点的度:二叉树结点的分支数目, 也就是孩子结点的个数。比如,度为1,表示有一个节点; 度为2,表示有两个结点;度为2,表示没有结点。叶子结点度为0,因为没有孩子结点。 

    各种结点个数的关系:假设N0 = 叶子结点,度为0的结点总数。N1 =度为1的结点总数。N2 = 度为2的结点总数。

    N=所有结点总数之和。

    那么有以下公式:

    所有树:N=N0+N1+N2

    满二叉树:N1=0, N= 2N0 - 1。 哈夫曼树至少是满二叉树, 或者完全二叉树。

    权值:每一个叶子结点,都设置一个值,这个值就是权值。

    哈夫曼树

    哈夫曼树也叫最优二叉树。给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)

    什么是带权路径长度:

    看上图, 所有叶子结点的权值 × 深度,之和是带权路径长度。带权路径长度最小的树就是哈夫曼树。

    如何构建哈夫曼树:

    假设有n个权值结点,以及根据这些结点生成n棵只有一个结点的树, 也就是树集合F:{T1, T2,.....Tn},

    1. 从集合F中取出两个最小权值的树.  

    2. 取出的两个结点作为左右结点, 小的在左边,大的在右边。 跟结点是权值和的结点,  由此组成一个树.

    3. 把生成的树,再次返回集合F. 这颗新树的权值是左右结点权值的和.

    4. 重复1,2,3步骤, 直到集合F只剩下一颗树. 这颗树就是哈夫曼树.

    实践如下:

    假如有权值列表:[2, 5, 1, 4, 3]

    1. 先从列表里取出两个最小值1和2,组成以3为跟结点的一颗树。[ 5, 4,  3,3]

    2. 取出这时取值列表里两个最小值3和3,此时权值列表:[ 5, 4,  6]

    3. 取出这时取值列表里两个最小值4和5,此时权值列表:[ 6, 9]

    4. 取出这时取值列表里两个最小值6和9,此时权值列表:[ 15]

    5. 此时权值列表只有一颗树, 结束。

    带权路径长度是:1 × 3 + 2×3+3×2+4×2+5×2 =  27

    什么是同权不同构:

    同样一组权值列表, 有时, 可以构建出不同形状的树, 但是带权路径长度还是一样。 比如构建中间出现两个相同权值的结点, 新加结点可以放左边也可以放右边,造成了两种不同形状的树。

    这种情况都是允许的,选哪棵树都可以。

    哈夫曼编码

    编码是为了给权值列表中的权值数值分别用0,1编码。在哈夫曼树上,左分支边是0, 右分支边是1。 由此构成编码。如下图,依旧采用上面举例的哈夫曼树:

    编码后,1: 000,2:001, 3:01, 4:10, 5:11

     这样有什么用处呢? 请看这一穿字符:[ABCABDBBDBEDEED]

    A出现2次,B出现5次,C出现1次,D出现4次,E出现3次。这也正好是上面举例的权值列表。 

    那编了这些码有什么用呢? 用来压缩。 是哈夫曼树的作用。

    没有压缩前一个字符用定长的3位表示, 总共需要45位。压缩后是不定长的,而且你会发现出现次数越多的编码长度越短。比如B出现5次,编码是11, 而C只出现一次编码是000。

    压缩后是:001 11 000 001 11 10 11 11 10 11 01 10 01 01 10 

    总共是33位。压缩了12位。

    什么是前缀遍码:

    哈夫曼编码就是前缀编码。 就是说,不能让一个字母的二进制代表数,为另一个字母的二进制代表数的子串。就是说,不会出现01代表一个字母, 011又代表一个字母。

    哈夫曼编码是如果做到的呢?

    简单的说,因为都是叶子结点。所以任何一个权值结点,不可能出现在某一个权值的路径上。

    哈夫曼是从叶子节点开始构造,构造到根节点的,而且构造时,都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况,只会出现在终点的情况下因此不会出现01代表一个字母, 011又代表一个字母。

    图像压缩

    使用哈夫曼编码是无损压缩。

    哈夫曼编码不是图像压缩的所有,是其中一个环节。不然压缩比才大约有1:0.7。

    展开全文
  • 哈夫曼树的应用——哈夫曼编码 附:前缀码 基本概念: 需要了解的一些基概念: 路径:结点序列满足是的双亲。 路径长度:路径的分支数。L=k-1 扩充二叉树:在一般二叉树中,将原来的每个空指针都指向一个特殊...
  • 1.前缀编码 首先对于一个串可以用等长的二进制位表示,这样就叫做固定长度编码。如果可以用不等长的二进制位表示,则称之为可变长度编码。那么对于那些频度高的字符我们采用短二进制位编码,出现频度低的采用长二...
  • 浅谈 前缀编码哈夫曼编码

    千次阅读 2019-08-02 08:08:54
    1 前缀编码 1.1 前缀编码概念 1.2 前缀编码实例分析(简洁易懂) 1.3 前缀编码作用 2 哈夫曼编码 2.1 哈夫曼编码概念 2.2 哈夫曼编码的两条性质 2.3 哈夫曼编码的两条性质的证明(摘取自严蔚敏老师的教材) ...
  • 最优二叉树--哈夫曼树和最优前缀编码--哈夫曼编码

    万次阅读 多人点赞 2017-05-18 11:56:25
    1.最优二叉树的定义最优二叉树又称哈夫曼树,是一种带权路径长最短的树。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权(比如字符在某串中的...
  • 哈夫曼树与哈夫曼编码

    千次阅读 2020-10-19 18:05:30
    介绍哈夫曼树及哈夫曼编码
  • 头歌数据结构构建哈夫曼树及编码 第1关构建哈夫曼树 第2关根据哈夫曼树构建哈夫曼编码 通过哈夫曼树的构造,深刻理解二叉树的构造。...第二关:根据构建好的哈夫曼树构造字符的前缀编码(哈夫曼编码)。
  • 哈夫曼树 哈夫曼树的定义:设二叉树具有 n 个带权值的叶节点,那么从根节点到各个叶节点的路径长度与相应叶节点权值的乘积的和,叫...哈夫曼编码就是规定哈夫曼树中的左分支为 0,右分支为 1,从根节点到每个叶节点所经
  • 【数据结构】哈夫曼树、哈夫曼编码

    千次阅读 多人点赞 2022-05-09 20:38:24
    哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明,这到底是一颗什么样的树呢? 刚才我们学习了树的带权路径长度(WPL),而哈夫曼树(Huffman Tree)是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,...
  • 哈夫曼树及哈夫曼编码详解

    千次阅读 2021-10-28 21:53:42
    的内路径长度:除叶结点外,从根到中其他所有结点的路径长度之和; • 的外路径长度:从根结点到中所有叶子结点的路径长度之和; • 扩充二叉树:除叶子结点外,其余结点都必须有两个孩子,也称为2-...
  • (1)定长编码 我们要传输一条数据: i like like like java do you like a java //共40个字符 通过Ascii码将其转化为对应的二进制形式 http://tool.alixixi.com/ascii2/ 按照二进制来传递数据,总长度为359(包括...
  • 【数据结构】哈夫曼树及哈夫曼编码实现(C语言)

    千次阅读 多人点赞 2022-02-12 11:13:38
    哈夫曼树1.1 基本概念1.2 构造哈夫曼树1.3 哈夫曼树的类型定义1.4 哈夫曼树创建的算法实现2. 哈夫曼编码实现2.1 哈夫曼编码2.2 完整代码2.3 运行结果 1. 哈夫曼树 1.1 基本概念 路径:指从根结点到该结点的分支序列...
  • 哈夫曼树,又称最优树,是一类带权路径长度最短的树。下面有几个概念:(1)路径。树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。(2)路径长度。路径上的分枝数目。(3)树的路径长度。从树根到每一个...
  • 哈夫曼树与哈夫曼编码;哈夫曼树与哈夫曼编码;编码;前缀编码;前缀编码;树的路径长度定义为;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;哈夫曼树; 2.在 F 中选取其根结点的权值为最小的两...
  • 一,哈夫曼树的基本概念 路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点的路径长度:两结点之间路径上的分支数 树的路径长度:从树根到每一个结点的路径长度之和.记作:TL 权...
  • 震惊!原来哈夫曼编码还能这样玩
  • 一篇文章100个字符,99个字符是 e e e,那么可以给 e e e 编码为0,只用一个比特位进行编码,剩余的最后一个字符为 {a-z} 中任意的一个字符,使其前缀编码值为 1,然后使用 5 个比特位进行编码。这样,100 个字符...
  • 一、什么是哈夫曼编码? 1.文件编码 文件是由字符构成的,ACSII码中大概包含100个可打印的字符,每一个字符都有其特定的编码,扩展ACSII码为8位,也就是说不同的字符都需要用8位二进制位来编码,这是一种等长码。 ...
  • 最优前缀编码哈夫曼树及编码)问题 问题 给定字符集C=/left/x1,x2,…,xn/right/C=/left/{x_1,x_2,…,x_n /right/}C=/left/x1​,x2​,…,xn​/right/和每个字符的频率f(xi),求关于C的一个最优前缀码。
  • 文章目录哈夫曼树的构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树的构建和...
  • 题目背景:介绍什么是哈夫曼树和哈夫曼编码, 不影响做题 哈夫曼树(Huffman Tree)又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根...
  • 对所建的哈夫曼树,根据左0右1的原则,对各结点进行编码。设计一个算法,对给定的若干码串进行相应的解码,并输出解码结果。 Input: 有多组测试数据,每组数据由结点信息和码串两部分组成。结点信息部分的第一行为...
  • 哈夫曼树与哈夫曼编码及代码实现

    万次阅读 多人点赞 2020-03-18 12:43:30
    哈夫曼树与哈夫曼编码的理解 数据压缩 含义 通过对数据重新的编码,减少数据占用的空间存储;使用的时候再进行解压缩,恢复数据的原有特性。 类别 无损压缩——压缩过程没有数据丢失,解压得到原有数据特性。 有损...

空空如也

空空如也

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

哈夫曼树前缀编码

友情链接: xuebao.rar