哈夫曼编码(Huffman Coding) cpp完整代码实现详细注释 ASCII码表

雨点打透心脏的1/2处 2022-06-15 12:43 140阅读 0赞

# 1.概念 #

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方法，也称霍夫曼（Huffman）编码。霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。

赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

![SouthEast][]

![SouthEast 1][]

# 2.代码实现 #

代码实现思路：

使用一串字符串创建huffman树，根据每个字符出现的频次生成对应字符的队列结点（queueNode）,根据频次从小到大，生成queue单链表,根据链表中的频次先取出前俩个（即最小的两个），创建新的结点，并同时生成huffman树，递归调用，直到队列（queue）中剩余一个元素,该元素即为huffman树的根结点。

编码过程：根据树中叶子节点（即字符）的位置，遍历树，向左为0，向右为1，对指定字符串进行二进制编码。

解码过程： 根据二进制编码遍历树，0为向左，1为向右，直到找到指定字符，输出。

![SouthEast 2][]

main.cpp

#include <stdio.h>
    #include <stdlib.h>
    #include "huffman.h"
    int main(void)
    {
    	htTree *codeTree = buildTree("I love FishC.com!");      //使用较多的指定字符串创建huffman树
    	hlTable *codeTable = buildTable(codeTree);              //使用创建的huffman树创建Table表
    	encode(codeTable, "I love FishC.com!");                 //使用Table表，对指定字符串进行编码压缩
    	decode(codeTree, "010101110");                          //使用该huffman树，解压指定编码的字符
    
    	return 0;
    }

queue.h

#pragma once
    #ifndef _QUEUE_H
    #define _QUEUE_H
    
    #include "huffman.h"
    
    #define TYPE htNode *
    #define MAX_SZ 256
    
    //（按频率排序的）队列结点
    typedef struct _pQueueNode
    {
    	TYPE val;
    	unsigned int probability;
    	struct _pQueueNode *next;
    }pQueueNode;
    
    //队列
    typedef struct _pQueue
    {
    	unsigned int size;
    	pQueueNode *first;
    }pQueue;
    
    
    //初始化huffman队列
    void initPQueue(pQueue **queue);       //二级指针*****//
    
    //增加结点到队列
    void addPQueue(pQueue **queue, TYPE val, unsigned int priority);
    
    //获取队列中第一个(出现频率值probability最小的)结点
    TYPE getPQueue(pQueue **queue);
    
    #endif

queue.cpp

#include "queue.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    void initPQueue(pQueue **queue)
    {
    	*queue = (pQueue *)malloc(sizeof(pQueue));
    	(*queue)->first = NULL;
    	(*queue)->size = 0;
    	//return;
    }
    
    void addPQueue(pQueue **queue, TYPE val, unsigned int priority)
    {
    	if ((*queue)->size == MAX_SZ)
    	{
    		printf("\nQueue is Full.\n");
    		return;                      //跳出函数
    	}
    
    	pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode)); //临时结点
    	aux->probability = priority;
    	aux->val = val;
    
    	//若是第一个huffmanQueue队列结点  //放在最前面队首
    	if ((*queue)->size == 0 || (*queue)->first == NULL)
    	{
    		aux->next = NULL;
    		(*queue)->first = aux;
    		(*queue)->size = 1;
    		return;
    	}
    
    	else   //比较priority大小，从小到大顺序插入队列
    	{
    		//频率小于第一个结点，插最前面
    		if (priority <= (*queue)->first->probability)
    		{
    			aux->next = (*queue)->first;
    			(*queue)->first = aux;
    			(*queue)->size++;
    			return;
    		}
    
    		//频率大于第一结点时
    		else
    		{
    			pQueueNode * iterator = (*queue)->first;
    
    			//遍历下一结点，未到最后一个结点时
    			while (iterator->next != NULL)
    			{
    				//频率比下一个结点频率小，插到其前面
    				if (priority <= iterator->next->probability)
    				{
    					aux->next = iterator->next;
    					iterator->next = aux;
    					(*queue)->size++;
    					return;
    				}
    				//频率比下一个结点频率大时，遍历下一个
    				iterator = iterator->next;
    			}
    
    			//遍历最后一个结点时(没有比此频率priority小的),放到队列最后
    			if (iterator->next == NULL)
    			{
    				aux->next = NULL;
    				iterator->next = aux;
    				(*queue)->size++;
    				return;
    			}
    		}
    	}
    
    	//free(aux);  //jo
    }
    
    TYPE getPQueue(pQueue **queue)
    {
    	TYPE returnVal;
    	if ((*queue)->size > 0)
    	{
    		returnVal = (*queue)->first->val;
    		(*queue)->first = (*queue)->first->next;
    		(*queue)->size--;
    	}
    	else
    	{
    		printf("\nQueue is empty.\n");
    	}
    	return returnVal;
    }

huffman.h

#pragma once
    #ifndef _HUFFMAN_H
    #define _HUFFMAN_H
    
    //huffman树树节点结构
    typedef struct _htNode
    {
    	char symbol;
    	struct _htNode *left, *right;
    }htNode;
    
    //huffman树 根结点
    typedef struct _htTree
    {
    	htNode *root;
    }htTree;
    
    
    //label结点
    typedef struct _hlNode
    {
    	char symbol;
    	char *code;
    	struct _hlNode *next;
    }hlNode;
    
    //label表
    typedef struct _hlTable
    {
    	hlNode *first;
    	hlNode *last;
    }hlTable;
    
    
    //使用指定字符串inputString，创建huffman树
    htTree *buildTree(char *inputString);
    
    //使用创建的huffmanTree树，创建hlTable表
    hlTable *buildTable(htTree *huffmanTree);
    
    //使用table表，对指定字符串stringToEncode进行编码压缩(逐字符编码成二进制数)
    void encode(hlTable *table, char *stringToEncode);
    
    //使用huffman tree，解压指定的编码stringToDecode
    void decode(htTree *tree, char *stringToDecode);
    
    #endif

huffman.cpp

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "Huffman.h"
    #include "queue.h"
    
    //遍历huffman树结点,形成table链表
    void traversalTree(htNode *treeNode, hlTable **table, int k, char code[256])
    {
    	//若当前树节点左右叶子为空（即自身为叶子节点） 
    	if (treeNode->left == NULL &&treeNode->right == NULL)
    	{
    		//code尾部加\0,定义新结点aux
    		code[k] = '\0';
    		hlNode *aux = (hlNode *)malloc(sizeof(hlNode));
    		aux->code = (char *)malloc( sizeof(char) * (strlen(code) + 1) );
    		strcpy(aux->code, code);
    		aux->symbol = treeNode->symbol;
    		aux->next = NULL;
    
    		//table增加第一个aux结点
    		if ((*table)->first == NULL)
    		{
    			(*table)->first = aux;
    			(*table)->last = aux;
    		}
    		//table尾部增加aux结点 ，形成table链表
    		else
    		{
    			(*table)->last->next = aux;
    			(*table)->last = aux;
    		}
    	}
    
    	//若当前树节点左叶子不为空，code中加0，向下递归遍历
    	if (treeNode->left != NULL)
    	{
    		code[k] = '0';
    		traversalTree(treeNode->left, table, k + 1, code);
    	}
    	//若当前树节点右叶子不为空，code中加1，向下递归遍历
    	if (treeNode->right != NULL)
    	{
    		code[k] = '1';
    		traversalTree(treeNode->right, table, k + 1, code);
    	}
    
    }
    
    hlTable *buildTable(htTree *huffmanTree)
    {
    	hlTable *table = (hlTable *)malloc(sizeof(hlTable));
    	table->first = NULL;
    	table->last = NULL;
    	int k = 0;
    	char code[256];
    	traversalTree(huffmanTree->root, &table, k, code);
    	return table;
    }
    
    htTree * buildTree(char * inputString)
    {
    	字符出现次数统计(所有字符对应的ASCII码对应的整型范围:0-127)
    	int *probability = (int*)malloc(sizeof(int) * 256);     //256个int内存空间
    
    	//初始化
    	for (int i = 0; i < 256; i++)
    	{
    		probability[i] = 0;
    	}
    	//使用ASCII的整型数值作为索引统计
    	for (int j = 0; inputString[j] != '\0'; j++)
    	{
    		probability[(unsigned char)inputString[j]]++;
    	}
    
    	//初始化huffman队列的头指针
    	pQueue *huffmanQueue;
    	initPQueue(&huffmanQueue);
    
    	//遍历所有的ASCIII码(0-256)对应的字符，若出现次数不为0，定义htNode结点 加入到huffman队列中去
    	for (int k = 0; k < 256; k++)
    	{
    		if (probability[k] != 0)
    		{
    			htNode *aux = (htNode *)malloc(sizeof(htNode));
    			aux->left = NULL;
    			aux->right = NULL;
    			aux->symbol = (char)k;         //ASCIII码整型转成字符
    
    			addPQueue(&huffmanQueue, aux, probability[k]);
    		}
    	}
    
    	free(probability);
    
    	//生成huffman树
    	while (huffmanQueue->size != 1)
    	{
    		int priority = huffmanQueue->first->probability;
    		priority += huffmanQueue->first->next->probability;  //前两个结点频率(最小两个值)的和生成新的huffman树结点频率
    
    		htNode * left = getPQueue(&huffmanQueue);
    		htNode * right = getPQueue(&huffmanQueue);
    
    		htNode * newNode = (htNode *)malloc(sizeof(htNode));
    		newNode->left = left;
    		newNode->right = right;
    
    		addPQueue(&huffmanQueue, newNode, priority);
    	}
    
    	//队列中剩余的一个结点即为根结点
    	htTree *hufTree = (htTree *)malloc(sizeof(htTree));
    	hufTree->root = getPQueue(&huffmanQueue);
    	return hufTree;
    }
    
    void encode(hlTable *table, char *stringToEncode)
    {
    	hlNode *traversal;
    
    	printf("stringToEncode is: %s \n\nEncoding...\n\n", stringToEncode);
    
    	for (int i = 0; stringToEncode[i] != '\0'; i++)
    	{
    		traversal = table->first;  //每个字符都需要从Table中第一个位置找起
    		while (traversal->symbol != stringToEncode[i])  //逐字符 全遍历
    		{
    			traversal = traversal->next;
    		}
    		printf("%s ", traversal->code);
    	}
    
    	printf("\n");
    }
    
    void decode(htTree *tree, char * stringToDecode)
    {
    	htNode *traversal = tree->root;
    	printf("\n\nDecoding.... \n\nstringToDecode is: %s \n\nDecoding String:\n\n", stringToDecode);
    
    	//逐字符（0左/1右）遍历huffman树
    	for (int i = 0; stringToDecode[i] != '\0'; i++)
    	{
    		//遍历到最后一个叶子节点 即为解码后的字符
    		if (traversal->left == NULL && traversal->right == NULL)
    		{
    			printf("%c", traversal->symbol);
    			traversal = tree->root;
    		}
    		if (stringToDecode[i] == '0')
    		{
    			traversal = traversal->left;
    		}
    		if (stringToDecode[i] == '1')
    		{
    			traversal = traversal->right;
    		}
    		if (stringToDecode[i] != '0' &&stringToDecode[i] != '1')
    		{
    			printf("Input String cannot be decoded correctly\n");
    			return;
    		}
    	}
    	//if (traversal->left == NULL && traversal->right == NULL)
    	//{
    
    	//}
    
    }

# 3.结果 #

![SouthEast 3][]

[SouthEast]: /images/20220615/45f5466737be438699b5a01b46d58ec2.png
[SouthEast 1]: /images/20220615/3851d4eeffad456b927d48f5b45328d7.png
[SouthEast 2]: /images/20220615/9eba44e9143e4f42b1400ddb6a3b3ca0.png
[SouthEast 3]: /images/20220615/3555660b31fd4be6b3b0f3ce068184c9.png