[参与有奖]给你一串编码，你有什么办法把他压到最短？【哈夫曼编码】

lu10086 · 发表于 7 天前

哈夫曼编码重点是构建哈夫曼树，每次取最小的两棵树合并到一起就行

小L鱼 · 发表于 7 天前

哈夫曼是从最底下往上长，逐步取权值最小的两个节点，再合并为一个新的节点，将问题规模逐渐减少，最后就能求出全局最优，对吗？

iHobe · 发表于 7 天前

脑子跟不上~

超燃陀螺 · 发表于 7 天前

看不懂qaq

PhilMao · 发表于 7 天前

几十年前学过

13351890899 · 发表于 7 天前

学习了

王星云 · 发表于 7 天前

那我先标记未读，好好看完我看看那3道题。

神荼Q · 发表于 7 天前

这个压缩可以，但是后期不一定能看懂呀

清风20260225 · 发表于 7 天前

有点打脑壳。加油

changkai09 · 发表于 7 天前

学习了，脑子有点跟不上

depart · 发表于 7 天前

哈夫曼编码的讲解太透彻了！从人物故事到手绘建树、代码落地，把最优压缩的原理讲得明明白白，也了解到它在日常文件格式里无处不在，收获很大。

Summeringg · 发表于 7 天前

转代码那块就无法继续了

rongbin · 发表于 7 天前

涉及的知识越来越深太高了，太难了

15257288806 · 发表于 7 天前

超标了看不懂了开始

我不是熊大 · 发表于 7 天前

我是真学不会啊

李安昭 · 发表于 7 天前

好厉害啊

成思宁 · 发表于 7 天前

完全看不懂

桐谷明日奈 · 发表于 7 天前

哈夫曼编码吗。。。小登要听不懂了

思想90 · 发表于 7 天前

这是手把手带着用C++把哈夫曼编码从头到尾撸了一遍，从为啥要压缩，哈夫曼树怎么建，编码表怎么生成，到怎么编码解码，怎么算压缩率，完整代码和运行结果也摆出来了，也说了说哈夫曼的短板
思考题1: 对于字符串"AAAAAP"，字符'A'频率为5，'P'频率为1。构建哈夫曼树时，优先队列按频率升序弹出，P(1)先出，A(5)后出合并。因此P为左子树（编码'0'），A为右子树（编码'1'），最终输出A的编码为"1"，P的编码为"0"。而特判path==""是处理文本只有单一字符的情况。这时候哈夫曼树只有一个根节点，而且这个节点就是叶子节点。如果不做特判，递归遍历时path一直为空，会让这个字符的编码是空字符串，无法进行后面的压缩和解压。特判赋予其默认编码保证了单字符文本的编码完整性
思考题2: 所有字符码长之和有可能比定长编码更差。哈夫曼编码的核心目标是最小化带权路径长度，就是最小化平均码长，不是单纯最小化所有字符码长的算术和。例子：假设字符集为四个字符，频率分别是0.5，0.25，0.125，0.125。哈夫曼树把两个0.125合并成0.25，再跟0.25合并成0.5，最后再和0.5合并。这个时候四个字符的码长分别是1，2，3，3，码长之和是9，但是定长编码的码长都是2，码长之和是8，在这样的分布下，哈夫曼编码的总码长劣于定长编码
思考题3: 压缩短文本时码表会让文件变大。对于只有10个字符的短文本，假如有5种不同字符，原始体积只有10字节，压缩后除了比特流，还需要附带包含字符，编码长度和具体编码值的头部码表。因为码表自身也有结构性冗余，占用空间往往远超短文本压缩所省下的比特数，所以总体积膨胀。
真实工程可以用这个方案解决：设定一个压缩阈值，对小于阈值的文件直接明文存储，不再压缩

jerry.0 · 发表于 6 天前

看不懂了0.0

账号		自动登录	找回密码
密码			立即注册

[技术交流] [参与有奖]给你一串编码，你有什么办法把他压到最短？【哈夫曼编码】

评分

点评

评分

点评

点评

评分

点评

评分