侧边栏壁纸
  • 累计撰写 278 篇文章
  • 累计创建 3 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

【数据结构】赫夫曼树及其应用

xuanxuan
2021-05-06 / 0 评论 / 0 点赞 / 4 阅读 / 3307 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2024-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

前言:

最基本的压缩编码方法——赫夫曼(huffman)编码。

在了解赫夫曼编码之前,我们必须了解一下赫夫曼树,赫夫曼编码就是基于赫夫曼树实现的。

相关视频——【C语言描述】《数据结构和算法》_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

相关书籍——《大话数据结构》

我的小站——半生瓜のblog,同步更新哦。


@TOC


1.赫夫曼树的定义与原理

  • 结点的路径长度

    • -从根节点到该结点的路径上的连接数。
  • 数的路径长度

    • -树中每个叶子结点的路径长度之和。
  • 结点带权路径长度

    • -结点的路径长度与结点权值的乘积。
  • 树的带权路径长度(WPL)

    • -是树中所有叶子结点的带权路径长度之和。
  • (数结点间的连线相关的数叫做权,Weight)


其中:带权路径长度(WPL)最小的二叉树叫做赫夫曼树。

带权路径长度(WPL)的值越小,说明构造出来的二叉树性越优。


2.构造赫夫曼树的过程

初识森林

在这里插入图片描述

在森林中选出两棵根节点的权值最小的二叉树,小的放左边,大的放右边。

在这里插入图片描述

合并两颗选出的二叉树,增加一个新结点作为新二叉树的根,权值为左右孩子的权值之和。

在这里插入图片描述

再从剩下的森林里面选出权值最小的二叉树,如果比第一次合并的结点权值小就放左边,反之,放右边。

在这里插入图片描述

再次进行合并。

在这里插入图片描述

第二次合并完成,第三次合并同理。

在这里插入图片描述

合并完成,这个二叉树就是赫夫曼树。

3.赫夫曼编码原理


补充:

赫夫曼研究这种最优树的目的是为了解决当年远距通信(主要是电报)的数据传输的最优化问题。


名词解释:

  • 定长编码
    • -像ASCII编码,用八位二进制数来表示一个字符。
  • 变长编码
    • -单个编码的长度不一致,可以根据整体频率来调节。
  • 前缀码
    • -所谓的前缀码,就是没有任何码字是其他码字的前缀。

编码过程(encode):还是利用上面的赫夫曼二叉树。

上图为构造赫夫曼树的过程权值显示。

下图为将权值左支改为0,右支改为1后的赫夫曼树。

在这里插入图片描述

在这里插入图片描述

我们对这4个字母(ABCD)用其从树根到叶子所经过路径0或1来进行编码。

例如原文字内容是ABCD。

原编码二进制串:000001010011(共12个字符)

新编码二进制串:010110111(共9 个字符)

也就是说我们的数据被压缩了,节约了25%的存储空间或者传输成本,随着字符的增加和字符权重的不同,这种压缩会更加显出其优势。


解码过程(decode):

发送方和接收方必须要约定好同样的赫夫曼编码规则,由约定好的赫夫曼树可以成功解码。

0

评论区