哈夫曼编码、哈夫曼树

news/2024/7/24 13:46:59/

        已知一个文件中出现的各字符及其对应的率如下表所示。若采用定长编码,则该文件中字符的码长应为( )。若采用Huffman编码,则字符序列face的编码应为( )

字符abcdef
频率4513121695

        码长决定了可以显示几位字符,题中一共有6位,那么就应该是2 ^ 3 , 码长至少为3位。

       得出哈夫曼编码分为两步:

一、绘制哈夫曼树(哈夫曼树叫做带权最短路径树)

        首先获取两个最小的值(9,5)添加到树中,左边为较小的值,右边为较大的值。将两值相加得到新的节点 14

        再获取两个最小的值(13,12) 与新的节点作比较,发现13 和 12 都小于 新节点14,那就再画一个树,并获取新的节点 25

         两个树的排序位置也要遵循小的在左,大的在右。然后再次获取最小的两个值(45,16),然后发现 16大于14 而小于25,那么16和14组成新的树。生成新的节点 30

         最后只剩下45了,而45大于25,大于30,那么它只能作为单独一个节点加入到树中(哈夫曼树是二叉树的一种,最多能有左子树和右子树),将25和30相连生成新的节点55。

        到这第一步就完成了,生成了哈夫曼树。

第二步、生成哈夫曼编码

        在哈夫曼树中左子树标记为0,右子树为1

                将字符填入对应的结点中

         最后得出节点对应的编码:a:0 , b:101 , c:100, d: 111,e:1101, f : 1100

         face的编码应为(1100 0 100 1101 )

 


http://www.ppmy.cn/news/33723.html

相关文章

【Linux】环境变量(基本概念 常见环境变量 测试PATH 环境变量相关命令)

文章目录环境变量基本概念常见环境变量测试PATH别的环境变量通过系统调用获取或设置环境变量环境变量相关命令export: 设置一个新的环境变量set: 显示本地定义的shell变量和环境变量unset: 清除环境变量通过代码如何获取环境变量环境变量 基本概念 环境变量(environment vari…

ThreadPool线程池源码解析

ThreadPool线程池源码解析 文章目录前言一、基本使用二、执行流程三、源码分析ThreadPoolExecutor 中重要属性ThreadPoolExecutor 内部类Workerexecute()方法addWorker(command, true)方法runWorker(worker )方法getTask()方法shutdown和shutdownNow四、…

Java栈和队列·下

Java栈和队列下2. 队列(Queue)2.1 概念2.2 实现2.3 相似方法的区别2.4 循环队列3. 双端队列 (Deque)3.1 概念4.java中的栈和队列5. 栈和队列面试题大家好,我是晓星航。今天为大家带来的是 Java栈和队列下 的讲解!😀 继上一个讲完的栈后&…

1.9 日本蜡烛图技术之支撑和压力的其他含义

破低反涨和破高反跌形态 支撑和压力的研究不能局限于涨跌幅边界研究,用K线图来验证会注意到很多突破来临的信号破低反涨形态 一种移动和反向移动,价格跌破支撑,然后反弹重新上涨通常建立新的支撑线 破高反跌形态:突破压力后&…

hadoop理论基础(一)

1.hadoop的组成2 HDFS概述HDFS(Hadoop Distributed File System)是一个分布式文件系统(1)NameNode:存储文件的元数据;如文件名、文件目录结构、文件属性,以及每个文件的块列表和块所在的DataNode等。(2)DataNode:在本地…

【测试开发篇4】测试模型

目录 一、软件测试V模型 编码前 概要设计: 详细设计: 编码后: 单元测试&集成测试 系统测试 验收测试 V模型的特点 优点: 缺点: 二、软件测试W模型 编码之前: 编码的时候: 编…

Three.js——learn01

Three.js——learn01Three.js——learn01本地搭建文档通过parcel搭建Threejs环境1.初始化2.安装parcel设置打包位置3.设置目录结构QuickStart安装threejsindex.htmlindex.cssindex.js启动Three.js——learn01 本地搭建文档 登录GitHub搜索three.js git clone https://github…

KubeSphere All in one安装配置手册

KubeSphere All in one安装配置手册 1. 初始化 1.1 配置apt源 # vi /etc/apt/sources.list deb https://mirrors.aliyun.com/ubuntu/ focal main restricted universe multiverse deb-src https://mirrors.aliyun.com/ubuntu/ focal main restricted universe multiversedeb…

【多线程】多线程案例

✨个人主页:bit me👇 ✨当前专栏:Java EE初阶👇 ✨每日一语:we can not judge the value of a moment until it becomes a memory. 目 录🍝一. 单例模式🍤1. 饿汉模式实现🦪2. 懒汉模…

redhat httpd服务安装、访问浏览器及自定义访问页面

目录 1.查看本地仓库,如果没有配置,就在这目录创建一个 2.挂载 3.下载httpd服务 4.修改httpd配置文件 5.重启httpd服务 6.查看当前可用IP地址 7.随便用一个IP 看是否有东西 8.无法访问,原因是我们防火墙没有放行httpd服务 1.查看本地仓库&a…

Cookie和Session详解

目录 前言: Session详解 Cookie和Session区别和关联 服务器组织会话的方式 使用Tomcat实现登录成功跳转到欢迎页面 登录前端页面 登录成功后端服务器 重定向到欢迎页面 抓包分析交互过程 小结: 前言: Cookie之前博客有介绍过&#x…

HJ1 字符串最后一个单词的长度(JAVA)

目录 题目: 描述 输入描述: 输出描述: 示例1 解题思路: 总代码: 题目: 描述 计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注&#xff1a…

error: C1083: 无法打开包括文件: “QtGui/QApplication”: No such file or directory

Qt系列文章目录 文章目录Qt系列文章目录前言一、原因二、解决办法1.修改pro工程文件2.在main.cpp中三、总结前言 当我们从网上或者从打开别人的工程师,报错,C1083: 无法打开包括文件: “QtGui/QApplication”。 原因:Qt5里不再用QtGui模块&a…

动态规划算法

一、前言动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。二、解析动态规划算法1.特点①把原来的问题分解成了【要点相同】…

vue使用split()将字符串分割数组join()将数组转字符串reverse()将数组反转

1.split() 将字符串切割成数组 const str Hello Vue2 Vue3 console.log(str.split()) console.log(str.split()) console.log(str.split( )) console.log(str.split( , 2)) console.log(str.split( , 6))输出如下 1.split()不传参数默认整个字符串作为数组的一个元素&#xf…

Java Web 实战 15 - 计算机网络之网络编程套接字

文章目录一 . 网络编程中的基本概念1.1 网络编程1.2 客户端(client) / 服务器(server)1.3 请求(request) / 响应(response)1.4 客户端和服务器之间的交互数据1.4.1 一问一答1.4.2 多问一答1.4.3 一问多答1.4.4 多问多答二 . socket 套接字2.1 UDP 的 Socket API2.1.1 引子2.1.2…

嵌入式硬件电路设计的基本技巧

目录 1 分模块 2 标注关键参数 3 电阻/电容/电感/磁珠的注释 4 可维修性 5 BOM表归一化 6 电源和地的符号 7 测试点 8 网络标号 9 容错性/兼容性 10 NC、NF 11 版本变更 12 悬空引脚 13 可扩展性 14 防呆 15 信号的流向 16 PCB走线建议 17 不使用\表示取反 不…

web测试技术

一、Web 测试与传统测试的区别 相同之处 测试内容: 功能、性能、易用性、兼容性、安全性等 测试方法: 等价类边界值法、判定表法、状态迁移法,流程分析法、因果图法、错误猜测法等 测试手段: 人工测试、工具测试等不同之处 Web 测…

C++造轮子飙车现场之无锁、有锁环形队列实现

先看带锁的实现。 带锁版本 circular_queue.h // 头文件防卫 #ifndef CIRCULAR_QUEUE_H #define CIRCULAR_QUEUE_H#include <mutex> // 互斥量 #include <condition_variable> // 条件变量template <typename T> class CircularQueue { public:// 构造函数…

docker安装overleaf并升级texlive

20230321 0. 引言 之前在虚拟机安装了overleaf&#xff0c;应该是两年前的事情了&#xff0c;本来是想尝试一下overleaf更新了什么功能&#xff0c;但是没想到浪费了这么多时间。当时安装的还是2.5的版本&#xff0c;现在已经是3.5了。 在这个过程中&#xff0c;有几个地方需…