• Day14/15/16：哈夫曼树、哈弗曼编码(压缩与解压缩)

    目录

       一、相关基础知识

       二、压缩     

            三、解压缩 

    关键:如何将放在一起的0101进行区分成相应的字符

    四、利用栈和堆---Huffman树的写法:

    一、相关基础知识

            1.unsigned char与signed char 的区别:

             2.哈夫曼树(最优树、最佳搜索树)：

    ①路径长度的概念


    1.路径：从一个结点到另一个结点之间的分支序列
    2.结点之间的路径长度：从一个结点到另一个结点之间的分支数目
    3.树的路径长度（用PL表示）：从树的根到每一个结点的路径长度之和  → 深度之和

     PL = 0＋1＋1＋2＋2＋2＋2＋3＝13

     

     WPL=7*2+5*2+2*2+4*2=36

    ②构建一颗Huffman树

    以数据{5,6,7,8,15}为例

    注意观察特征：原数据5\6\7\8\15均只会出现在叶子结点(自下而上构建新的节点) 

    3.压缩与解压缩：

    ①文件  ：

                        有损压缩   无损压缩(Huffman为无损压缩)
                        png  有损压缩
                        9个像素合为一个像素

    基于哈夫曼树的文件压缩和解压（QT可视化界面）
    rar 4星 超过75%的资源 17.26MB
    下载

    ②例子：

    "abbbbcccccccccddddddddddddddfffffffffffffffffffffff"
    'a'        1     'b'        4    'c'        9      'd'        14     'f'        23
    原来：54字节

    ---->Huffman编码后：24*1 +  14*2 + 9*3 + 4*4 + 1*4= 13字节不到 

    ③压缩过程： 


        1. 分析待压缩文件
            (获取文件中出现过的字节   和  每个出现过的字节的出现次数   组合成字典(索引))
        2. 根据字典组建哈夫曼树，获取每个字节对应的哈夫曼编码
        3. 创建压缩后文件，把字典写入压缩后文件中
           然后 一个一个字节去读待压缩文件的内容  把它转换成对应的编码
           把编码写入压缩后文件中

    ④解压过程:


        1. 从压缩后文件中读取字典
        2. 根据字典生成哈夫曼树
        3. 循环从压缩后文件中读取字节
            3.1 一个个比特位获取  并  根据比特位的值去哈夫曼树中找 
            3.2 找到一个叶子节点就解压出一个字节 
            3.3 都没有孩子了还往右 说明结束了  或者  读取完毕  结束

    二、压缩

    1.函数声明以及main函数.

    1. #include 
    2. #include 
    3. #include 
    4. #define TESTHUFFMANCODE 0
    5. #define TESTWRITECHAR   0
    6.  
    7. //哈夫曼编码长度      注意 文件中字符种类越多  对应哈夫曼编码长度越长  
    8. #define HFM_CODE_LEN   10
    9.  
    10. struct ZiFu
    11. {
    12. 	unsigned char			zf;					//字符
    13. 	unsigned int			count;				//字符出现次数
    14. 	char					code[HFM_CODE_LEN];	//对应哈夫曼编码
    15. 	int						idx;				//字符数组下标
    16. };
    17.  
    18. //字典
    19. struct allZifu
    20. {
    21. 	int			zf_count;			//出现过的字符的个数
    22. 	ZiFu		zf_arr[256];		//存储每个字符的信息
    23. };
    24.  
    25. //哈夫曼树节点类型
    26. struct treeNode
    27. {
    28. 	ZiFu		data;
    29. 	treeNode*	pLeft;
    30. 	treeNode*	pRight;
    31. 	treeNode*	pParent;
    32. };
    33. //创建 哈夫曼树节点
    34. treeNode* createNode(ZiFu*	pZf);
    35.  
    36.  
    37. //分析文件  得到字典(出现过的字符的个数 字符 字符出现次数)
    38. void analysisFile(char* srcFile, allZifu* zd);
    39.  
    40. //创建哈夫曼树并返回
    41. treeNode* createHaffmanTree(allZifu* zd);
    42. //根据哈夫曼树 创建哈夫曼编码 并写入字典中
    43. void createHaffmanCode(treeNode* root, allZifu* zd);
    44. //判断当前节点是否叶子节点，是返回true 否则返回false
    45. bool isLeaf(treeNode* root);
    46. //设置哈夫曼编码到字典中
    47. void setHaffmanCode(treeNode* root, char* pCodeStr);
    48. //创建压缩文件并把字典和对应字符的编码写入到压缩后文件中
    49. void writeCompressFile(char* src, char* dst, allZifu* zd);
    50. //从字典中获取某个字符对应的haffman编码
    51. void getHaffmanCode(char c, char* haffmanCode, allZifu* zd);
    52. int main()
    53. {
    54. 	char srcFile[256] = "1.txt";//待压缩文件
    55. 	char dstFile[256] = "2.txt";//压缩后文件
    56.  
    57. 	allZifu zd = { 0 };//字典
    58.  
    59. 	analysisFile(srcFile, &zd);
    60. 	treeNode* root = NULL;
    61. 	root = createHaffmanTree(&zd);
    62.  
    63. 	createHaffmanCode(root, &zd);
    64.  
    65. 	writeCompressFile(srcFile, dstFile, &zd);
    66.  
    67. 	printf("压缩完毕!\n");
    68. 	system("pause");
    69. 	//while (1);
    70. 	return 0;
    71. }

    2.分析文件 analysisFile

    正常统计是否出现过or出现过几次

    1. //分析文件  得到字典(出现过的字符的个数 字符 字符出现次数)
    2. void analysisFile(char* srcFile, allZifu* zd)
    3. {
    4. 	//1 打开文件
    5. 	FILE* fp = fopen(srcFile, "rb");
    6. 	if (NULL == fp)
    7. 	{
    8. 		printf("analysisFile函数中 打开待压缩文件:%s 失败!\n",srcFile);
    9. 		return;
    10. 	}
    11. 	//2 读取文件内容
    12. 	unsigned char c;//存储读到的字节
    13. 	int r;//fread 返回值:读取到的字节数
    14. 	bool is;//标记是否出现过
    15. 	int i;
    16. 	while (1)
    17. 	{//循环读取
    18. 		//读到一个字节  读不到 循环结束
    19. 		r = fread(&c, 1, 1, fp);
    20. 		if (1 != r) break;
    21. 		//判断是否出现过 
    22. 		is = false;//默认没有出现过
    23. 		for (i = 0; i < zd->zf_count; i++)
    24. 		{
    25. 			if (c == zd->zf_arr[i].zf)
    26. 			{
    27. 				is = true;
    28. 				break;
    29. 			}
    30. 		}
    31. 		if (!is)
    32. 		{//如果没有出现过
    33. 			zd->zf_count++;//字符个数增加
    34. 			zd->zf_arr[i].zf = c;//记录字符
    35. 		}
    36. 		zd->zf_arr[i].count++;
    37. 	}
    38. 	//3 关闭
    39. 	fclose(fp);
    40. }

    3.创建结点Node与哈夫曼树 tree

    1. //创建 哈夫曼树节点
    2. treeNode* createNode(ZiFu*	pZf)
    3. {
    4. 	treeNode* pNew = (treeNode*)malloc(sizeof(treeNode));
    5. 	if (NULL == pNew) return NULL;
    6.  
    7. 	memset(pNew, 0, sizeof(treeNode));
    8. 	memcpy(pNew->data.code, pZf->code, HFM_CODE_LEN);
    9. 	pNew->data.count = pZf->count;
    10. 	pNew->data.zf = pZf->zf;
    11. 	pNew->data.idx = pZf->idx;
    12.  
    13. 	return pNew;
    14. }

     创建Huffman树的步骤:

            ①准备一个指针数组,存储所有节点(依次将字典中的字符创建成结点放入arr)
            ②寻找count-1次minIDX和secIdx,制作父节点数据,双向连接即可。

    1. //创建哈夫曼树并返回
    2. treeNode* createHaffmanTree(allZifu* zd)
    3. {
    4. 	//1 准备一个指针数组 存储所有节点
    5. 	treeNode** pArray = (treeNode**)malloc(sizeof(treeNode*)* (zd->zf_count));
    6. 	for (int i = 0; i < zd->zf_count; i++)
    7. 	{
    8. 		pArray[i] = createNode(&(zd->zf_arr[i]));//将字典里存放的一个个字符转化成一个个treeNode
    9. 		pArray[i]->data.idx = i;//下标
    10. 	}
    11. 	
    12. 	//vector buff;
    13. 	int minIdx, secMinIdx;
    14. 	int j;
    15. 	treeNode* pTemp = NULL;
    16. 	//循环找最小的和第二小的  循环    zd->zf_count - 1 次(每次删两个,加一个-----共需要n-1次组建,最后一次剩下中间结点data=0)
    17. 	for (int i = 0; i < zd->zf_count - 1; i++)
    18. 	{
    19. 		//找出最小的
    20. 		j = 0;
    21. 		while (pArray[j] == NULL) j++;//让j是第一个的下标(删除是直接置空or新赋值结点)
    22. 		minIdx = j;
    23. 		for (j = 0; j < zd->zf_count; j++)
    24. 		{//利用短路效应(pArray[j]可能为nullptr)
    25. 			if (pArray[j] &&pArray[j]->data.count < pArray[minIdx]->data.count)
    26. 				minIdx = j;
    27. 		}
    28. 		//找出第二小的
    29. 		j = 0;
    30. 		while (pArray[j] == NULL || j==minIdx) j++;//避开最小下标(下同)
    31. 		secMinIdx = j;
    32. 		for (j = 0; j < zd->zf_count; j++)
    33. 		{
    34. 			if (pArray[j] && j!=minIdx &&pArray[j]->data.count < pArray[secMinIdx]->data.count)
    35. 				secMinIdx = j;
    36. 		}
    37. 		//组件成树
    38. 		//1.1制作父节点的数据
    39. 		ZiFu tempZf = { 0, pArray[minIdx]->data.count + pArray[secMinIdx]->data.count };
    40. 		tempZf.idx = -1;//保险  
    41. 		pTemp = createNode(&tempZf);
    42. 		//双向设置
    43. 		pTemp->pLeft = pArray[minIdx];
    44. 		pTemp->pRight = pArray[secMinIdx];
    45.  
    46. 		pArray[minIdx]->pParent = pTemp;
    47. 		pArray[secMinIdx]->pParent = pTemp;
    48. 		
    49. 		//1.2数组中添加(最小的和第二小的 的 父)  删掉(最小的和第二小的)
    50. 		pArray[minIdx] = pTemp;
    51. 		pArray[secMinIdx] = NULL;
    52. 	}
    53. 	return pTemp;
    54. }

    4.设置哈夫曼编码到字典中＆将整个树完成对应的设置＆从字典中获取字符c对应的Huffman编码

    ①设置Huffman编码到字典中,传入的root是叶子结点,所以在此向上追溯,左1右2(不用0是因为初始化默认为0,以示区分)---->最终记得将结果进行翻转 

    1. //设置哈夫曼编码到字典中
    2. void setHaffmanCode(treeNode* root, char* pCodeStr)
    3. {//args:pCodeStr是传入对应字符的code成员的。(直接赋值)
    4. 	treeNode* pTemp = root;
    5. 	char buff[HFM_CODE_LEN] = { 0 };
    6. 	int buffIdx = 0;
    7.  
    8. 	while (pTemp->pParent)
    9. 	{//一路往上
    10. 		if (pTemp == pTemp->pParent->pLeft)
    11. 		{
    12. 			buff[buffIdx] = 1;
    13. 		}
    14. 		else{
    15. 			buff[buffIdx] = 2;
    16. 		}
    17. 		buffIdx++;
    18. 		pTemp = pTemp->pParent;
    19. 	}
    20.  
    21. 	//逆转存储到参数数组中
    22. 	char temp;
    23. 	for (int i = 0; i < buffIdx / 2; i++)
    24. 	{
    25. 		temp = buff[i];
    26. 		buff[i] = buff[buffIdx - i - 1];
    27. 		buff[buffIdx - i - 1] = temp;
    28. 	}
    29. 	//赋值
    30. 	strcpy(pCodeStr, buff);
    31. }

    ②将整个Huffman的原始元素进行相应的赋值，原始元素是会是在叶子节点上！！                           --->递归搜索判断是否符合,

    1. //根据哈夫曼树 创建哈夫曼编码 并写入字典中
    2. void createHaffmanCode(treeNode* root, allZifu* zd)
    3. {
    4. 	int idx;
    5. 	if (root)
    6. 	{	//终止条件
    7. 		if (isLeaf(root))									//只有在叶子结点需要创建好哈弗曼编码(元素均在叶子结点)
    8. 		{
    9. 			idx = root->data.idx;
    10. 			setHaffmanCode(root, zd->zf_arr[idx].code);
    11. 		}
    12. 		else//递归调用
    13. 		{
    14. 			createHaffmanCode(root->pLeft, zd);
    15. 			createHaffmanCode(root->pRight, zd);
    16. 		}
    17. 	}
    18. }
    1. //从字典中获取某个字符对应的haffman编码
    2. void getHaffmanCode(char c, char* haffmanCode, allZifu* zd)
    3. {
    4. 	for (int i = 0; i < zd->zf_count; i++)
    5. 	{
    6. 		if (c == zd->zf_arr[i].zf)
    7. 		{
    8. 			strcpy(haffmanCode, zd->zf_arr[i].code);
    9. 			break;
    10. 		}
    11. 	}
    12. }

    5.判断叶子结点＆创建压缩文件并写入对应的编码

    1. //判断当前节点是否叶子节点，是返回true 否则返回false
    2. bool isLeaf(treeNode* root)
    3. {
    4. 	if (root && NULL == root->pLeft && NULL == root->pRight) return true;
    5. 	return false;
    6. }

     写编码到文件中的关键:

            ①charForwrite有8个bit位，依次由对应的每个字符对应而来。当Huffman编码读到0的时候,表明当前的char已经读完，需要再读入一个字符和对应编码。当读到的是2,对应0。当读到是1,对应的是1.

            ②每满8个bit位就写入这个charForWrite

            ③1---->0000 0001  然后对它进行左移操作，结合& ~ |等位运算,可以很容易的将charForWrite的二进制的bit进行需要的修改。0x80也行---->1000 0000

    1. //创建压缩文件并把字典和对应字符的编码写入到压缩后文件中
    2. void writeCompressFile(char* src, char* dst, allZifu* zd)
    3. {
    4. 	//1. 创建压缩后文件    打开 待压缩文件
    5. 	FILE* fpSrc = fopen(src, "rb");
    6. 	FILE* fpDst = fopen(dst, "wb");
    7. 	if (NULL == fpSrc || NULL == fpDst)
    8. 	{
    9. 		printf("writeCompressFile函数中 打开文件失败!\n");
    10. 		return;
    11. 	}
    12. 	//2. 优先把字典写入压缩后文件中
    13. 	fwrite(zd, 1, sizeof(allZifu), fpDst);
    14. 	//3. 一个个字节读待压缩文件 对照字典中的哈夫曼编码 得到对应二进制  每拼成一个字节(8bit) 写入到压缩后文件中 读完 写完 循环结束
    15. 	char c;//存储读到的字节
    16. 	int r;//读到的字节数
    17.  
    18. 	char charForWrite;//用来存储写入  压缩后文件中的  字节  （二进制位拼接而来）
    19. 	int  idxForWrite;//charForWrite 的  二进制位 索引
    20.  
    21. 	char haffmanCode[HFM_CODE_LEN] = { 0 };//临时存储哈夫曼编码
    22. 	int  haffmanCodeIdx=0;//haffmanCode 数组下标
    23.  
    24. 	bool isEnd = false;
    25.  
    26. 	while (1)
    27. 	{
    28. 		if (0 == haffmanCode[haffmanCodeIdx])
    29. 		{
    30. 			r = fread(&c, 1, 1, fpSrc);
    31. 			if (1 != r) break;//读不不到了
    32.  
    33. 			getHaffmanCode(c, haffmanCode, zd);//获得字符c对应的哈弗曼编码
    34. 			haffmanCodeIdx = 0;
    35. 		}
    36. #if  TESTHUFFMANCODE
    37. 		printf("%c=================", c);
    38. 		for (int i = 0; i < HFM_CODE_LEN; i++)
    39. 		{
    40. 			printf("%d", haffmanCode[i]);
    41. 		}
    42. 		printf("\n");
    43. #endif
    44.  
    45.  
    46. 		//把haffman编码转成二进制并存入charForWrite里  注意八个bit位 写入fpDst一次
    47. 		idxForWrite = 0;
    48. 		charForWrite = 0;
    49. 		while (idxForWrite < 8)//8个bit位写一次
    50. 		{
    51. 			if (2 == haffmanCode[haffmanCodeIdx])
    52. 			{//设置对应的bit位为0
    53. 				charForWrite &= ~(1 << (7 - idxForWrite));//把对应位置零 其他 维持不变
    54.  
    55. 				haffmanCodeIdx++;
    56. 				idxForWrite++;
    57. 			}
    58. 			else if (1 == haffmanCode[haffmanCodeIdx])
    59. 			{//设置对应的bit位为1
    60. 				charForWrite |= 1 << (7 - idxForWrite);//把对应位置1 其他 维持不变
    61. 				haffmanCodeIdx++;
    62. 				idxForWrite++;
    63. 			}
    64. 			else
    65. 			{//当前这个字符对应的haffman编码操作完毕 读取下一个字符的haffman编码 或者 结束
    66. 				r = fread(&c, 1, 1, fpSrc);
    67. 				if (1 != r)
    68. 				{//读完了
    69. 					isEnd = true;
    70. 					break;//结束 while (idxForWrite < 8) 循环
    71. 				}
    72.  
    73. 				getHaffmanCode(c, haffmanCode, zd);
    74. 				haffmanCodeIdx = 0;
    75. #if  TESTHUFFMANCODE
    76. 				printf("%c=================", c);
    77. 				for (int i = 0; i < HFM_CODE_LEN; i++)
    78. 				{
    79. 					printf("%d", haffmanCode[i]);
    80. 				}
    81. 				printf("\n");
    82. #endif
    83. 			}
    84. 		}
    85. 		fwrite(&charForWrite, 1, 1, fpDst);//写入压缩后文件中
    86. #if 	TESTWRITECHAR
    87. 		for (int i = 0; i < 8; i++)
    88. 		{
    89. 			if ((charForWrite & 0x80) == 0x80)
    90. 			{//这边&的优先级是低于==,所以要加上一个括号
    91. 				printf("1");
    92. 			}
    93. 			else
    94.             {
    95. 				printf("0");
    96. 			}
    97.  
    98. 			charForWrite <<= 1;
    99. 		}
    100. 		printf("\n");
    101. #endif
    102. 		if (isEnd) break;
    103. 	}
    104.  
    105. 	//4. 关闭保存
    106. 	fclose(fpSrc);
    107. 	fclose(fpDst);
    108. }

    三、解压缩 

            关键:如何将放在一起的0101进行区分成相应的字符

                    将压缩后的文件,读出字典---->根据字典生成相应的Huffman树---->读一个字节,依次看每一个比特位,1就往左孩子走一个,0往右边走一个,实时判断是否走到了叶子结点->当走到了叶子结点,结束,读取走到当前p节点的data存放的字符,写入文件即可.

                    

    1. int main()
    2. {
    3. 	
    4. 	char srcFile[256] = "2.txt";//压缩后文件
    5. 	char dstFile[256] = "3.txt";//解压后文件
    6.  
    7. 	allZifu zd = { 0 };//字典
    8. 	// 1 读取字典
    9. 	FILE* fpSrc = fopen(srcFile, "rb");
    10. 	fread(&zd, 1, sizeof(allZifu), fpSrc);
    11. 	
    12. 	FILE* fpDst = fopen(dstFile, "wb");
    13. 	//2 根据字典生成haffman树
    14. 	treeNode* root =  createHaffmanTree(&zd);
    15.  
    16. 	//3 循环读取
    17. 	//3.0 统计字节数
    18. 	int allCount = root->data.count;//根节点就保存了总的字节数
    19. 	printf("字节数为:%d\n", allCount);
    20.  
    21. 	int myCount = 0;
    22. 	char temp;
    23.  
    24. 	int bit_idx;//比特位的索引
    25. 	treeNode* tempNode = root;
    26. 	bool isOver = false;
    27. 	while (1 == fread(&temp,1,1,fpSrc))
    28. 	{
    29. 		bit_idx = 0;
    30. 		while (bit_idx < 8)
    31. 		{/*0x80是 1000 0000*/
    32. 			if ((0x80 >> bit_idx) == (temp&((0x80 >> bit_idx))))
    33. 			{//当前位为 1
    34. 				tempNode = tempNode->pLeft;
    35. 			}
    36. 			else
    37. 			{
    38. 				tempNode = tempNode->pRight;
    39. 			}
    40. 			if (isLeaf(tempNode))//若走到了叶子结点√---->就写一个字符(tempNode结点存储的字符即可)
    41. 			{
    42. 				fwrite(&(tempNode->data.zf), 1, 1, fpDst);
    43. 				myCount++;
    44. 				if (myCount >= allCount) 
    45. 				{
    46. 					isOver = true;
    47. 					break;
    48. 				}
    49. 				tempNode = root;//继续下一个字符
    50. 			}
    51. 			bit_idx++;
    52. 		}
    53. 		if (isOver) break;
    54. 	}
    55.  
    56. 	fclose(fpSrc);
    57. 	fclose(fpDst);
    58. 	printf("解压缩完毕!\n");
    59. 	system("pause");
    60. 	return 0;
    61. }

    四、利用栈和堆---Huffman树的写法:

    数据结构 --- 栈和堆实现哈夫曼树_https://blog.csdn.net/weixin_60569662/article/details/123376155

  • 相关阅读:
    特征工程设计思路
    Spring中使用了哪些设计模式
    Java面向对象进阶
    如何添加葫芦儿派盘
    Linux死锁
    上机实验三 图的最小生成树算法设计 西安石油大学数据结构
    gradle-7.6.3-all 快速下载百度网盘下载
    OpenHarmony实战开发-如何实现tabContent内容可以在tabBar上显示并且tabBar可以响应滑动事件的功能。
    软件配置管理计划
    OSCAR数据库上锁问题如何排查
  • 原文地址：https://blog.csdn.net/zjjaibc/article/details/126240699