데이터 구조 05 - 트 리 9 Huffman 코드

제목.
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 N (2≤N≤63), then followed by a line that contains all the 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 M (≤1000), then followed by M student submissions. Each student submission consists of 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
분석 하 다.
대개 입력 한 문자 와 주파수 에 따라 제 시 된 문자 인 코딩 이 가장 좋 은 인 코딩 인지 아 닌 지 를 판단 하 는 것 입 니 다.
제출 오 류 는 샘플 출력 이 "yes"와 "No"가 아니 라 "yes"와 "no"라 는 것 을 알 게 될 때 까지 밤새 바 뀌 었 습 니 다.
해법
순 전 히 시 뮬 레이 션 을 통 해 하 프 만 나 무 를 만 들 고 모든 학생 들 의 제출 에 따라 나 무 를 만 드 는 것 이 가장 좋 은 지 여 부 를 판단 한다.규칙 에 따라 하 프 만 트 리 를 최소 화하 고 최소 로 삽입 하 며 최소 로 삭제 하고 최소 로 초기 화 하 며 하 프 만 트 리 를 만 듭 니 다.그 다음 에 본 연극 이 시작 되 었 습 니 다. 입력 문자 가 '0' 이 고 왼쪽 트 리 를 만 들 고 입력 문자 가 '1' 이 며 오른쪽 트 리 를 만 든 다음 에 입력 문자열 이 끝 난 곳 에 가중치 를 저장 합 니 다. 한 그룹의 데이터 입력 이 완료 되면 나무 한 그루 를 얻 을 수 있 습 니 다. 이 나무의 노드 개 수 를 검증 합 니 다. WPL 이 가장 좋 은 하프 만 트 리 와 같 는 지 확인 합 니 다.

#include
#include
#include
#include
#include
#define HeapCapacity 64
#define MinData 0
typedef struct TreeNode *HuffmanTree;
typedef struct Heap *MinHeap;
struct Heap{   //   
	HuffmanTree *data;  //       
	int size; //        
};
struct TreeNode{   //      
	int weight;  //   
	HuffmanTree left; 
	HuffmanTree right; 
};
using namespace std;

MinHeap createHeap();   //    
HuffmanTree createHuffman();  //       
void sortHeap(MinHeap H,int i); //        
void adjust(MinHeap H);  //     
MinHeap InitHeap(int n); //      
HuffmanTree Delete(MinHeap H); //      
void Insert(MinHeap H,HuffmanTree Huff); //      
HuffmanTree Huffman(MinHeap H);  //         
int WPL(HuffmanTree Huff,int depth); //    HuffmanTree       


map<char,int> mappp;  //              

//    
MinHeap createHeap(){
	MinHeap H;
	H = (MinHeap)malloc(sizeof(struct Heap));
	H->data = (HuffmanTree *)malloc(sizeof(struct TreeNode) * HeapCapacity);
	H->size = 0; 
	//     
	HuffmanTree Huff = createHuffman();
	H->data[0] = Huff; 
	return H;
}

//       
HuffmanTree createHuffman(){
	HuffmanTree Huff;
	Huff = (HuffmanTree)malloc(sizeof(struct TreeNode));
	Huff->weight = MinData;   //          
	Huff->left = NULL;
	Huff->right = NULL;
	return Huff;
}

//        
void sortHeap(MinHeap H,int i){
	int parent,child;
	HuffmanTree Huff = H->data[i]; //             
	for(parent = i;parent*2<=H->size;parent = child){
		//          
		child = parent * 2; 
		if((child!=H->size) && (H->data[child+1]->weight < H->data[child]->weight))
			child++;
		//       ，     
		if(Huff->weight <= H->data[child]->weight)
			break;
		//           
		H->data[parent] = H->data[child]; 
	}
	H->data[parent] = Huff;
} 


//     
void adjust(MinHeap H){
	//                  
	for(int i=H->size/2;i>0;i--)
		sortHeap(H,i); 
}

//      
MinHeap InitHeap(int n){
	MinHeap H =createHeap();
	HuffmanTree Huff;
	char c;  //        
	int f;  //         
	for(int i=0;i<n;i++){
		getchar();
		scanf("%c %d",&c,&f);
		mappp.insert(pair<char,int>(c,f));  //              map 
		Huff = createHuffman();
		Huff->weight = f;
		H->data[++H->size] = Huff;
	}
	//       
	adjust(H);
	return H;
}

//      
HuffmanTree Delete(MinHeap H){
	int parent,child;
	HuffmanTree T = H->data[1]; //            
	HuffmanTree Huff = H->data[H->size--];  //               
	for(parent = 1;parent*2<=H->size;parent = child){
		//          
		child = parent * 2; 
		if((child!=H->size) && (H->data[child+1]->weight < H->data[child]->weight))
			child++;
		//       ，     
		if(Huff->weight <= H->data[child]->weight)
			break;
		//           
		H->data[parent] = H->data[child]; 
	}
	H->data[parent] = Huff;
	return T;
} 

//     
void Insert(MinHeap H,HuffmanTree Huff){
	int i = ++H->size; 
	for(;Huff->weight < H->data[i/2]->weight;i/=2)
		H->data[i] = H->data[i/2];
	H->data[i] = Huff;
} 

//         
HuffmanTree Huffman(MinHeap H){
	HuffmanTree Huff;
	int times = H->size;
	for(int i=1;i<times;i++){
		Huff = createHuffman();
		Huff->left = Delete(H);  //          ，    T       
		Huff->right = Delete(H);  //          ，    T       
		Huff->weight = Huff->left->weight + Huff->right->weight; //        
		Insert(H,Huff);   //       
	}
	Huff = Delete(H);
	return Huff;
} 

//    HuffmanTree       
int WPL(HuffmanTree Huff,int depth){
	//       ，       
	if(Huff->left==NULL && Huff->right==NULL)
		return depth*Huff->weight;
	else  //                 
		return (WPL(Huff->left,depth+1) + WPL(Huff->right,depth+1));
}

//    
void submit(int n,int codeLen){
	HuffmanTree Huff = createHuffman();
	HuffmanTree pre;
	int counter = 1;
	bool flag = true;
	char ch;
	string code; 
	for(int i=0;i<n;i++){
		getchar();
		pre = Huff; 
		//      
		scanf("%c",&ch);
		cin>>code;
		//      
		for(int j=0;j<code.size();j++){
			if(code[j]=='0'){  //         0，    
				if(pre->left==NULL){   //         ，   
					pre->left =createHuffman();
					counter++;
				}
				if(pre->weight != 0)
					flag =false;
				pre = pre->left;
			}else if(code[j]=='1'){ //         0，    
				if(pre->right==NULL){   //         ，   
					pre->right = createHuffman();
					counter++;
				}
				if(pre->weight != 0)
					flag =false;
				pre = pre->right;
			}
		}
		if(pre->left || pre->right)
			flag = false;
		pre->weight = mappp[ch];   //   mapp       
	}
	if(counter!=2*n-1 || !flag || WPL(Huff,0) != codeLen){ //        2n-1              
		printf("No
");
		return;
	}else{
		printf("Yes
");
		return;
	}
} 


int main(){
	int n,m;
	scanf("%d",&n);
	//        
	MinHeap H = InitHeap(n);
	//         
	HuffmanTree Huff = Huffman(H);
	//              
	int codeLen = WPL(Huff,0); 
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		submit(n,codeLen);
	} 
	return 0;
}

알고리즘 2
교묘 한 알고리즘 은 STL 에서 최소 더미, 즉 priority_queue,greater >q 를 실 현 했 습 니 다. WPL 도 트 리 높이 로 계산 하지 않 고 매번 에 두 번 씩 팀 에 들 어 가 는 것 을 모 의 하고 한 번 씩 팀 에 들 어 갈 때마다 입 대 된 값 을 더 하면 최종 적 으로 얻 은 값 은 WPL 학생 이 제출 한 WPL 이 입력 한 문자 길이 * 이 문자 의 빈 도 를 합 친 다음 에 제출 에 접두사 가 존재 하 는 지 확인 하면 제출 이 가장 좋 은 지 여 부 를 판단 할 수 있 습 니 다.

#include
#include 
#include
#include
#define MaxSize 64
using namespace std;
priority_queue<int,vector<int>,greater<int> >q; //       ，       
map<char,int> mapp;  
struct character{
	char ch;   //    
	int fre;  //    
};
struct huffmanTree{
	char ch;  //    
	string str;  //    
};


//   
int bulidTree(int n,character c[]){
	int weight = 0;
	//    
	for(int i=0;i<n;i++)
		q.push((c[i].fre));
	while(q.size()>1){ 
		//        
		int x = q.top();
		//        
		q.pop();
		int y = q.top();
		q.pop();
		//    
		q.push(x+y);
		weight += x+y;  //        
		//          
	}
	q.pop();
	return weight;
}
bool cmp(huffmanTree a,huffmanTree b){
	return a.str.size() < b.str.size();
}

//        
bool isPrefix(huffmanTree code[],int n){
	//              
	sort(code,code+n,cmp); 
	for(int i=0;i<n;i++){
		string str = code[i].str;
		for(int j=i+1;j<n;j++){ //         
			//                    ，     
			if(code[j].str.substr(0,str.size()) == str)
				return true;
		}
	}
	return false; 
}

void judge(int n,character c[],int weight){
	//    WPL 
	huffmanTree code[MaxSize];
	int codelen = 0;
	for(int i=0;i<n;i++){
		cin>>code[i].ch>>code[i].str;
		//           *     
		codelen += mapp[code[i].ch]*code[i].str.size();  
	}
	if(codelen != weight || isPrefix(code,n))
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
} 

int main(){
	int n;
	int m;
	cin>>n;
	character c[MaxSize];
	for(int i=0;i<n;i++){
		cin>>c[i].ch>>c[i].fre;
		mapp[c[i].ch] = c[i].fre;
	}
	int weight = bulidTree(n,c);
	cin>>m;
	for(int i=0;i<m;i++)
		judge(n,c,weight);
	return 0;
}