jjzjj

【开卷数据结构 】哈夫曼编码

锡兰_CC 2023-11-29 原文

在上文中，我们了解了哈夫曼树的基本概念和构造算法，那么哈夫曼树究竟有什么用呢？接下来讲的哈夫曼编码就是哈夫曼树的应用。

目录

🌺哈夫曼编码

🍁固定长度编码

🍁哈夫曼编码

🍁前缀编码

🌺文件的编码与译码

🍁编码

🍁译码

🌺哈夫曼编码

如果有一段文字【ABCDEF】要网络传输给别人，在进行数据压缩时，最简单的编码方法就是固定长度编码。

🍁固定长度编码

Q：什么是固定长度编码

A：在数据通信中，若对每个字符用相同的二进制位表示，称这种编码方式为固定长度编码。

有一段文字【BADCADFEED 】，我们可以用相应的二进制的数据表示，如图所示

字母ABCDEF
二进制字符000001010011100101

这样真正传输的数据就是编码后的 【001000011010000011101100100011】 （三十个字符），对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将长的非常的可怕，那么有没有什么方法可以对其进行压缩的吗？

🍁哈夫曼编码

我们假设各字母出现的频率如下

假设六个字母的频率为 A:27  B:8  C:15  D:15  E:30  F:5 ，合起来正好是 100 ,那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

 我们将左分支权值改为0，右分支权值改为1，那么该哈夫曼树就变成了

这时，我们对着六个字母用其从树根到叶所经过路径的 0 与 1 来编码，按照新的字母对应的二进制字符对【BADCADFEED 】进行编码，通过对比可以很明显的发现，字符数量减少了。

  • 固定长度编码：001000011010000011101100100011（共30个字符）
  • 哈夫曼编码：    1001010010101001000111100         （共25个字符）

哈夫曼编码的特点：

  1. 对频率高的字符赋以短编码。
  2. 对频率较低的字符则赋予较长一些的代码。
  3. 从而使得字符的平均编码长度减短，起到压缩数据的效果。
  4. 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

🍁前缀编码

Q：什么是前缀编码

A：前缀编码是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。

仔细观察，哈夫曼编码其实就是一种前缀编码

Q：前缀编码有什么优点

A：通过观察前缀编码（哈夫曼编码）【1001010010101001000111100】，以及其对应的哈夫曼树，我们发现不会出现容易混淆的编码，比如不会出现与1000，1001混淆的10，100编码。

对前缀编码的解析很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译成原码，再对余下的编码文件重复同样的解码操作即可。例如，码串 00101100 可被唯一的翻译成 0，0，101，100 .

🌺文件的编码与译码

🍁编码

有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表HC中找到此字符，将字符c转换为编码表中存放的编码串。

🍁译码

对编码后的文件进行译码的过程必须借助于哈夫曼树。具体过程是：依次读入文件的二码，从哈夫曼树的根结点(即HT[m])出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子HT[i]时便译出相应的字符编码HT[i]。然后重新从根出发继续译码，直至文件结束。

哈夫哈夫曼spanstylecolor数据结构c++c语言算法树

有关【开卷数据结构 】哈夫曼编码的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  5. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  6. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  7. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  8. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  9. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  10. FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2

    本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01  客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02  数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit

随机推荐