• 哈夫曼编码原理

    一、应用背景

    给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 'a'、'x'、'u'、'z' 的出现频率对应为 4、2、1、1。我们可以设计编码 {'a'=0, 'x'=10, 'u'=110, 'z'=111}，也可以用另一套 {'a'=1, 'x'=01, 'u'=001, 'z'=000}，还可以用 {'a'=0, 'x'=11, 'u'=100, 'z'=101}，三套编码都可以把原文压缩到 14 个字节。但是 {'a'=0, 'x'=01, 'u'=011, 'z'=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，"aaaxuaxz" 和 "aazuaxax" 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

    输入格式：

    首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

    c[1] f[1] c[2] f[2] ... c[N] f[N]

    其中c[i]是集合{'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

    c[i] code[i]

    其中c[i]是第i个字符；code[i]是不超过63个'0'和'1'的非空字符串。

    输出格式：

    对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

    注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

    输入样例：

    1. 7
    2. A 1 B 1 C 1 D 3 E 3 F 6 G 6
    3. 4
    4. A 00000
    5. B 00001
    6. C 0001
    7. D 001
    8. E 01
    9. F 10
    10. G 11
    11. A 01010
    12. B 01011
    13. C 0100
    14. D 011
    15. E 10
    16. F 11
    17. G 00
    18. A 000
    19. B 001
    20. C 010
    21. D 011
    22. E 100
    23. F 101
    24. G 110
    25. A 00000
    26. B 00001
    27. C 0001
    28. D 001
    29. E 00
    30. F 10
    31. G 11

    输出样例：

    1. Yes
    2. Yes
    3. No
    4. No

    二、具体实现 

    在完成这道题之前， 首先要对构建哈夫曼树和哈夫曼编码的框架有一定的理解。

    之后再根据题目的要求进行恰当的修改。

    以下代码参考   清华大学 《数据结构》（C语言版）严蔚敏 吴伟民 编著  

    ---------------------------------------数组从1开始，0未用。

    框架代码如下： 

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. #define MAXSIZE 100
    7.  
    8. typedef struct{
    9. 	int weight;
    10. 	int parent,lchild,rchild;
    11. }HTNode,*HuffmanTree;
    12.  
    13. typedef char** HuffmanCode;
    14.  
    15. void Init_HuffmanTree(HuffmanTree &HT,int n)
    16. {
    17. 	int m = 2*n-1;
    18. 	HT = (HuffmanTree)malloc(sizeof(HTNode)*(m+1));
    19. 	for(int i=0;i<=m;i++)
    20. 	{
    21. 		HT[i].parent=0;
    22. 		HT[i].lchild=0;
    23. 		HT[i].rchild=0;
    24. 	}
    25. }
    26.  
    27. void Select(HuffmanTree HT,int *S1,int *S2,int m)
    28. {
    29. 	int minweight=10000;
    30. 	
    31. 	for(int i=1;i
    32. 	{
    33. 		if(HT[i].weight0)
    34. 		{
    35. 			minweight = HT[i].weight;
    36. 			*S1 = i;
    37. 		}
    38. 	}
    39. 	
    40. 	minweight=10000;
    41. 	
    42. 	for(int i=1;i
    43. 	{
    44. 		if(HT[i].weight0 && i!=*S1)
    45. 		{
    46. 			minweight = HT[i].weight;
    47. 			*S2 = i;
    48. 		}
    49. 	}
    50. 	
    51. }
    52.  
    53. void Creat_HuffmanTree(HuffmanTree &HT,int n)
    54. {
    55. 	int m = 2*n-1;
    56. 	int s1,s2;
    57. 	if(n<=1)
    58. 		return;
    59. 	
    60. 	for(int i=n+1;i<=m;i++)
    61. 	{
    62. 		Select(HT,&s1,&s2,i);
    63. 		HT[s1].parent=i;
    64. 		HT[s2].parent=i;
    65. 		HT[i].lchild=s1;
    66. 		HT[i].rchild=s2;
    67. 		HT[i].weight=HT[s1].weight+HT[s2].weight;
    68. 	}
    69. }
    70.  
    71. void Print_HuffmanTree(HuffmanTree HT,int n)
    72. {
    73. 	cout<<"index"<<"\t"<<"weight"<<"\t"<<"parent"<<"\t"<<"lchild"<<"\t"<<"rchild"<
    74. 	for(int i=1;i<=2*n-1;i++)
    75. 	{
    76. 		cout<"\t"<"\t"<"\t"<"\t"<
    77. 	}
    78. }
    79.  
    80. void Creat_HuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
    81. {
    82. 	char *cd;
    83. 	int c,f,start;
    84. 	HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));
    85. 	cd = (char*)malloc(sizeof(char)*n);
    86. 	cd[n-1]='\0';
    87. 	
    88. 	for(int i=1;i<=n;i++)
    89. 	{
    90. 		start = n-1;
    91. 		c=i;
    92. 		f=HT[i].parent;
    93. 		while(f!=0)
    94. 		{
    95. 			start--;
    96. 			if(HT[f].lchild==c)
    97. 				cd[start]='0';
    98. 			else cd[start]='1';
    99. 			
    100. 			c=f;
    101. 			f=HT[f].parent;
    102. 		}
    103. 		
    104. 		HC[i] = (char*)malloc(sizeof(char)*(n-start));
    105. 		strcpy(HC[i],&cd[start]);
    106. 	}
    107. 	free(cd);
    108. }
    109.  
    110. void Print_HuffmanCode(char ch[][MAXSIZE],HuffmanCode HC,int n)
    111. {
    112. 	for(int i=1;i<=n;i++)
    113. 	{
    114. 		cout<" ";
    115. 		cout<
    116. 	}
    117. }
    118.  
    119. int main()
    120. {
    121. 	int n;
    122. 	char ch[MAXSIZE][MAXSIZE];
    123. 	HuffmanTree HT;
    124. 	HuffmanCode HC;
    125. 	
    126. 	
    127. 	cin>>n;
    128. 	Init_HuffmanTree(HT,n);
    129. 	
    130. 	for(int i=1;i<=n;i++)
    131. 	{
    132. 		cin>>ch[i]>>HT[i].weight;
    133. 	}
    134. 	
    135. 	
    136. 	Creat_HuffmanTree(HT,n);
    137. 	Creat_HuffmanCode(HT,HC,n);
    138. 	
    139. 	cout<
    140. 	Print_HuffmanTree(HT,n);
    141. 	cout<
    142. 	Print_HuffmanCode(ch,HC,n);
    143. 	cout<
    144. 	return 0;
    145. }

    整体思路总结如下：

     构造最优二叉树（哈夫曼树），a、b、c、d、e的权值依次为7、5、5、2、4 。 程序运行结果如上图2。

     在有了相应的基础后，我们再来看这道题目。

    仔细阅读题目过后我们发现，本题的初衷并不是让我们求出哈夫曼编码。题干说：“注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。”

    这道题的解题思路为：先求出哈夫曼编码的的最短加权路径和然后再判断是不是前缀编码。两者缺一不可。

     完整代码如下：

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. #define MAXSIZE 100
    7.  
    8. typedef struct{
    9. 	int weight;
    10. 	int parent,lchild,rchild;
    11. }HTNode,*HuffmanTree;
    12.  
    13. typedef char** HuffmanCode;
    14.  
    15. void Init_HuffmanTree(HuffmanTree &HT,int n)
    16. {
    17. 	int m = 2*n-1;
    18. 	HT = (HuffmanTree)malloc(sizeof(HTNode)*(m+1));
    19. 	for(int i=0;i<=m;i++)
    20. 	{
    21. 		HT[i].parent=0;
    22. 		HT[i].lchild=0;
    23. 		HT[i].rchild=0;
    24. 	}
    25. }
    26.  
    27. void Select(HuffmanTree HT,int *S1,int *S2,int m)
    28. {
    29. 	int minweight=10000;
    30. 	
    31. 	for(int i=1;i
    32. 	{
    33. 		if(HT[i].weight0)
    34. 		{
    35. 			minweight = HT[i].weight;
    36. 			*S1 = i;
    37. 		}
    38. 	}
    39. 	
    40. 	minweight=10000;
    41. 	
    42. 	for(int i=1;i
    43. 	{
    44. 		if(HT[i].weight0 && i!=*S1)
    45. 		{
    46. 			minweight = HT[i].weight;
    47. 			*S2 = i;
    48. 		}
    49. 	}
    50. 	
    51. }
    52.  
    53. void Creat_HuffmanTree(HuffmanTree &HT,int n)
    54. {
    55. 	int m = 2*n-1;
    56. 	int s1,s2;
    57. 	if(n<=1)
    58. 		return;
    59.  
    60. //这里需要注意i是从n+1开始的	
    61. 	for(int i=n+1;i<=m;i++)
    62. 	{
    63. 		Select(HT,&s1,&s2,i);
    64. 		HT[s1].parent=i;
    65. 		HT[s2].parent=i;
    66. 		HT[i].lchild=s1;
    67. 		HT[i].rchild=s2;
    68. 		HT[i].weight=HT[s1].weight+HT[s2].weight;
    69. 	}
    70. }
    71.  
    72. void Print_HuffmanTree(HuffmanTree HT,int n)
    73. {
    74. 	cout<<"index"<<"\t"<<"weight"<<"\t"<<"parent"<<"\t"<<"lchild"<<"\t"<<"rchild"<
    75. 	for(int i=1;i<=2*n-1;i++)
    76. 	{
    77. 		cout<"\t"<"\t"<"\t"<"\t"<
    78. 	}
    79. }
    80.  
    81. int Creat_HuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
    82. {
    83. 	char *cd;
    84. 	int c,f,start;
    85. 	HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));
    86. 	cd = (char*)malloc(sizeof(char)*n);
    87. 	cd[n-1]='\0';
    88. 	
    89. 	for(int i=1;i<=n;i++)
    90. 	{
    91. 		start = n-1;
    92. 		c=i;
    93. 		f=HT[i].parent;
    94. 		while(f!=0)
    95. 		{
    96. 			start--;
    97. 			if(HT[f].lchild==c)
    98. 				cd[start]='0';
    99. 			else cd[start]='1';
    100. 			
    101. 			c=f;
    102. 			f=HT[f].parent;
    103. 		}
    104. 		
    105. 		HC[i] = (char*)malloc(sizeof(char)*(n-start));
    106. 		strcpy(HC[i],&cd[start]);
    107. 	}
    108. 	
    109. 	
    110. 	int sum=0;
    111. 	for(int i=n+1;i<2*n;i++)
    112. 	{
    113. 		sum+=HT[i].weight;
    114. 	}
    115. 	
    116. 	free(cd);
    117. 	return sum;
    118. }
    119.  
    120. void Print_HuffmanCode(char ch[][MAXSIZE],HuffmanCode HC,int n)
    121. {
    122. 	for(int i=1;i<=n;i++)
    123. 	{
    124. 		cout<" ";
    125. 		cout<
    126. 	}
    127. }
    128.  
    129. int IsPrefix(char code[MAXSIZE][MAXSIZE],int n)  //判断是否是前缀式编码 
    130. {
    131. 	int flag=1; //1为是前缀式编码，0为否 
    132. 	for (int i = 1;i <= n;i++)
    133. 	{
    134. 		int j = i+1;
    135. 		while (j <= n && j!=i && flag == 1)
    136. 		{
    137. 			if (strstr(code[j-1], code[i-1]) != code[j-1]) //运用strstr函数 
    138. 			{
    139. 				if (j == n)
    140. 					j = 1;
    141. 				else j++;
    142. 			}
    143. 			else {
    144. 				flag = 0;
    145. 			}
    146. 		}
    147.  
    148. 		if (flag == 0)
    149. 		{
    150. 			break;
    151. 		}
    152. 	}
    153.  
    154. 	return flag;
    155. }
    156.  
    157. int main()
    158. {
    159. 	int n,sum_weight;
    160. 	char ch[MAXSIZE][MAXSIZE];
    161. 	HuffmanTree HT;
    162. 	HuffmanCode HC;
    163.  
    164. 	cin>>n;
    165. 	Init_HuffmanTree(HT,n);
    166. 	
    167. 	for(int i=1;i<=n;i++)
    168. 	{
    169. 		cin>>ch[i]>>HT[i].weight;
    170. 	}
    171. 	
    172. 	
    173. 	Creat_HuffmanTree(HT,n);
    174. 	sum_weight = Creat_HuffmanCode(HT,HC,n);
    175. 	
    176. 	//Print_HuffmanTree(HT,n);
    177. 	//Print_HuffmanCode(ch,HC,n);
    178. 	
    179. 	//开始读入各段哈夫曼编码
    180. 	int M,sum=0;
    181. 	cin>>M;
    182. 	char code[MAXSIZE][MAXSIZE];
    183. 	char c;
    184. 	
    185. 	for(int i=1;i<=M;i++)
    186. 	{
    187. 		sum=0;
    188. 		for(int j=0;j
    189. 		{
    190. 			cin>>c>>code[j];
    191. 			sum+=strlen(code[j])*HT[j+1].weight; //求输入的加权路径：编码长度*权重 
    192. 		}
    193. 		if(sum!=sum_weight) //先判断最短加权路径和是否相等，若不等直接No,若相等，判断是否是前缀码 
    194. 		{
    195. 			cout<<"No"<
    196. 		}else{
    197. 			if(IsPrefix(code,n)==1)
    198. 				cout<<"Yes"<
    199. 			else cout<<"No"<
    200. 		}
    201. 	}
    202. 	return 0;
    203. }

    下面我们来看这个代码，注意与第一个框架代码做对比。

    • 首先在 Creat_HuffmanCode（） 函数中，我们加入如下代码1，来求最短加权路径和。用于与主函数中（代码2）输入的哈夫曼编码作比较。
    • 依照上面的图1，找到相应的数学关系。
    1. //代码1
    2. int sum=0;
    3. 	for(int i=n+1;i<2*n;i++)  //注意从n+1开始
    4. 	{
    5. 		sum+=HT[i].weight;
    6. 	}
    7.  
    8. return sum;
    1. //代码2
    2. sum=0;
    3. 		for(int j=0;j
    4. 		{
    5. 			cin>>c>>code[j];
    6. 			sum+=strlen(code[j])*HT[j+1].weight; //求输入的加权路径：编码长度*权重 
    7. 		}
    • 写了 IsPrefix（） 函数用于判断是否是前缀码。相应代码的思路如下：

    前缀编码定义：
    （字符集中）任一编码都不是其它字符的编码的前缀


    例：
    (1)找出下面不是前缀编码的选项
    A{1，01，000，001}
    B{1，01，011，010}
    C{0，10，110，11}
    D{0，1，00，11}

    第一步：看A中的第一个数1，看看其他数有没有1开头的。没有。
    第二步：看A中的第二个数01，看看其他数有没有01开头的。没有。
    第三步：看看A中的第三个数000，看看其他数有没有000开头的。没有。
    第四步：看看A中的第四个数001，看看其他数有没有001开头的。没有。
    所以A是前缀编码。

    其他选项也一样。B、C也一样。来说说D：

    第一步，看D中的第一个数，找有0开头的的数，有，是00；其实到这里已经不用看了
    因为D已经不是前缀编码了。
    但第二个数1，是第四个数11的前缀，所以也能作为D不是前缀编码的理由。

      IsPrefix（） 函数中应用了strstr()函数。解释如下：

    最后，题干的测试数据：

    1. 4
    2. a 4
    3. x 2
    4. u 1
    5. z 1
    6. 4
    7. a 0
    8. x 10
    9. u 110
    10. z 111
    11. a 1
    12. x 01
    13. u 001
    14. z 000
    15. a 0
    16. x 11
    17. u 100
    18. z 101
    19. a 0
    20. x 01
    21. u 011
    22. z 001

  • 相关阅读:
    VBA和VBS之不同
    AirServer2024免费功能强大的投屏软件
    Redis订阅模式在生产环境引起的内存泄漏
    Web版RSS阅读器yarr
    21.Hadoop在Windows环境下的下载安装配置超详细版
    818专业课【考经】—《信号系统》之章节概要：第五章 连续时间信号的变换域分析
    Day16：C++之STL应用篇(推箱子cxk限定)
    每日一个设计模式之【工厂模式】
    Oracle-数据库对象的使用
    【Vue 开发实战】基础篇 # 6：双向绑定和单向数据流不冲突
  • 原文地址：https://blog.csdn.net/a15608445683/article/details/125882298