导航:首页 > 源码编译 > 哈尔曼编码是什么算法

哈尔曼编码是什么算法

发布时间:2024-01-25 14:22:09

❶ 哈夫曼编码(贪心算法

参考: 哈夫曼编码

哈夫曼编码是一种十分有效的编码方法,广泛应用于 数据压缩
通过采用 不等长 的编码方式,根据 字符频率的不同 ,选择 不同长度的编码 ,对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。

下面看一个例子:
假如我们有一个包含1000个字符的文件,每个字符占1个byte(1byte=8bits),则存储这100个字符一共需要8000bits。这还是有一些大的
那我们统计一下这1000个字符中总共有多少种字符,原来需要8bit来表示一个字符,如果使用更少的位数来表示这些字符,则可以减少存储空间。
假设这1000个字符中总共有a、b、c、d、e、f共6种字符,使用使用3个二进制位来表示的话,存储这1000个字符就只需要3000bits,比原来更节省存储空间。

或许还可以再压缩一下:
根据字符出现的 频率 给与字符 不等长 的编码,频率越高的字符编码越短,频率越低的字符编码越长。
它不能像等长编码一样直接按固定长度去读取二进制位,翻译成字符,为了能够准确读取翻译字符,它要求一个字符的编码不能是另外一个字符的前缀。

假设a、b、c、d、e、f这6个字符出现的频率依次降低,则我们可以给与他们这样的编码

假如字符的出现频率如图所示,按照这样的编码表示的话,总位数如图,一共2100bits,更加节省空间了

贪心策略:频率小的字符,优先入队。

步骤:
1.将每一个字符作为节点,以出现频率大小作为权重,将其都放入 优先队列 中(一个最小堆);
2.每次出队两个节点并创建一个父节点,使其权值为刚刚出队的节点的权值和,并且为两个节点的父节点(合并)。然后将这个树入队。
3.重复操作2,直到队列中只有一个元素(此时这个元素表示形式应该为一个树)时,完成创建。

创建好了树,该怎么编码呢?
我们对一个哈夫曼树,从父节点开始的所有节点,往左边标0,右边标1。那么到达叶子节点的顺次编码就可以找到了。

C:字符集合
Q:优先队列
EXTRACT-MIN:传入一个队列,出队最小的元素
INSERT:将z插入到Q中

当for循环结束之后,此时队列中只有一个元素,就是我们需要的哈夫曼树,最后返回此树即可。

假设T树已经是一个最优的树,假设x、y的频率小于等于最低处的a、b,然后交换x、a,y、b。

计算代价是否发生变化。
比如这里比较 T 变成 T ’ 后代价是否变化,发现代价变小或不变。

同理T’到T’’,又因为T本来假设就是最优的,所以只能相等
所以T’’也应该符合条件,即贪婪算法,每次取最小的两个节点出来这种做法是正确的

阅读全文

与哈尔曼编码是什么算法相关的资料

热点内容
绿地回收App怎么登陆 浏览:656
iapp转跳QQ源码 浏览:348
深入理解nginx源码 浏览:951
串口发送命令 浏览:842
程序员每天上班很累 浏览:279
javasetlayout 浏览:91
空调压缩机用多大的压力 浏览:993
python爬虫视频教程下载 浏览:237
php53以上 浏览:810
iphone手机怎么用安卓应用 浏览:492
本地文件如何传到华为云服务器 浏览:383
加密ic卡在电脑怎么复制 浏览:522
鄞州繁裕三村附近启蒙编程学校 浏览:555
单片机里code什么意思 浏览:182
linux修改umask 浏览:536
编程锁的发展 浏览:346
唯词app怎么改密码 浏览:72
魔兽世界表情命令 浏览:985
智能还款信用卡源码 浏览:554
zoo文件夹 浏览:762