Unity开发者联盟收藏本站
发帖教程新人必读切换到宽版

 找回密码
 立即注册
Unity开发者联盟»论坛 › 3D Dev Asset 开发资源大全 › 学术研究 Scholarly › 哈夫曼编码与二叉字典树
返回列表 发新帖
查看: 167|回复: 0

哈夫曼编码与二叉字典树

[复制链接]
发表于 2023-2-18 16:03 | 显示全部楼层 |阅读模式
系列文章导引

    系列文章导引
开源项目

本系列所有文章都将会收录到GitHub中统一收藏与管理，欢迎ISSUE和Star。
GitHub传送门：Kiner算法算题记
哈夫曼编码

什么是编码

思考：在计算机当中是如何表示一个字符’a’的

有相关计算机基础知识的同学肯定都知道，我们的计算机其实是非常“笨”的，它只认识0和1，非黑即白，因此，无论我们要往计算机中存储什么信息，最终都是以二进制的形式存储，即存储了一段0和1的信息。
计算机中的编码

如果想要人眼去一一识别计算机中存储的0和1的信息，基本是不可能的，在我们人类的认知中，更容易让我们接受的是诸如：“a、A、0、1、2、3”等信息，因此，就需要将我们人类能够读懂的信息转换为计算机能够读懂的0和1的信息，这个过程，就是计算机中的编码。
概念

所谓编码，就是一种信息到另一种信息的映射规则。
定长编码与变长编码

定长编码

如：ASCII码就是一个定长编码。在我们的ASCII码表中，每一个字符占一个字节，而8个二进制位就表示一个字节，也就是说，我们的ASCII码是固定长度为8的二进制表示的定长编码，如字符’a’的ASCII码表示为：97,其8位二进制表示为：01100001。
定长编码的好处在于：由于定长编码代表一个字符的长度是确定的，因此，我们在编码和解码时都比较方便，直接按照这个长度截取并编码/解码即可。
  1. # 以下二进制位代表的是一个ASCII码字符的二进制串，请转换成实际的字符
  2. 01100001010000010011001000110000
  3. # 由于ASCII码是定长编码，每8个二进制位代表一个字符，因此，我们先将上面的二进制以8个为一个单位拆开
  4. 01100001 01000001 00110010 00110000
  5. # 然后针对每一段8位2进制找到期对应的ASCII代表的字符
  6.     a        A        20# 因此，上述二进制信息代表的是字符“aA20”
复制代码
变长编码

有效的变长编码：字符编码不能是其他字符编码的前缀（非绝对，只是比较常用）。如果把编码看成是二叉树上的路径，那么所有字符都落在叶子节点上。
  1. # 假设我们将a、A和0三个字符分别编码成以下信息：# a
  2. 01
  3. # A10# 011# 我们用一个二叉树来表示0和1的编码
  4.                     root
  5.                 /            \01
  6.            /        \       /      \0101
  7.                      a     A         0# 可以看出我们的字符都是落在了二叉树的叶子节点上
复制代码
变长编码的应用场景：在网络传输的过程中，通过变长编码提升网络传输的效率（需要传输的数据大小变小了，传输效率自然就高了）
哈夫曼编码

哈夫曼编码是最优的变长编码
统计字符出现频率

哈夫曼编码首先会对我们待编码的字符串进行统计，将每一个字符出现的频率统计出来
建树

统计出每一个字符的出现频率之后，会每次将所有频率中最低的两个字符合并创建成一颗二叉子树，这颗二叉子树的总频率就是两个字符出现频率之和。合并之后再从所有字符频率中（包括新合并子树的频率）再挑出两个最小的创建子树，依次类推，知道将所有字符都放到了一颗二叉树中。
编码

我们将每个路径按照左0右1的原则进行编号，那么，我们每个字符所代表的编码就已经呼之欲出了。
  1. # 假设一篇文章中出现了以下字符
  2. hello
  4. # 首先统计每个字符出现的频率
  5. h: 0.2
  6. e: 0.2
  7. l: 0.4
  8. o: 0.2# 递归地将每个字母按照出现频率最低的两两建树# 首先将h和e放到一颗二叉子树中0.4
  9.        /     \
  10.       h       e
  11. # 然后再将新建的子树放回概率池，剩余的字符概率最低的进行建树# 发现新建子树和字符o概率最低0.6
  12.           /       \
  13.          o        0.4
  14.                /       \
  15.               h         e
  16. # 最后将l于新建子树合并1
  17.             /        \
  18.            l         0.6
  19.                   /        \
  20.                 o          0.4
  21.                         /        \
  22.                        h          e
  23. # 接下来我们将每条边都按照左0右1的规则进行编号10 /         \1
  24.            l          0.60 /        \1
  25.                  o          0.40 /        \1
  26.                         h          e
  27. # 那么，我们每个字符的编码就出来了
  28. l: 0
  29. o: 10
  30. h: 110
  31. e: 111# 现在我们来对以下编码进行解码试试1101110010# 变长编码的解码规则是尽可能匹配更长的编码，匹配不上再缩小范围，按照这个规则，我们把编码划分为已下几块1101110010# 依次编码得
  32. h    e  l l  o
复制代码
公式



哈夫曼编码实际上是在求解上述公式，即根据出现概率来求解平均长度最短的码字。这也是为什么说哈夫曼编码是最优变长编码的原因。
代码实现
  1. // 利用小顶堆维护频率池最小的节点，npm i heapconst Heap =require("heap");classHaNode{
  2.   freq:number=0;
  3.   ch:string="";
  4.   left: HaNode =null;
  5.   right: HaNode =null;constructor(
  6.     freq:number,
  7.     ch:string,
  8.     left: HaNode =null,
  9.     right: HaNode =null){this.freq = freq;this.ch = ch;this.left = left;this.right = right;}}exporttypeHaffmanInfo={
  10.   root: HaNode;
  11.   codes: Record<string,string>;
  12.   codeKey: Record<string,string>;
  13.   freqInfo: Record<string,number>;};exporttypeHaffmanEncodeResult={
  14.     detail: Record<string,string>;
  15.     code:string;
  16.     freqInfo: Record<string,number>;
  17.     haffmanInfo: HaffmanInfo
  18. };classHaffmanCode{// 由于建树时需要每次获取两个出现频次最低的节点，因此利用小顶堆实现
  19.   heap: Heap<HaNode>;constructor(){this.heap =newHeap((a: HaNode, b: HaNode)=> a.freq - b.freq);}/**
  20.    * 统计每个字符出现的次数
  21.    * @param str
  22.    * @returns
  23.    */statistics(str:string): Record<string,number>{const map: Record<string,number>={};for(let c of str){if(map[c]===undefined) map[c]=0;
  24.       map[c]++;}return map;}/**
  25.    * 根据构建的二叉字典树构建成哈夫曼编码
  26.    * @param root 二叉树根节点
  27.    * @param prefix 当前节点的前缀字符串
  28.    * @param codes 储存字符和哈夫曼编码的映射关系，用于编码
  29.    * @param codeKey 储存哈夫曼编码与字符的映射关系，用于解码
  30.    * @returns
  31.    */__extra_code(
  32.     root: HaNode,
  33.     prefix:string="",
  34.     codes: Record<string,string>,
  35.     codeKey: Record<string,string>):void{if(root.ch !==""){
  36.       codes[root.ch]= prefix;
  37.       codeKey[prefix]= root.ch;return;}this.__extra_code(root.left, prefix +"0", codes, codeKey);this.__extra_code(root.right, prefix +"1", codes, codeKey);}/**
  38.    * 预处理哈夫曼编码的一些信息，如手机字符出现频次，创建小顶堆，建树，字符编码银蛇
  39.    * @param str
  40.    * @returns
  41.    */__predo(str:string): HaffmanInfo {// 统计每个字符出现的频次const map =this.statistics(str);// 按照频次将节点插入到小顶堆中
  42.     Object.keys(map).forEach((key)=>{this.heap.insert(newHaNode(map[key], key));});// 每次从小顶堆弹出两个元素（频次最少）合并成一个节点while(this.heap.size()>1){const a: HaNode =this.heap.pop();const b: HaNode =this.heap.pop();this.heap.insert(newHaNode(a.freq + b.freq,"", a, b));}const root: HaNode =this.heap.top();const codes: Record<string,string>={};const codeKey: Record<string,string>={};this.__extra_code(root,"", codes, codeKey);return{
  43.       root,
  44.       codes,
  45.       freqInfo: map,
  46.       codeKey
  47.     };}/**
  48.    * 编码
  49.    * @param str
  50.    * @returns
  51.    */encode(str:string): HaffmanEncodeResult {const info =this.__predo(str);const{ codes, freqInfo }= info;return{
  52.       detail: codes,
  53.       code: str
  54.         .split("").map((char)=> codes[char]).join(""),
  55.       freqInfo,
  56.       haffmanInfo: info
  57.     };}/**
  58.    * 解码
  59.    * @param str
  60.    * @param info 包含编码信息与字符映射信息等编码相关信息，用于解码
  61.    * @returns
  62.    */decode(str:string, info: HaffmanInfo):string{let pos =0;let res ='';let buff ='';const{codeKey}= info;while(str[pos]){
  63.         buff += str[pos++]if(codeKey[buff]){
  64.             res+=codeKey[buff];
  65.             buff ='';}}return res;}}const haffmanCode =newHaffmanCode();const{ detail, code, freqInfo, haffmanInfo }= haffmanCode.encode("hello, my name is kiner tang! would you like some milk?");
  67. Object.keys(detail).forEach((key)=>{console.log(`字符【${key}(出现频次：${freqInfo[key]})】的哈夫曼编码为：${detail[key]}`);});console.log("完整哈夫曼编码：", code);console.log(`解码：${haffmanCode.decode(code, haffmanInfo)}`);// 字符【 (出现频次：10)】的哈夫曼编码为：00// 字符【l(出现频次：5)】的哈夫曼编码为：010// 字符【!(出现频次：1)】的哈夫曼编码为：01100// 字符【s(出现频次：2)】的哈夫曼编码为：01101// 字符【n(出现频次：3)】的哈夫曼编码为：0111// 字符【o(出现频次：4)】的哈夫曼编码为：1000// 字符【t(出现频次：1)】的哈夫曼编码为：100100// 字符【,(出现频次：1)】的哈夫曼编码为：100101// 字符【d(出现频次：1)】的哈夫曼编码为：100110// 字符【?(出现频次：1)】的哈夫曼编码为：100111// 字符【i(出现频次：4)】的哈夫曼编码为：1010// 字符【m(出现频次：4)】的哈夫曼编码为：1011// 字符【a(出现频次：2)】的哈夫曼编码为：11000// 字符【g(出现频次：1)】的哈夫曼编码为：110010// 字符【w(出现频次：1)】的哈夫曼编码为：110011// 字符【h(出现频次：1)】的哈夫曼编码为：110100// 字符【r(出现频次：1)】的哈夫曼编码为：110101// 字符【u(出现频次：2)】的哈夫曼编码为：11011// 字符【y(出现频次：2)】的哈夫曼编码为：11100// 字符【k(出现频次：3)】的哈夫曼编码为：11101// 字符【e(出现频次：5)】的哈夫曼编码为：1111// 完整哈夫曼编码： 1101001111010010100010010100101111100000111110001011111100101001101001110110100111111111010100100100110000111110010011000011001110001101101010011000111001000110110001010101110111110001101100010111111001011101001011101100111// 解码：hello, my name is kiner tang! would you like some milk?
复制代码

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

×
回复

使用道具 举报

返回列表 发新帖
懒得打字嘛，点击右侧快捷回复 【右侧内容，后台自定义】
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Unity开发者联盟 ( 粤ICP备20003399号 )

GMT+8, 2024-6-27 14:23 , Processed in 0.151882 second(s), 26 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表