In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since “aaaxuaxz” and “aazuaxax” can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.
Input Specification:
Each input file contains one test case. For each case, the first line gives an integer
NN
N
(
2≤N≤632\le N\le 63
2
≤
N
≤
6
3
), then followed by a line that contains all the
NN
N
distinct characters and their frequencies in the following format:
c[1] f[1] c[2] f[2] ... c[N] f[N]
where
c[i]
is a character chosen from {‘0’ – ‘9’, ‘a’ – ‘z’, ‘A’ – ‘Z’, ‘_’}, and
f[i]
is the frequency of
c[i]
and is an integer no more than 1000. The next line gives a positive integer
MM
M
(
≤1000\le 1000
≤
1
0
0
0
), then followed by
MM
M
student submissions. Each student submission consists of
NN
N
lines, each in the format:
c[i] code[i]
where
c[i]
is the
i
-th character and
code[i]
is an non-empty string of no more than 63 ‘0’s and ‘1’s.
Output Specification:
For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not.
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.
Sample Input:
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
Sample Output:
Yes
Yes
No
No
/*
体会：
这道题写了有8个小时了。
这题主要考察:
1.哈夫曼树，建立依靠最小堆，在堆中存储树的节点 。
2.最小wpl的判断。只要符合长度的都是最小wpl，哈夫曼树不唯一，但最小值是唯一的，所以只要判断是否为前缀码，再比较wpl值即可。
*/
#include <stdio.h> #include <stdlib.h> #include <string.h> #define Maxn 64 int N, w[Maxn]; char ch[Maxn]; int codelen, cnt1, cnt2; typedef struct TreeNode* Tree; struct TreeNode { int Weight; Tree Left, Right; }; typedef struct HeapNode* Heap; struct HeapNode { struct TreeNode Data[Maxn]; int Size; }; Tree CreatTree() { Tree T; T = (Tree)malloc(sizeof(struct TreeNode)); T->Left = T->Right = NULL; T->Weight = 0; return T; } Heap CreatHeap() { Heap H; H = (Heap)malloc(sizeof(struct HeapNode)); H->Size = 0; H->Data[0].Weight = -1; return H; } void Insert(Heap H, struct TreeNode T) { int i = ++H->Size; for( ; T.Weight < H->Data[i/2].Weight; i /= 2) H->Data[i] = H->Data[i/2]; H->Data[i] = T; } Tree Delete(Heap H) { int parent, child; struct TreeNode Temp = H->Data[H->Size--]; Tree T = CreatTree(); *T = H->Data[1]; for(parent = 1; 2*parent <= H->Size; parent = child) { child = 2 * parent; if(child != H->Size && H->Data[child].Weight > H->Data[child+1].Weight) child++; if(Temp.Weight < H->Data[child].Weight) break; H->Data[parent] = H->Data[child]; } H->Data[parent] = Temp; return T; } Tree Huffman(Heap H) { Tree T = CreatTree(); //分配空间 while(H->Size != 1) { T->Left = Delete(H); T->Right = Delete(H); T->Weight = T->Left->Weight + T->Right->Weight; //printf("l = %d, r = %d, t = %d\n", T->Left->Weight, T->Right->Weight, T->Weight); Insert(H, *T); } T = Delete(H); return T; } void PreTravel(Tree T) { if(T) { printf("%d ", T->Weight); PreTravel(T->Left); PreTravel(T->Right); } } int WPL(Tree T, int Depth) { if(!T->Left && !T->Right) { /*printf("d = %d w = %d\n", Depth, T->Weight);*/ return Depth*T->Weight; } else return WPL(T->Left, Depth+1) + WPL(T->Right, Depth+1); } void JudgeTree(Tree T) { if(T) { if(T->Left && T->Right) cnt2++; else if(!T->Left && !T->Right) cnt1++; else cnt1 = 0; JudgeTree(T->Left); JudgeTree(T->Right); } } int Judge() { int i, j, wgh, flag = 1; char s1[Maxn], s2[Maxn]; Tree T = CreatTree(), pt = NULL; for(i = 0; i < N; i++) { scanf("%s%s", s1, s2); if(strlen(s2) > N) return 0; for(j = 0; s1[0] != ch[j]; j++); wgh = w[j]; pt = T;//每次建树前先将指针移动到根节点上； for(j = 0; s2[j]; j++) { if(s2[j] == '0') { if(!pt->Left) pt->Left = CreatTree(); pt = pt->Left; } if(s2[j] == '1') { if(!pt->Right) pt->Right = CreatTree(); pt = pt->Right; } if(pt->Weight) flag = 0; if(!s2[j+1]) { if(pt->Left || pt->Right) flag = 0;//判断是否为前缀 pt->Weight = wgh; } //printf("w = %d\n", pt->Weight); } } if(!flag) return 0; cnt1 = cnt2 = 0; JudgeTree(T);//判断是否不存在度数1的节点 if(cnt1 != cnt2 + 1) return 0; //printf("wpl = %d\n", WPL(T, 0)); if(codelen == WPL(T, 0)) return 1; else return 0; } int main() { int i, n; Heap H; Tree T; H = CreatHeap(); T = CreatTree(); scanf("%d", &N); for(i = 0; i < N; i++) { getchar(); scanf("%c %d", &ch[i], &w[i]); H->Data[H->Size].Left = H->Data[H->Size].Right = NULL; T->Weight = w[i]; Insert(H, *T); } //for(i = 1; i <= H->Size; i++) printf("%d ", H->Data[i].Weight); T = Huffman(H); //PreTravel(T); codelen = WPL(T, 0); scanf("%d", &n); while(n--) { if(Judge()) printf("Yes\n"); else printf("No\n"); } return 0; }