Huffman霍夫曼树，霍夫曼编码_霍夫曼编码树-程序员宅基地

技术标签： 算法  数据结构与算法  数据结构  

霍夫曼树基本概念：

 

路径：从一个结点往下到孩子或孙子结点之间的同理

路径长度：如结点1到结点7的路径长度=2

结点的权：将结点的某一属性值作为结点的权

带权路径长度：从根节点到该结点*该结点的权；如结点1到结点7的带权路径长度：7*2=14

的带权路径长度（WPL）：该树的所有叶子结点的带权路径长度之和

霍夫曼树：给定n个权值，构造一颗二叉树并由这n个权值作为数的叶子结点，且该树的带权路径长度（WPL）达最小，这样的二叉树成为最优二叉树，也叫霍夫曼树

霍夫曼树特点：权值越大的叶子结点离根节点越近

 

 霍夫曼编码：

编码规则：

（1）给定一个字符串，统计各个字符出现的次数，将次数作为权值构成霍夫曼树；例如“i like like like java do you like a java”转化为霍夫曼树为：

 

（2）规定路径向左为0，向右为1，则各个权值的路径即为他们的霍夫曼编码 

 注意：

（1）霍夫曼编码为前缀编码，即任何编码不会是其他编码的前缀（因为叶子结点）

 （2）若出现权值相同的结点，则根据排序方法不同，对应的霍夫曼编码也不完全相同，但压缩率是相同的。

代码实现：

以“i like like like java do you like a java”为例

结点

class ByteNode implements Comparable<ByteNode> {
    Byte data;//存放字符本身,注意用包装类方便存入集合中
    int weight;//权值，表示字符出现的次数
    ByteNode left;
    ByteNode right;

    public ByteNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(ByteNode o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "ByteNode{" +
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/rookie123222/article/details/118976767

智能推荐

QT：pyqt删除layout中的控件，移除、添加、替换控件_pyqt5中,我用groupbox设置了一个layout,layout开始有个控件,后来我用remo-程序员宅基地

文章浏览阅读1.5w次，点赞5次，收藏36次。一个折磨了我好久好久的问题，终于得到解决，哈哈哈！百度了很久，都没有找到具体方法，最后突然试出来了首先，在不知道layout中控件的情况下，要删除所有的子控件，可采用以下方法：for i in range(verticalLayout_3.count()): print(verticalLayout_3.count()) verticalLayout_3.itemAt(i..._pyqt5中,我用groupbox设置了一个layout,layout开始有个控件,后来我用removewidget

NET中的三种Timer的区别和用法(转)_net timer-程序员宅基地

文章浏览阅读495次。 最近正好做一个WEB中定期执行的程序，而.NET中有3个不同的定时器。所以正好研究研究。这3个定时器分别是： //1.实现按用户定义的时间间隔引发事件的计时器。此计时器最宜用于 Windows 窗体应用程序中，并且必须在窗口中使用。 System.Windows.Forms.Timer // 2.提供以指定的时间间隔执行方法的机制。无法继承此类。 System.Threading.Timer //3_net timer

Linux系统硬盘挂载命令_linux磁盘挂载命令-程序员宅基地

文章浏览阅读2.3k次。6. 挂载网络共享目录（需要先安装samba客户端）：mount -t cifs //192.168.1.2/share /mnt/share -o username=user,password=pass。7. 自动挂载命令（修改/etc/fstab文件）：/dev/sda1 /mnt/data ext4 defaults 0 0。5. 挂载U盘命令（需要先插入U盘）：mount /dev/sdb1 /mnt/usb。8. 强制卸载命令：umount -l /mnt/data。1. 挂载命令：mount。_linux磁盘挂载命令

python fpdf 中文加粗-程序员宅基地

文章浏览阅读585次。python fpdf中文加粗_python fpdf 中文

JedisPool的getResource()方法配置不当导致服务假死_jedispool.getresource()卡死-程序员宅基地

文章浏览阅读1.4w次。JedisPool的getResource()方法配置不当导致服务假死dubbo服务中使用jedis，在从JedisPool获取jedis时超时导致dubbo服务假死"DubboServerHandler-10.0.101.208:20880-thread-22" daemon prio=10 tid=0x00007f52f00b7800 nid=0x3d85 waiting on cond..._jedispool.getresource()卡死

WordPress安装简单详细教程（云服务器和轻量应用服务器搭建WordPress）_wordpress服务器部署教程-程序员宅基地

文章浏览阅读8.9k次，点赞4次，收藏61次。目录域名解析下面是WordPress网站具体搭建步骤：一、云服务器搭建wordpress二、轻量应用服务器搭建wordpress前言：不知道如何安装宝塔面板的朋友，可以先看下面的教程：1、轻量应用服务器安装宝塔面板（建站）2、云服务器安装宝塔面板（建站）3、阿里云服务器ECS搭建网站教程如何搭建一个wordpress网站呢？其实非常简单，你需要做的就是买一个域名和云服务器（或者轻量应用服务器）域名解析首先，进行域名解析，也就是将你的域名与服务器绑定_wordpress服务器部署教程

随便推点

linux之通过挂载iso镜像去安装文件_mount 挂载 iso 后,把文件拷贝到别的目录能安装么-程序员宅基地

文章浏览阅读2.2w次，点赞3次，收藏28次。我们首先需要知道什么是DNS?  DNS全名是Domain Name System,翻译成中文就是域名系统，它主要的作用就是将人们容易记忆的域名和不方便记忆的ip地址做转换，比如，当我们访问百度的时候，我们知道www.baidu.com就可以直接访问，但是却不知道它的ip地址，DNS就是将我们不容易记忆的ip地址转换成域名的方式查看内核是否开启路由功能sysctl -a|grep..._mount 挂载 iso 后,把文件拷贝到别的目录能安装么

拜占庭容错的三个基本理论（CAP/FLP/DLS）_容错理论-程序员宅基地

文章浏览阅读2.2k次，点赞4次，收藏5次。拜占庭容错的三个基本理论1) CAP理论 - "如果网路发生阻断（partition）时，你只能选择资料的一致性（consistency）或可用性（availability），无法两者兼得"。论点比较真观：如果网路因阻断而分隔为二，在其中一边我送出一笔交易："将我的十元给A"；在另一半我送出另一笔交易："将我的十元给B "。则此时系统要不是，a）无可用性，即这两笔交易至少会有一笔交易不会被接受..._容错理论

R语言中如何选择线性回归模型以及如何降维_r语言anova函数比较两个线性模型好坏-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏26次。一、模型比较的二中方式（1）使用anova（）函数比较二个模型fit1 Frost, data = states)fit2 anova(fit2, fit1)Model 1: Murder ~ Population + IlliteracyModel 2: Murder ~ Population + Illiteracy + Income + Frost _r语言anova函数比较两个线性模型好坏

CANoe中的离线回放+Trace回放_canoe数据回放-程序员宅基地

文章浏览阅读2.6k次，点赞28次，收藏42次。必须要说明的是，在实际工作中，有很多工程师将ReplayBlock当做一种报文回放功能使用。其实这是一种错误的用法。如果只想实现报文回放，有两种方式1：offline模式下，在Measurement配置窗口，使用数据回放功能。2：在trace窗口，使用import命令，也可直接导入数据文件，并显示在Trace窗口显示。如果文本很大，需要注意可能显示的数据会产生溢出和被覆盖。比较 1和2两种方式，建议在文件比较小的时候，直接在trace窗口添加。文件较大时使用offline模式下的数据回放。_canoe数据回放

论文关于mysql数据库文献_数据库论文参考文献-程序员宅基地

文章浏览阅读8.5k次，点赞4次，收藏18次。数据库论文参考文献论文的最后部分是由参考文献组成的，有时也会有附录。参考文献在论文中是有一些要求的，大都都是来源格式的要求。小编这次整理的是有关数据库论文的参考文献，大家可以参考参考。[1]基于关系数据库的关键词查询[J]. 林子雨,杨冬青,王腾蛟,张东站. 软件学报. 2010(10)[2]S-CBR:基于数据库模式展现数据库关键词检索结果[J]. 彭朝晖,张俊,王珊. 软件学报. 2008(0..._mysql文献

IDEA出现闪退或打不开的解决方法_idea重新安装后进入总是闪退-程序员宅基地

文章浏览阅读1.8k次。本身项目比较大，为了打开这个软件，可调节IDEA中安装的bin目录下有个。打开IDEA的时候过一会便闪退，可以再IDEA的右下角看到如下提示。（如果没有该提示，软件右下角也会有个红色感叹号，点开查看原因即可）闪退的多数原因大致是out of memory，内存溢出。查看任务管理器中的进程：（发现内存随时有溢出的情况）但也需要注意，该参数并不是越大越好，适中即可。只有个别原因是需要管理员权限就可执行！可以尽量减少软件的启动。_idea重新安装后进入总是闪退

推荐文章

热门文章

相关标签