PTA 05-哈夫曼编码 哈夫曼编码
题目描述：
如果我们统计出每个字母在给定文本中的出现频率，则可以通过哈夫曼算法设计一套独特的编码方案以实现对原文的最有效压缩。然而需要注意的是哈夫曼编码方案并不唯一因此在实际应用中可能会有多种不同的最优解选择不同的码字分配方式来满足特定的技术要求和性能指标需求。例如对于字符串"aaaxuaxz"我们能够得到四个字符'a'x'u'z的频率分布分别为4211个单位在此基础上我们可以构造多套不同的码字分配方案如{'a'=0x=10u=110z=111}{'a'=1x=01u=001z=000}以及{'a'=0x=11u=100z=101'}这些方案都能将原文压缩至最低限度即共需使用十六位二进制码共计十四个单位长度（即总长度为十四位）。但是若采用另一组码字分配{'a'=0x=01u=01
l z= 》则会导致无法达到最优压缩效果因为这种分配方式下存在冗余码导致最终解码结果不唯一例如解码后的字符串可能变为"aaaauxaxz"或者"aazuaaxax"等具体情况视具体的输入数据而定因此这种非标准的哈夫曼编
码方案就不能满足严格的通信系统需求
输入格式：
在第一行表示为一个正整数 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。在输入时，请先提供一个不超过 1000 的正整数 M（M ≤ 1000），随后读取 M 套待检的编码数据。每一组编码将占用 N 行，并遵循以下具体格式：
c[i] code[i]其中c[i]是第i个字符；code[i]是不超过63个'0'和'1'的非空字符串。
输出格式：
对于每一套待检编码而言，在判定其是否为有效的哈夫曼编码时，在一行中输出的结果将是“Yes”，而如果判定结果为否，则应输出“No”。
特别注意：最佳编码并非总是由哈夫曼算法生成。对于能够达到最短平均码长的所有前缀码而言，都应该被视为正确的方案。
输入样例：
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11输出样例：
Yes
Yes
No
No具体来说，在信息论中给定一组特定的字符及其每个字符对应的出现频率时，给定这些字符的编码方案并判断该编码方案是否属于哈夫曼编码是一个典型的应用场景
针对题目要求进行解析与分析，请判断所给案例编码方案是否属于最优长度的前缀编码中的一个。
1、是最优长度编码（也就是WPL）。
遵循前缀编码规则（即没有任何一个代码是其他代码的前缀），例如案例四所示，在这种情况下,E采用的是二进制码00,并且这与A,B,C,D所使用的二进制码一致,导致解码过程中可能出现歧义现象,从而导致最终解码结果各不相同）。
首先我们要求的是最优长度编码。
举个例子：构造A1 B2 C2 D5 E9的哈夫曼树以及求其WPL。
这便是构造出的哈夫曼树。WPL = （|A|+|B|）* 4 + |C| * 3 + |D| * 2 + |E| * 1 = 37。这个是使用权值乘以路径长度，但是在计算其中非叶子节点的权值时，3 包含了1个(1+2)，5是用3得来的，所以也包含了一个(1+2)，同理10和19也是一样，所以如果直接将所有非叶子节点相加
WPL = 3 + 5 + 10 + 19 = 37。
所以我们可以用优先队列处理，代码如下：
priority_queue<int , vector<int>,greater<int>> que;
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
char x;
int num;
cin >> x >> num;
q[x] = num;
que.push(num);
}
int ans = 0;
while(que.size() >= 2)
{
int a = que.top(); que.pop();
int b = que.top(); que.pop();
que.push(a+b);
ans += a+b;
}
}这样求出的ans就是最优长度编码了。
接下来就是判断前缀编码了：
bool check(string s1,string s2)
{
int a = min(s1.size(),s2.size());
for(int i = 0;i < a;i++)
{
if(s1[i] != s2[i])
{
return true;
}
}
return false;
}方法也很简单，就是逐个比较如果有不同的就满足了。
AC代码如下：
#include<bits/stdc++.h>
using namespace std;
map<char,int> q;
int data[1010];
vector<int> arr;
priority_queue<int , vector<int>,greater<int>> que;
bool check(string s1,string s2)
{
int a = min(s1.size(),s2.size());
for(int i = 0;i < a;i++)
{
if(s1[i] != s2[i])
{
return true;
}
}
return false;
}
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++)
{
char x;
int num;
cin >> x >> num;
q[x] = num;
que.push(num);
}
int ans = 0;
while(que.size() >= 2)
{
int a = que.top(); que.pop();
int b = que.top(); que.pop();
que.push(a+b);
ans += a+b;
}
//cout << ans << endl;
int tt;
cin >> tt;
while(tt--)
{
int cnt = 0;
string s[1010];
for(int i = 1;i <= n;i++)
{
char x;
cin >> x >> s[i];
cnt += q[x]*s[i].size();//求案例的编码长度
}
//check最优
if(cnt != ans)
{
arr.push_back(0);
continue;
}
//check是否满足不是前缀编码
int flag = 0;
for(int i = 1;i <= n;i++)
{
for(int j = i+1;j <= n;j++)
{
if(!check(s[i],s[j]))
{
arr.push_back(0);
flag = 1;
break;
}
}
if(flag)
{
break;
}
}
if(!flag)
{
arr.push_back(1);
}
}
for(int i = 0;i < arr.size();i++)
{
if(arr[i])
{
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
return 0;
}同样将判断结果先放入vector容器，最后统一输出。