哈夫曼编码的实现

哈夫曼编码

一.关于哈弗曼编码的个人理解

       在数据传输过程中，数据都是由很多字符构成，每个字符又都是由二进制数构成，如果给每个字符确定且定长的编码，那么在数据传输过程中，数据量就会很大，如何使数据量变小呢？
       可以通过观察得到，在我们人类的所使用的语言中，总是有那么几个字符的应用频率大于其他字符的使用频率，所以我们可以通过将这些使用频率很高的字符通过缩短其二进制编码的长度，来进行数据量的压缩。
       哈夫曼树就是一种很好的解决方式，哈夫曼树可以根据我们规定的权值，对字符进行排列组合，生成一颗哈夫曼树，而在这个树中，每个字符所生成的编码都是独一无二的，不会产生二义性，当对压缩后的数据进行解密时，不会因为字符编码出现二义性，不仅减小了数据量，并且保证压缩之后的数据的准确性。

二.问题的提出

  1. 如何统计给定的一篇文本中，每个字符出现的频率。
  2. 使用什么样的结构可以完成哈夫曼树权值最小子树的挑选。
  3. 如何对输入的数据进行压缩处理。

以上问题将会在下文进行解释。

三.哈夫曼编码的实现原理

  1. 哈夫曼编码的实现需要通过构造哈夫曼树，通过遍历哈夫曼的子树来确定每个字符的编码。
  2. 在构建哈夫曼树时，需要取出权值最小的两颗子树，可以利用队列从队头取元素的特性，将树节点按照权值由小到大的存储在队列中，在构造哈夫曼树时，从队头取出两个权值最小的子树进行哈夫曼树的构造，并将构造好的子树继续根据权值大小放入队列中，用于下一次构造，直至队列为空。
  3. 为节点生成哈夫曼编码，生成时，利用前序遍历的方式，将每个节点走过的路径记录下来，并且将路径生成的字符串进行存储。
  4. 压缩后的编码如何解密，我们可以知道，哈夫曼编码是没有二义性的，就可以利用生成的编码顺序对比压缩的编码，一位一位进行解密。

四.哈夫曼树的存储结构

为了利用队列的特性，使用队列节点嵌套二叉树节点的方式，进行存储。

// 哈夫曼树节点
struct BiTreeNode
{
	ElemType data;
	int weight;
	BiTreeNode* lchild;
	BiTreeNode* rchild;
};

// 队列节点
struct SqQueueNode
{
	BiTreeNode* btNode;
	SqQueueNode* next;
};
struct SqQueueLink
{
	SqQueueNode* front;
	SqQueueNode* rear;
};

// 密钥表结构
struct EncTable
{
	char ch;
	char table[256];
};

五.哈夫曼树如何构造

1.统计文本中字符出现的频率

	string str = "this is a test string";		// 示例字符串
	int priority[ACSII_LEN] = { 0 };		// 确定优先级，记录ACSII表所有字符出现的次数 

	// 记录str中每个字符出现的次数（将字符转为acsII进行记录）
	for (int i = 0; i < str.length(); i++)
	{
		priority[(unsigned char)(str[i])]++;
	}

	// 对字符进行入队
	for (int i = 0; i < ACSII_LEN; i++)
	{
		if (priority[i] != 0)
		{
			AddSqQueue(sq, i, priority[i]);
		}
	}

2.对入队列的节点进行排序处理

// 入队操作 根据weight进行入队 从小到大进行排序
void AddSqQueue(SqQueueLink*& sq, ElemType e, int weight)
{
	SqQueueNode* sqNew = new SqQueueNode;
	sqNew->btNode = new BiTreeNode;
	sqNew->btNode->lchild = NULL;
	sqNew->btNode->rchild = NULL;

	sqNew->btNode->data = e;
	sqNew->btNode->weight = weight;
	sqNew->next = NULL;

	SqQueueNode* sqCur = new SqQueueNode;
	sqCur->btNode = new BiTreeNode;
	sqCur = sq->front->next;

	// 队列为空时 直接入栈
	if (sq->front == sq->rear)
	{
		sq->rear->next = sqNew;
		sq->rear = sqNew;
	}	
	// 如果权最小 则在队头直接加入
	else if (sqNew->btNode->weight <= sqCur->btNode->weight)
	{
		sqNew->next = sqCur;
		sq->front->next = sqNew;
	}
	else
	{
		// 按照权小-大寻找位置进行插入
		while(sqCur != NULL && sqCur->next != NULL)
		{
			if (sqNew->btNode->weight <= sqCur->next->btNode->weight)
			{
				break;
			}

			sqCur = sqCur->next;
		}

		if (sqCur->next == NULL)
		{
			sqCur->next = sqNew;
			sqNew->next = NULL;
			sq->rear = sqNew;
		}
		else
		{
			sqNew->next = sqCur->next;
			sqCur->next = sqNew;
		}
	}
}

3.哈夫曼树的两种构造方法

  1. 将生成的子树继续入队，通过取队头两元素进行哈夫曼树构造
void CreateHuffmanTreeBySq(BiTreeNode*& hufmTree, SqQueueLink*& sq)
{
   hufmTree = new BiTreeNode;

   BiTreeNode* bRes = new BiTreeNode;
   bRes->lchild = NULL;
   bRes->rchild = NULL;

   while (sq->front != sq->rear)
   {
   	// 判断队列中元素是否只剩一个
   	if (sq->front->next != sq->rear)
   	{
   		// 取出队头两个元素
   		GetHeadQueue(sq, bRes->lchild);
   		GetHeadQueue(sq, bRes->rchild);
   		// 将取出的队头两个最小元素 构造树
   		CreateBiTree(hufmTree, bRes->lchild, bRes->rchild);

   		// 创建临时变量 构造哈夫曼树
   		SqQueueNode* sqTmp = new SqQueueNode;
   		sqTmp->btNode = hufmTree;

   		AddSqQueue(sq, sqTmp->btNode, sqTmp->btNode->data, sqTmp->btNode->weight);
   	}
   	else
   	{
   		GetHeadQueue(sq, bRes->lchild);

   		hufmTree = bRes->lchild;
   	}
   }
}
  1. 从队列中取出节点进行构建
// 队列节点嵌套树节点 利用嵌套的树节点进行构建  节点值小的放左边 大的放右边
void CreateHuffmanTree(BiTreeNode*& hufmTree, SqQueueLink*& sq)
{
	hufmTree = new BiTreeNode;

	BiTreeNode* bRes = new BiTreeNode;

	// 取出队头两个元素
	GetHeadQueue(sq, bRes->lchild);
	GetHeadQueue(sq, bRes->rchild);
	// 将取出的队头两个最小元素 构造树
	CreateBiTree(hufmTree, bRes->lchild, bRes->rchild);

	while (sq->front != sq->rear)
	{
		SqQueueNode* sqTmp = sq->front->next;

		// 判断当前队列中是否剩余一个元素
		if (sqTmp != sq->rear)
		{
			// 如果哈夫曼树当前的根节点与队列中最小的节点的权值小于从队头取出的两元素权值，则将lchild加入hufmTree
			if ((hufmTree->weight + sqTmp->btNode->weight) < (sqTmp->btNode->weight + sqTmp->next->btNode->weight))
			{
				GetHeadQueue(sq, bRes->lchild);

				if (hufmTree->weight < bRes->lchild->weight)
				{
					CreateBiTree(hufmTree, hufmTree, bRes->lchild);
				}
				else
				{
					CreateBiTree(hufmTree, bRes->lchild, hufmTree);
				}
			}
			else	// 如果不满足条件 则利用两节点构建新二叉树 并将新二叉树添加值hufmTree
			{
				BiTreeNode* btNew = new BiTreeNode;

				// 构建树
				GetHeadQueue(sq, bRes->lchild);
				GetHeadQueue(sq, bRes->rchild);
				CreateBiTree(btNew, bRes->lchild, bRes->rchild);

				// 判断该将子树添加值左子树或右子树
				if (btNew->weight < hufmTree->weight)
				{
					CreateBiTree(hufmTree, btNew, hufmTree);
				}
				else
				{
					CreateBiTree(hufmTree, hufmTree, btNew);
				}
			}
		}
		else	// 剩余一个元素时 直接将队列中的节点加入哈夫曼树中
		{
			GetHeadQueue(sq, bRes->lchild);

			if (hufmTree->weight < bRes->lchild->weight)
			{
				CreateBiTree(hufmTree, hufmTree, bRes->lchild);
			}
			else
			{
				CreateBiTree(hufmTree, bRes->lchild, hufmTree);
			}
		}
	}
}

六.哈夫曼编码的生成(压缩编码长度)

1.利用哈夫曼树生成对应的密钥字典

// 利用前序遍历二叉树进行遍历  如果遇到叶子节点 或者 该节点已定义 则将该节点添加至 存储结构中
// int i: 用于记录生成密文后的下标
int CreateHuffmanCode(BiTreeNode* hufmTree, int i, EncTable(&encTable)[ACSII_LEN])
{
	static char* code = new char[128];
	static int deep = 0;

	if (hufmTree != NULL)
	{
		// 如果当前节点有数据 或者为叶子节点 则将编码 和 节点数据 存至 密钥表中
		if ((hufmTree->data != '#' && hufmTree != NULL) || (hufmTree->lchild == NULL && hufmTree->rchild == NULL))
		{
			encTable[deep].ch = hufmTree->data;
			strcpy(encTable[deep].table, code);
			encTable[deep].table[i] = '\0';
			deep += 1;
		}

		code[i] = '0';
		CreateHuffmanCode(hufmTree->lchild, i + 1, encTable);
		code[i] = '1';
		CreateHuffmanCode(hufmTree->rchild, i + 1, encTable);
	}

	return deep;
}

2.根据密钥字典进行字符串的压缩

// 将输入字符串 匹配字符串 将密钥替换进去
void Encrypt(string str, EncTable enctable[], int deep/*密钥表大小*/, string& cryptograph)
{
	char* cryptographTmp = new char[256];
	char* pC = cryptographTmp;

	for (int i = 0; i < str.length(); i++)
	{
		for (int j = 0; j < deep; j++)
		{
			if (str[i] == enctable[j].ch)
			{
				strcpy(cryptographTmp, enctable[j].table);
				cryptographTmp += strlen(enctable[j].table);
			}
		}
	}
	cryptographTmp[strlen(cryptographTmp)] = '\0';

	cryptographTmp = pC;
	cryptograph = cryptographTmp;
}

3.利用密钥字典中的编码对字符串进行解密

// 解密函数 根据密钥表 对 密文进行匹配 匹配到一位 存储一位 直到全部解密完成
void Decode(string cryptograph, EncTable enctable[], int deep, string& str)
{
	char* decodeStr = new char[256];
	int deocelen = 0;

	char* crytmp = new char[cryptograph.length() + 1];
	strcpy(crytmp, cryptograph.c_str());

	int crytmplen = strlen(crytmp);
	for (int i = 0; i < crytmplen; i++)
	{
		for (int z = 0; z < deep; z++)
		{
			int flag = 0;
			for (int j = 0; j < strlen(enctable[z].table); j++)
			{
				if (enctable[z].table[j] == crytmp[j])
				{
					flag++;
				}
			}

			if (flag == strlen(enctable[z].table))
			{
				decodeStr[deocelen++] = enctable[z].ch;
				crytmp += strlen(enctable[z].table);

				crytmplen = strlen(crytmp);
				i = 0;
			}
		}
	}
	decodeStr[deocelen] = '\0';

	str = decodeStr;
}

七.测试结果

测试结果

int main()
{
	SqQueueLink* sq = new SqQueueLink;

	InitQueue(sq);

	ElemType e;
	int weight;

	string str = "This is a test string!!";
	int priority[ACSII_LEN] = { 0 };		// 确定优先级，记录ACSII所有字符出现的次数 

	// 记录str中每个字符出现的次数（将字符转为acsII进行记录）
	for (int i = 0; i < str.length(); i++)
	{
		priority[(unsigned char)(str[i])]++;
	}

	for (int i = 0; i < ACSII_LEN; i++)
	{
		BiTreeNode* bi = new BiTreeNode;
		bi->lchild = NULL;
		bi->rchild = NULL;
		if (priority[i] != 0)
		{
			AddSqQueue(sq, bi, i, priority[i]);
		}
	}

	BiTreeNode* hufmTree = NULL;
	CreateHuffmanTreeBySq(hufmTree, sq);

	// 密钥表
	EncTable encTable[ACSII_LEN] = { 0 };

	// 加密算法有问题
	int len = 0;
	int deep = CreateHuffmanCode(hufmTree, len, encTable);

	cout << "密钥表:" << endl;
	for (int i = 0; i < deep; i++)
	{
		cout << encTable[i].ch << " " << encTable[i].table << endl;
	}

	// 对字符串进行加密
	string cryptograph;
	Encrypt(str, encTable, deep, cryptograph);

	cout << "\n密文:\n" << cryptograph << endl;

	string decodeStr;
	Decode(cryptograph, encTable, deep, decodeStr);
	cout << "\n\n解密:\n" << decodeStr << endl;

	return 0;
}