精华内容
下载资源
问答
  • MP3解码哈夫曼解码快速算法

    千次阅读 2013-12-18 12:31:47
    哈夫曼(huffman)解码用查表法,数据组织采用形结构,若采用二叉树,一次处理一位(bit),效率是比较低的。从一些杂志上看到关于哈夫曼(huffman)解码的快速算法介绍,直接用位流索引一次处理N(4  MP3解码处理主数据...

          哈夫曼(huffman)解码用查表法,数据组织采用树形结构,若采用二叉树,一次处理一位(bit),效率是比较低的。从一些杂志上看到关于哈夫曼(huffman)解码的快速算法介绍,直接用位流索引一次处理N(4<N<=32)位,这种方法实际上是不可行的,原因是构造出的码表很长,如果一次处理8位,可以编写程序构造出码表,不过可以肯定的是码表的长度会超过我们事先的想象,以至于没有多大的实用价值。一次处理多位(一位以上)码表中冗余度很大导致码表很长。

          MP3解码处理主数据(main_data)的第一步就是对主数据进行哈夫曼解码。MP3编解码用到的哈夫曼表由ISO/IEC 11172-3 的附录B中给出,大值区用到31张码表(其中第0、4、14号码表未使用),小值区用到两张码表。从ISO/IEC 11172-3复制出两张原始的码表来分析,解码大值区的码表:

    Huffman code table 7
     x  y hlen hcod
     0  0   1   1
     0  1   3   010
     0  2   6   001010
     0  3   8   00010011
     0  4   8   00010000
     0  5   9   000001010
     1  0   3   011
     1  1   4   0011
     1  2   6   000111
     1  3   7   0001010
     1  4   7   0000101
     1  5   8   00000011
     2  0   6   001011
     2  1   5   00100
     2  2   7   0001101
     2  3   8   00010001
     2  4   8   00001000
     2  5   9   000000100
     3  0   7   0001100
     3  1   7   0001011
     3  2   8   00010010
     3  3   9   000001111
     3  4   9   000001011
     3  5   9   000000010
     4  0   7   0000111
     4  1   7   0000110
     4  2   8   00001001
     4  3   9   000001110
     4  4   9   000000011
     4  5  10   0000000001
     5  0   8   00000110
     5  1   8   00000100
     5  2   9   000000101
     5  3  10   0000000011
     5  4  10   0000000010
     5  5  10   0000000000

     

    解码小值区的码表:

    Huffman code table 17
     x  y hlen hcod
     0  0  1   1
     0  1  4   0101
     0  2  4   0100
     0  3  5   00101
     0  4  4   0110
     0  5  6   000101
     0  6  5   00100
     0  7  6   000100
     0  8  4   0111
     0  9  5   00011
     0  10 5   00110
     0  11 6   000000
     0  12 5   00111
     0  13 6   000010
     0  14 6   000011
     0  15 6   000001

     

    所有码表中,大值区的x=0..15,y=0..15,码长hlen=1..19。

     

    一次处理多位应该如何实现呢?首先构造出码表,如果每次处理2比特,构造码表暂存数据时用4叉树;如果一次处理3比特,则用8叉树,以此类推。编程从一个文本文件中读入如上所示的原始的哈夫曼表数据,将其插入到N叉树中相应的位置。假如一次处理2位而码字(hcod)是5位(hlen=5),那么在hcod最后分别补上0和1凑足2的整数倍位数,这就导致了构造出的哈夫曼表冗余度,即一个码字对应多个码表中元素。一次处理的位数越多,构造出的码表的冗余度越大。

     

    根据自己解码设计构造出码比较费事,解码过程挺简单。

     

    实际编程中,可以用数组来存储N叉树,只需要将指针域的值改为元素在数组中的下标值。以大值区解码一次处理2比特为例,x和y取值范围为0..15,只需占用4比特;码长hlen取值范围为1..19,存储hlen只需5比特。存储一个码值只需要13比特,可以将一个码值存储在16位整数中,低4位是y,接下来的4位是x,再接下来的5位是hlen。高3位全为零表示该数组元素存储的是一个码值,最高位为1(表示负数)则其绝对什表示该数组元素存储的是数组的下标值。经过这样处理后解码大值区的码表“Huffman code table 7”:

    C代码:

    static short htbv7[72] = {
      -4, -68, 256, 256,  -8, -48, -64,1041, -12, -28, -40, -44, -16, -20, -24,2069,
    2645,2629,2644,2643,2357,2357,2372,2372,2341,2341,2386,2386,2129, -32,2128, -36,
    2309,2309,2356,2356,2371,2371,2355,2355,2084,2114,1812,1812,1857,1857,1856,1856,
     -52, -56, -60,1554,2052,2083,2098,2051,1811,1811,1841,1841,1840,1840,1826,1826,
    1313,1313,1538,1568, 769, 769, 784, 784};


     

    解码小值区的码表“Huffman code table 17”一次处理4比特:

    static short htc0[80] = {
     -16, -32, -48, -64,1026,1025,1028,1032, 256, 256, 256, 256, 256, 256, 256, 256,
    1547,1547,1547,1547,1551,1551,1551,1551,1549,1549,1549,1549,1550,1550,1550,1550,
    1543,1543,1543,1543,1541,1541,1541,1541,1289,1289,1289,1289,1289,1289,1289,1289,
    1286,1286,1286,1286,1286,1286,1286,1286,1283,1283,1283,1283,1283,1283,1283,1283,
    1290,1290,1290,1290,1290,1290,1290,1290,1292,1292,1292,1292,1292,1292,1292,1292};

    码表构造好了,如何解码呢?从码流中读入4字节暂存到unsigned int umask,解码大值区得到x和y:

    y = ptab[umask >> 30];	// 一次处理2比特,ptab指向码表(如ptab=htbv7)
    while (y < 0) {
    	umask <<= 2;
    	y = ptab[(umask >> 30) - y];
    }
    x = y >> 8;		// hlen
    num -= x;			// num为umask中剩余的比特数
    umask <<= x;
    x = (y >> 4) & 0xf;		// 得到x值
    y &= 0xf;			// 得到y值

    解码小值区得到y值的代码:

    C代码
    y = ptab[umask >> 28];		// 一次处理4比特
    while (y < 0) {
    	umask <<= 4;
    	y = ptab[(umask >> 28) - y];
    }
    x = y >> 8;	// hlen
    num -= x;
    umask <<= x;
    
    y &= 0xf;		// 得到y值

    每解码完一个码字,重新刷新umask和num。以上解码方法正确与否可以用“Huffman code table 7”或“Huffman code table 17”内的数据去检查。

    一次处理N比特肯定比一次处理1比特效率高。兼顾效率和存储空间开销,解码大值区采用一次处理2位到4位,解码小值区一次处理4位,这样比较好。

     

    展开全文
  • 一、设计题目对一幅BMP格式的灰度图像(个人证件照片)进行二元霍夫曼编码和译码二、算法设计(1)二元霍夫曼编码:①:图像灰度处理:利用python的PIL自带的灰度图像转换函数,首先将彩色图片转为灰度的bmp图像,此时每...

    一、设计题目

    对一幅BMP格式的灰度图像(个人证件照片)进行二元霍夫曼编码和译码

    二、算法设计

    (1)二元霍夫曼编码:

    ①:图像灰度处理:

    利用python的PIL自带的灰度图像转换函数,首先将彩色图片转为灰度的bmp图像,此时每个像素点可以用单个像素点来表示。

    ②:二元霍夫曼编码:

    程序流程图:

    详细设计:

    统计像素点频率,首先通过python自带的PIL库的图像像素点读取函数read()获取灰度图像的所有像素点,通过循环遍历每个像素点,将每个出现的像素点值以及其次数以键值对的形式放入到python的字典中。

    ①:首先构造用以表示节点的类,其中每个节点包括一下成员属性:

    self.left = left

    self.right = right

    self.parent = parent

    self.weight = weight

    self.code = code

    ②:遍历已经保存好的像素点频率字典,将图片中出现的像素点全部定义为叶子节点,通过类的code以及weight来表示对应的像素点值和该像素点出现的次数。

    ③:此时叶子结点中的权值为乱序,此时依据每个叶子结点的权重所有的叶子结点进行从小到大的排序;

    ④:每次取权值最小的两个节点最为要被替换的节点,将这两个节点的权值进行相加,然后生成新的节点,同时将这两个节点从叶子结点列表中去除,同时将新生成的节点放入叶子节点列表,同时对列表进行排序;

    ⑤:重复步骤④,直到列表中还剩下一个节点,此时这个节点便为头节点。

    3.

    ①:根据已经构造好的二元霍夫曼编码树,由叶子节点开始遍历整棵树,左边赋予码字1,右边赋予码字0,每次向下遍历一次,若节点为非根节点,则依次将码符号放在码字左边,若遍历到根节点,则将该叶子结点所表示的像素值以及对应编成的码字放到码字字典中;

    ②:重复步骤①,直到所有的叶子节点都有其对应的二元霍夫曼码字。

    ③:经过步骤②,此时像素的码字字典已经生成,此时回归到原图片,根据遍历原图片的像素点,依次在码字列表中查找其对应的码字,将所有像素点对应的码字拼接在一起。

    4.此时由于为二元霍夫曼编码,则编码结果为01字符串,此时为了对信息量进行压缩,采用将8个string类似的值转为一个byte,首先填充编码结果使其长度为8的倍数,并增加冗余位数保存原使编码结果最后多余位数的值以及其长度。填充完毕后,只需每次取编码结果的八位转为一个byte存入到txt中即可。

    (2)二元霍夫曼译码:

    详细设计:

    1.每次读取txt中的一个字节,将其还原为字符串,直到txt中的所有字节被读取结束 ,则所得到的字符串则为霍夫曼编码的结果。

    2.

    ①遍历霍夫曼编码的结果,根据霍夫曼编码已经生成的码字列表,对原始像素点进行还原,并根据还原后的像素点生成原始bmp图片。

    ②:对于每一个被遍历到的字符均在码字列表中进行查找,若未找到则加上后续一个字符,继续查找;

    ③:重复步骤③,直到在码字列表中找到该码字对应的像素点,将其码字对应的像素值放入到像素点列表中,重复以上查找还原像素值的步骤直到所有字符串均被遍历完。

    三、模块划分

    (1)二元霍夫曼编码部分:

    ①:类:

    class node:

    def __init__(self, right=None, left=None, parent=None, weight=0, code=None):

    self.left = left

    self.right = right

    self.parent = parent

    self.weight = weight

    self.code = code

    功能:表示叶子节点的类

    ②:函数:

    def picture_convert():

    功能:此函数完成彩色图转为灰度图的功能

    ③:函数:

    def pin_lv_tong_ji(list):

    功能:统计每个像素出现的次数

    ④:函数

    def gou_zao_ye_zi(xiang_su_zhi):

    功能:此函数主要为生成叶子结点,将每个节点赋予权值与像素值

    ⑤:函数

    def sort_by_weight(list_node):

    功能:根据每个叶子结点的权重对叶子结点列表进行排序

    ⑥:函数

    def huo_fu_man_shu(listnode):

    功能:根据叶子结点列表,生成对应的霍夫曼编码树

    ⑦:函数

    def er_yuan_huo_fu_man_bian_ma(picture):

    功能:此函数为进行二元霍夫曼编码的主函数,通过对其他函数的调用完成对像素点的编码

    ⑧:函数

    def zi_jie_xie_ru():

    功能:由于霍夫曼编码结果为string类型,此时应将其转为byte保存,此函数完成将编码结果的字节存入

    (2)二元霍夫曼译码部分:

    ①:函数:

    def zi_jie_du_qu(qqqq):

    功能:根据霍夫曼编码生成的txt文件读取其中的字节恢复为字符串形式的编码结果

    ②函数:

    def er_yuan_huo_fu_man_yi_ma(kuan,gao)

    功能:此为二元霍夫曼译码的主函数,通过调用其他函数来还原原始的bmp图像

    四、测试数据

    测试采取图片像素点个数大小两种bmp图进行:

    图片1信息:

    名称:new.bmp

    大小: 255 KB (261,366 字节)

    像素点个数为: 260288

    灰度图宽为448像素

    灰度图高为581像素

    图片2信息:

    名称:test1.bmp

    大小:12.7 KB (13,078 字节)

    像素点个数: 12000

    灰度图宽:96像素

    灰度图高:125像素

    六、测试情况及结果分析:

    (一)二元霍夫曼编码过程:

    图片1测试结果:

    程序运行后将会生成霍夫曼编码表,并且将最终的编码结果存入到当前程序运行目录下的huo_fu_man_compress.txt中

    由于存入为字节形式,以txt形式查看会显示乱码,属于正常情况。

    原始图像大小为255kb,经过霍夫曼编码最终大小为218kb,大小缩减了接近15%。

    图片2测试结果:

    由程序运行结果可得出二元霍夫曼游程编码结果保存到

    er_yuan_huo_fu_man_youcheng_compress.txt中

    由于存入为字节形式,以txt形式查看会显示乱码,属于正常情况。

    原始图片大小为12.7kb,编码结果文件为9.5kb,大小缩减了接近26%。

    (二)二元霍夫曼译码过程:

    图一测试结果:

    根据编码生成的huo_fu_man_compress.txt还原原始bmp图片并保存为

    er_yuan_huo_fu_man_huan_yuan.bmp

    还原后的图片与原始图片相符合,译码成功

    图片2测试结果:

    根据编码生成的huo_fu_man_compress.txt还原原始bmp图片并保存为

    er_yuan_huo_fu_man_huan_yuan.bmp

    还原后的图片与原始图片相符合,译码成功

    结果分析:

    Bmp灰度图片经过二元霍夫曼编码后,文件大小总能够缩小,即所占空间减小,即达到了压缩的效果,压缩效率会由像素点出现频率的影响。

    等长码编码位数的影响。

    展开全文
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 构造过程:...

    哈夫曼(Haffman)树(最优树)

    定义:

    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    构造过程:

    以 1,7,3,4,9,8为例:

    第一步:排序,1,3,4,7,8,9

    第二步:选出最小的两个数,1,3(哈夫曼树是从下往上排列的),用一个树杈连接上两个最小的数,在顶点处计算出这两个数字的和 并写在上面。

    第三步:然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列。

    第四步:如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了;如果这两个数的和比较大不是下一步的两个最小数的其中一个那么,就并列生长。

    注意:(由于并未规定左右子树,所以哈夫曼树不唯一,同一层上的结点,位置是可以互换的)

     

     

    哈夫曼树的数据结构:

     1 //haffman 树的结构
     2 typedef struct
     3 {
     4     //叶子结点权值
     5     float weight;
     6     //指向双亲,和孩子结点的指针
     7     unsigned int parent;
     8     unsigned int lChild;
     9     unsigned int rChild;
    10 } Node, *HuffmanTree;
    11 
    12 //动态分配数组,存储哈夫曼编码
    13 typedef char *HuffmanCode;

    选择两个权值最小的结点:

     1 //选择两个parent为0,且weight最小的结点s1和s2的方法实现
     2 //n 为叶子结点的总数,s1和 s2两个指针参数指向要选取出来的两个权值最小的结点
     3 void select(HuffmanTree *huffmanTree, int n, int *s1, int *s2)
     4 {
     5     //标记 i
     6     int i = 0;
     7     //记录最小权值
     8     int min;
     9     //遍历全部结点,找出单节点
    10     for(i = 1; i <= n; i++)
    11     {
    12         //如果此结点的父亲没有,那么把结点号赋值给 min,跳出循环
    13         if((*huffmanTree)[i].parent == 0)
    14         {
    15             min = i;
    16             break;
    17         }
    18     }
    19     //继续遍历全部结点,找出权值最小的单节点
    20     for(i = 1; i <= n; i++)
    21     {
    22         //如果此结点的父亲为空,则进入 if
    23         if((*huffmanTree)[i].parent == 0)
    24         {
    25             //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
    26             if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
    27             {
    28                 min = i;
    29             }
    30         }
    31     }
    32     //找到了最小权值的结点,s1指向
    33     *s1 = min;
    34     //遍历全部结点
    35     for(i = 1; i <= n; i++)
    36     {
    37         //找出下一个单节点,且没有被 s1指向,那么i 赋值给 min,跳出循环
    38         if((*huffmanTree)[i].parent == 0 && i != (*s1))
    39         {
    40             min = i;
    41             break;
    42         }
    43     }
    44     //继续遍历全部结点,找到权值最小的那一个
    45     for(i = 1; i <= n; i++)
    46     {
    47         if((*huffmanTree)[i].parent == 0 && i != (*s1))
    48         {
    49             //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
    50             if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
    51             {
    52                 min = i;
    53             }
    54         }
    55     }
    56     //s2指针指向第二个权值最小的叶子结点
    57     *s2 = min;
    58 }

    构造哈夫曼树:

     1 //创建哈夫曼树并求哈夫曼编码的算法如下,w数组存放已知的n个权值
     2 void createHuffmanTree(HuffmanTree *huffmanTree, float w[], int n)
     3 {
     4     //m 为哈夫曼树总共的结点数,n 为叶子结点数
     5     int m = 2 * n - 1;
     6     //s1 和 s2 为两个当前结点里,要选取的最小权值的结点
     7     int s1;
     8     int s2;
     9     //标记
    10     int i;
    11     // 创建哈夫曼树的结点所需的空间,m+1,代表其中包含一个头结点
    12     *huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node));
    13     //1--n号存放叶子结点,初始化叶子结点,结构数组来初始化每个叶子结点,初始的时候看做一个个单个结点的二叉树
    14     for(i = 1; i <= n; i++)
    15     {
    16 
    17         //其中叶子结点的权值是 w【n】数组来保存
    18         (*huffmanTree)[i].weight = w[i];
    19         //初始化叶子结点(单个结点二叉树)的孩子和双亲,单个结点,也就是没有孩子和双亲,==0
    20         (*huffmanTree)[i].lChild = 0;
    21         (*huffmanTree)[i].parent = 0;
    22         (*huffmanTree)[i].rChild = 0;
    23     }// end of for
    24     //非叶子结点的初始化
    25     for(i = n + 1; i <= m; i++)
    26     {
    27         (*huffmanTree)[i].weight = 0;
    28         (*huffmanTree)[i].lChild = 0;
    29         (*huffmanTree)[i].parent = 0;
    30         (*huffmanTree)[i].rChild = 0;
    31     }
    32 
    33     printf("\n HuffmanTree: \n");
    34     //创建非叶子结点,建哈夫曼树
    35     for(i = n + 1; i <= m; i++)
    36     {
    37     
    38       select(huffmanTree,i-1,&s1,&s2);
    39       (*huffmanTree)[s1].parent=i;
    40       (*huffmanTree)[s2].parent=i;
    41       (*huffmanTree)[i].lChild=s1;
    42       (*huffmanTree)[i].rChild=s2;    
    43       (*huffmanTree)[i].weight=(*huffmanTree)[s1].weight+(*huffmanTree)[s2].weight;
    44       printf("%f (%f, %f)\n", (*huffmanTree)[i].weight, (*huffmanTree)[s1].weight, (*huffmanTree)[s2].weight);
    45     }
    46     printf("\n");
    47 }

    求每个节点的哈弗曼编码:

     1 //哈夫曼树建立完毕,从 n 个叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码
     2 void creatHuffmanCode(HuffmanTree *huffmanTree, HuffmanCode *huffmanCode, int n)
     3 {
     4     //指示biaoji
     5     int i;
     6     //编码的起始指针
     7     int start;
     8     //指向当前结点的父节点
     9     int p;
    10     //遍历 n 个叶子结点的指示标记 c
    11     unsigned int c;
    12     //分配n个编码的头指针
    13     huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
    14     //分配求当前编码的工作空间
    15     char *cd = (char *)malloc(n * sizeof(char));
    16     //从右向左逐位存放编码,首先存放编码结束符
    17     cd[n - 1] = '\0';
    18     //求n个叶子结点对应的哈夫曼编码
    19     for(i = 1; i <= n; i++)
    20     {
    21         //初始化编码起始指针
    22         start = n - 1;
    23         //从叶子到根结点求编码
    24         for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
    25         {
    26             if( (*huffmanTree)[p].lChild == c)
    27             {
    28                 //从右到左的顺序编码入数组内
    29                 cd[--start] = '0';  //左分支标0
    30             }
    31             else
    32             {
    33                 cd[--start] = '1';  //右分支标1
    34             }
    35         }// end of for
    36         //为第i个编码分配空间
    37         huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
    38         strcpy(huffmanCode[i], &cd[start]);
    39     }
    40 
    41     free(cd);
    42     //打印编码序列
    43     for(i = 1; i <= n; i++)
    44     {
    45         printf("HuffmanCode of %d is %s\n", i, huffmanCode[i]);
    46     }
    47 
    48     printf("\n");
    49 }

    输入一串数据(数据为1—9之间从小到大连续的数),编译成哈夫曼编码:

     1 HuffmanCode *creatHuffmanCode1(HuffmanTree *huffmanTree,char *Huffman, int n,int data[],float num){
     2     //该函数通过改写creatHuffmanCode函数,来实现译码(即是通过匹配即添加字符串的方式来实现) 
     3     HuffmanCode *huffmanCode;
     4     huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
     5     int i;
     6     int start;
     7     int p;
     8     unsigned int c;
     9     char *cd = (char *)malloc(n * sizeof(char));
    10     cd[n - 1] = '\0';
    11     for(i = 1; i <= n; i++)
    12     {
    13         start = n - 1;
    14         for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
    15         {
    16             if( (*huffmanTree)[p].lChild == c)
    17             {
    18                 cd[--start] = '0';
    19             }
    20             else
    21             {
    22                 cd[--start] = '1';
    23             }
    24         }
    25         huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
    26         strcpy(huffmanCode[i], &cd[start]);
    27     }
    28     free(cd);
    29     //打印编码序列
    30     int num1=int(num);
    31     int l=0;
    32     char s[10]="";
    33     itoa(n,s,10);
    34     huffmanCode[0] = (char *)malloc((10) * sizeof(char));
    35     strcpy(huffmanCode[0],s);
    36     for(int i=1;i<=num1;i++){
    37         int z=data[i];    
    38         strcat(Huffman,huffmanCode[z]);
    39     }
    40     printf("HuffmanCode of this String is %s\n",Huffman);
    41     printf("\n");
    42     return huffmanCode;
    43 }
    44 
    45 
    46 HuffmanCode *dataToHuffmanCode(char *Huffman, int data[]){
    47     //data数组是原数据(0—9),Huffman存放编译后的 Huffman编码 
    48     HuffmanTree huffmanTree;
    49     int k=1;
    50     int q=0;
    51     while(data[k]!=-99){
    52         k++;
    53     }
    54     float num=float(k-1);
    55     float val[10];
    56     for(int j=1;j<10;j++){
    57         int i=1;
    58         int n=0;
    59         while(data[i]!=-99){
    60             if(data[i]==j){
    61                 n++;
    62             }
    63             i++;
    64         }    
    65         val[j]=n/num;
    66     }
    67     for(int i=1;i<10;i++){
    68         if(val[i]!=0){
    69             q++;                //q为叶子结点数 
    70         }
    71     }
    72     float *val2; 
    73     val2 = (float *)malloc((q+1) * sizeof(float));
    74     int m=1;
    75     for(int i=1;i<10;i++){
    76         if(val[i]!=0){
    77             val2[m]=val[i];
    78         }
    79         m++;                   //val2[]储存不同元素的权值 
    80     }
    81     createHuffmanTree(&huffmanTree,val2,q);
    82     HuffmanCode *huffmanCode=creatHuffmanCode1(&huffmanTree,Huffman,q,data,num);//调用上面的 creatHuffmanCode1函数 
    83     return huffmanCode;
    84 }

    将一串哈夫曼编码,还原成原来的数据(此时哈弗曼树已经构造完成):

     1 void HuffmanCodeTodata(char *Huffman, int data[],HuffmanCode *huffmanCode){
     2     //huffmanCode为已经构造好的一颗Huffman树,Huffman存放已经编译好的 Huffman编码 ,data数组存放解码后的原数据(0—9) 
     3     
     4     printf("Huffman:%s\n",Huffman);
     5     printf("1:%s\n",huffmanCode[1]);
     6     printf("2:%s\n",huffmanCode[2]);
     7     printf("3:%s\n",huffmanCode[3]);
     8     printf("4:%s\n",huffmanCode[4]);
     9     //这几行是显示功能,和实现无关 
    10     
    11     int num=atoi(huffmanCode[0]);
    12     char Huffman1[100]="";
    13     int k1=0;
    14     int k2=0;
    15     int x=1;
    16     int y=1;
    17     while(Huffman[k1]=='1'||Huffman[k1]=='0'){    
    18         Huffman1[k2]=Huffman[k1];
    19         for(int i=1;i<=num;i++){
    20             if(strcmp(huffmanCode[i],Huffman1)==0){
    21                 k2=-1;
    22                 data[x]=i;
    23                 x++;
    24                 //strcpy(Huffman1,"");
    25                 memset(Huffman1,0,sizeof(Huffman1));
    26                 break;
    27             }
    28         }
    29         k1++;
    30         k2++;
    31     }
    32     data[x]=-99;
    33     for(int i=1;i<100;i++){
    34         if(data[i]!=-99){
    35             printf("%d",data[i]);
    36         }
    37         else{
    38             break;
    39         }
    40     }
    41 }

    输入一个文本,统计文本中各字符串的数目,计算相应的权重,使用该权重构建哈夫曼编码,使用该编码编译原文件

    (即是在编码的基础上加上文件操作):

     1 void fileHuff(){
     2     FILE *in;
     3     char Huffman2[1000]="";
     4     int data[100];
     5     char file[10];
     6     int k = 1;
     7     printf("输入读取的文件名:(输入aaa.txt)");
     8     scanf("%s",file);
     9     if((in=fopen(file,"r+"))==NULL){
    10         printf("无法打开此文件!\n");
    11         exit(0);
    12     }
    13     while(!feof(in)){
    14         fscanf(in,"%d",&data[k++]);
    15     }    
    16     for(int i=1;i<k;i++){
    17         printf("\n%d\n",data[i]);
    18     }
    19     data[k]=-99;    
    20     dataToHuffmanCode(Huffman2,data);
    21     fprintf(in,"\n");
    22     fprintf(in,"解码后的码为:\n");
    23     fprintf(in,"%s",Huffman2);
    24     fflush(in);
    25     fclose(in);
    26 }

    主函数:

     1 int main()
     2 {
     3     HuffmanTree HT;
     4     HuffmanCode HC;
     5     char Huffman[1000]="";
     6     char Huffman1[1000]="";
     7     HuffmanCode *huffmanCode;
     8     int i, n;
     9     float *w, wei;
    10     int choice;
    11     for (;;)
    12     {
    13         printf("\n           哈夫曼编码 \n");
    14         printf("             1.哈夫曼编码实现\n");
    15         printf("             2.输入一串数据(数据为1—9之间从小到大连续的数),编译成哈夫曼编码\n");
    16         printf("             3.将一串哈夫曼编码,还原成原来的数据\n");
    17         printf("             4.输入一个文本,统计文本中各字符串的数目,计算相应的权重,使用该权重构建哈夫曼编码,使用该编码编译原文件\n");
    18         printf("             5.退出系统\n");
    19         printf("请选择:");
    20         scanf("%d", &choice);
    21         switch (choice)
    22         {
    23         case 1:
    24             printf("\n 需要创建的文件有多少个码元 = " );
    25             scanf("%d", &n);
    26             w = (float *)malloc((n + 1) * sizeof(float));
    27             printf("\ninput the %d element's weight:\n", n);
    28             for(i = 1; i <= n; i++)
    29             {
    30                 printf("%d: ", i);
    31                 fflush(stdin);
    32                 scanf("%f", &wei);
    33                 w[i] = wei;
    34             }
    35             createHuffmanTree(&HT, w, n);
    36             creatHuffmanCode(&HT, &HC, n);
    37             break;
    38         case 2:
    39             printf("\n输入数据为:(以-99结束)");
    40             int data[100];
    41             for(int i=1;i<100;i++){
    42                 scanf("%d",&data[i]);
    43                 if(data[i]==-99){
    44                     break;
    45                 }
    46             }
    47             huffmanCode=dataToHuffmanCode(Huffman,data);
    48             break;
    49         case 3:
    50             int data1[100];
    51             printf("\n哈夫曼编码解码后为:\n");
    52             HuffmanCodeTodata(Huffman,data1,huffmanCode);
    53             break;
    54         case 4:
    55             printf("\n需要实现将aaa.txt文件放在桌面上!\n");
    56             fileHuff();
    57             break;
    58         case 5:
    59             printf("请退出系统!\n");
    60             exit(0);
    61             break;
    62         }
    63     }
    64     return 1;
    65 }

     

    转载于:https://www.cnblogs.com/OrdinaryMan/p/10048547.html

    展开全文
  • 哈夫曼树及哈夫曼编码和解码

    千次阅读 2018-11-02 23:07:35
    哈夫曼树,又称最优树,是带权路径最小的树。 基本概念: 节点间的路径长度:两个节点间所包含的边的数目。 树的路径长度:从根到树中任意节点的路径长度之和。 权:将节点赋予一定的量值,该量值成为权。 树的带权...

    哈夫曼树,又称最优树,是带权路径最小的树。
    基本概念:
    节点间的路径长度:两个节点间所包含的边的数目。
    树的路径长度:从根到树中任意节点的路径长度之和。
    权:将节点赋予一定的量值,该量值成为权。
    树的带权路径长度:树中所有叶子结点的带权路径长度。

    哈夫曼算法:给定一个保存权值的数组,求最优树的算法。对于此权值数组找出其中最小的权值和第二小的权值,用这两个权值创建树,并把这两个权值相加所得作为一个新权值放入到原数组中(注意:此时数组中已经去掉了刚才用过的权值),重复以上操作即可建立最优树。

    哈弗曼编码和解码的优点不再赘述。

    哈夫曼树的实现
    1.建立结构体,比较简单

    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    

    2.利用权值数组创建哈夫曼树(代码注释已相对清晰)

    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    

    3.打印哈夫曼树

    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    

    4.获取哈夫曼树的带权路径长度

    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    

    5.下面便是哈夫曼编码与解码,思路也较为简单

    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    

    6.哈夫曼解码,比较容易实现
    节点与左子节点之间记为 0 ,节点与右节点之间记为 1 ,如图
    在这里插入图片描述

    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    

    完整代码如下

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    
    
    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    
    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    
    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    
    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    
    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    
    int main(int argc, char *argv[]) {
    	int a[4] = {2,6,7,3};
    	Tree *tree = create(a,4);
    	print(tree);
    	printf("\n哈夫曼树的权值为:");
    	printf("%d\n",getWeight(tree,0));
    	getCoding(tree,0);
    	printf("解码时请参照上方编码\n");
    	Decoding(tree); 
    }
    

    运行结果如下
    在这里插入图片描述

    展开全文
  • 二叉树的存储结构Ⅲ 哈夫曼树及编码A. 构造哈夫曼树a. 频度统计b. 生成哈夫曼树B. 哈夫曼编码C. 解码 Ⅰ 树 由于树的应用场合很少,不是很实用,所以在此只做简单介绍。 A. 树的概念 树状图是一种数据结...
  • 哈夫曼树以及编解码

    万次阅读 多人点赞 2016-09-10 14:43:39
    这一篇要总结的是树中的最后一种,即哈夫曼树,我想从以下几点对其进行总结: 1,什么是哈夫曼树? 2,如何构建哈夫曼树? 3,哈夫曼编码? 4,算法实现? 回到顶部 一,什么是哈夫曼树 什么是...
  • 最近完成了数据结构课程设计,被分到的题目是《哈夫曼编码和解码》,现在在这篇博文里分享一下自己的成果。  我在设计时,在网上参考了很多老师和前辈的算法和代码,向他们表示感谢!他们的成果给了我很多启示和...
  • 下图为代码测试的(数组格式) 代码实现: import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = { 4, 6, 8, 5, 9 }; heapSort(arr); Syst...
  • 哈夫曼树即最优二叉树,算法如下: (1)在当前未使用结点中找出两个权重最小的作为左右孩子,计算出新的根结点 (2)新的根结点继续参与过程(1),直至所有结点连接为一棵树 如下图,symbol为具体字符,Frequency...
  • 问题描述:输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上对字符串进行压缩(即编码),同时对压缩后的二进制编码串进行解压(即译码)。为简化设计,输入字符...
  • 最小堆实现哈夫曼树的构造及哈夫曼编码、解码

    千次阅读 多人点赞 2018-12-03 22:49:15
    最大堆(最小堆思想差不多)这里就不再多说,这里主要讲讲哈夫曼树的定义及实现。 Huffman Tree 相关概念: 结点的路径长度:从根结点到该结点的路径上分支的数目。 树的路径长度:树中每个结点的路径长度之和。...
  • 哈夫曼树

    2020-09-14 20:28:33
    文章目录哈夫曼树的基本概念如何构造哈夫曼树哈夫曼树构造算法的实现哈夫曼编码为什么Huffman编码能够保证是前缀码为什么Huffman编码能够保证字符编码总长最短Huffman编码的代码实现Huffman的编码解码 哈夫曼树的...
  • 哈夫曼解码器.zip

    2020-04-24 10:16:50
    数据结构与算法课程设计,将需要传送的字母字符等转换为二进制的字符串,用0,1码的不同排列来表示;将输入的字母,字符等转变为哈夫曼树进而构造哈夫曼编码。还有对哈夫曼编码的破译。
  • k叉哈夫曼树

    2020-10-18 00:14:38
    哈夫曼树定义和构造算法, 2叉哈夫曼树回顾 贪心-哈夫曼编码 k叉哈夫曼树 节点定义 建树,同时也是贪心算法的构造性证明 获取字符集的编码 模拟k叉哈夫曼建树的贪心问题 贪心-模拟哈夫曼建树过程的合并问题 ...
  • 》哈夫曼编码 在二叉树最后的例子里的最后提到了哈夫曼树,个人感觉不是很好理解,为大家找到了一个篇讲的比较简洁明了的http://blog.csdn.net/jinixin/article/details/52142352,就不再造...哈夫曼树的构造过程。
  • 树&二叉树&哈夫曼树Ⅰ 树A. 树的概念B. 树的表达形式(存储结构)C. 树的遍历a. 广度优先遍历(队列)b. 深度优先遍历(堆栈)Ⅱ. 二叉树A. 二叉树的有关概念B. 二叉树中相关公式C. 二叉树的存储结构Ⅲ 哈夫曼树及...
  • 哈夫曼树定义和构造算法 2叉哈夫曼树 节点定义 建树,同时也是贪心算法的构造性证明 获取字符集的编码 用建好的2叉哈夫曼树对同一字符集的数据编码和解码 271. 字符串的编码与解码 $1 哈夫曼树 平衡树插入...
  • 哈夫曼树的构造算法 1.哈夫曼算法 举例 2.哈夫曼树算法实现: 举例 实现 哈夫曼典型应用—哈夫曼编码 思想 举例 产生的两大问题 算法实现 文件的编码和解码 编码 解码 哈夫曼概念: 引入: 由上述...
  • 哈夫曼编码的概念哈夫曼树又称作最优树,是一种带权路径长度最短的树,而通过哈夫曼树构造出的编码方式称作哈夫曼编码。也就是说哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符 “0” 与 “1” ...
  • 创建huffman4. 由huffman获得huffman编码表5. 根据huffman编码表把原数据转换成0101字符串6. 将0101字符串转化为byte数组7. 将该数组写入指定路径存储8. 同时将编码表对象也进行存储解压1. 读取压缩数据2. 读取...
  • 数据结构课程设计 “哈夫曼编码/译码器 设计一个利用哈夫曼算法的编码和译码...3)初始化:键盘上输入字符集大小n,n个字符和n个权值,建立哈夫曼树 4)编码:利用建好的哈夫曼树生成哈夫曼编码 5)输出编码 6)实...
  • 问题描述:输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼树编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解码(即译码)。...
  • 哈夫曼树实现

    2020-03-12 12:00:51
    利用了优先队列,实现了对哈夫曼树的创建,基于已经建好的哈夫曼树,对其进行编码,解码算法步骤: 1、初始化每个叶节点,n个叶节点就初始化为n棵树,构成森林; 2、利用优先队列,每次从森林中pop出两个权重最小...
  • 1. 贪心算法概览 贪心算法是一种算法思想。希望能够满足限制的情况下将期望值最大化...比如:Huffman编码,Dijkstra单源最短路径问题,Kruskal最小生成 等问题都希望满足限制的情况下找到最优的解决问题的方式。 ...
  • 哈夫曼树的概念以及算法简述 1.相关名次的概念: 路径和路径长度:从树中的一个节点到达另外一个节点的之间的分支为路径,其长度为路径长度。树的路径长度定义为从根节点开始到达每一个节点的路径长度之和。 权值:...

空空如也

空空如也

1 2 3 4
收藏数 71
精华内容 28
关键字:

哈夫曼树解码算法