--- title: 赫/哈/霍 夫曼(Huffman)编码 游程编码 url: 'https://yayi.site/archives/赫哈霍夫曼huffman编码游程编码' categories: 算法与设计 cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/三ノ·輪 銀.png' tags: 'Huffman,游程编码' abbrlink: db061071 date: 2020-09-23 17:47:45 updated: 2021-05-14 22:05:10 ---  ## 数据压缩算法 ### 游程编码 n\*\*分为定长游程编码和变长游程编码两类。\*\* n\*\*定长游程编码是指编码的游程所使用的位数是固定的，一旦灰度相同且连续的个数超过了固定位数所能表示的最大值，则转入下一轮游程编码。\*\* n\*\*变长游程编码则是指不同范围的游程使用不同位数来进行编码。\*\* \*\*游程编码适合于二值图像编码，原因是二值图像的每一行（列）都是由若干个黑白像素段交替出现的，就可以将二元序列转换为游程长度的序列\*\* \| Y \| Y \| Y \| Y \| Y \| G \| \|:----:\| --- \| --- \| --- \| --- \| --- \| \| G \| B \| B \| B \| B \| Y \| \| .... \| \| \| \| \| \| \| \| \| \| \| \| \| 5X5像素中，yellow blue green 三种颜色，分别标志为 Y B G 顺序下来就是YYYYYGGBBBBY ...... 你可以发现，很多时候一幅图像总是有很多重复的像素。 所以我们可以使用Y4 表示4个Y 。这样就只用了2个字符。重复操作。Y4G2B4Y.... 解码的时候，逆过程就可以了。 我们也可以发现如果只有一种颜色的地方，如G1 ，反而由一个字符变成 了两个字符。如果一幅图像，重复很少，那么反而会使编码更大了。 \~\~当只有黑白的时候。那么可以这样表示，去掉 W B , 用 黑白的数字表示 。默认以白色开头，黑色开头的加上0 表示。\~\~==文本类黑纸白字图像好用这个== ### 赫/哈/霍 夫曼(\*\*Huffman\*\*)编码 ==核心原理就是利用概率学，把经常出现的用更短的编码来表示。== \*\*哈夫曼编码属于变长编码，是一种平均长度最短的即时可译码\*\* n\*\*该编码对最常出现的符号赋予最短的码字，然后按符号出现概率递减顺序逐个赋予次长的码字。因此，使编码的平均长度最短。\*\* !\[image-20200923164733529\](http://img.yayi.site/csdn/d8e5d4374e569a3c5f184e4ce7c20242.png-watermaskStyle) $$ p_i是s_i的出现概率，l_i,是对s_i编码的码字长 $$ $$ L_{avg} 是衡量一个压缩算法的压缩率。 $$ #### 举例 \*\*信号源\*\* s={s1, s2, s3, s4, s5, s6}，其概率分布为p1=0.4, p2=0.3, p3=0.1, p4=0.1, p5=0.06, p6=0.04，求其哈夫曼编码 \| S1 \| 0.4 \| \| \| \| \| --- \| ---- \| --- \| --- \| --- \| \| S2 \| 0.3 \| \| \| \| \| S3 \| 0.1 \| \| \| \| \| S4 \| 0.1 \| \| \| \| \| S5 \| 0.06 \| \| \| \| \| S6 \| 0.04 \| \| \| \| 1. 将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。 2. 把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。 3. 重复上述做法，直到最后剩下两个概率为止。 4. 从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码 1-3： !\[image-20200923171344107\](http://img.yayi.site/csdn/03da91a697f508cb91d7b2331344d770.png-watermaskStyle) 4： !\[image-20200923172758031\](http://img.yayi.site/csdn/2bc99c5fb08e94db9349cb8a8a004308.png-watermaskStyle) 括号 上部分表0 下半部分表1 （上1下0也行，选定，就不要改了） ==括号作为二叉树，沿路径到到s即可编码== 如 这里的 0.6 为根结点 s1的编码为 0 s2 的编码为 10 。从0.6 根结点开始 到左孩子结点 !\[image-20200923173330395\](http://img.yayi.site/csdn/ff19c0fb51b8a8b6a75177f4f5ea177a.png-watermaskStyle) s3:110 根-\> 右孩子 -\> 左孩子 !\[image-20200923173311871\](http://img.yayi.site/csdn/cb0842d4031bd2aff04a6c19f0b26da2.png-watermaskStyle) s4: 1110 依次类推。 唯一可解码和即时编码。