Huffman编码与Morse编码

Posted on   |   In

最近做课程设计，接触到了Huffman编码与Morse编码。在此总结，分享。之前认为编码是个很神奇的存在，现在能够用代码实现，感觉还是很开心的！

一、Huffman编码

1、概念（摘自wikipedia）

　　霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）演算法。也称“哈夫曼编码”，“赫夫曼编码”。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多馀编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

　　在计算机资料处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

　　例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个位元来表示，而z则可能花去25个位元（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个位元。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

　　霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。

HuffmanTree

2、算法

构造huffman树的哈夫曼算法如下：

（1）n节点的权值｛w1、w2、·····，wn｝构成n棵二叉树集合F=｛T1，T2，···，Tn｝，每棵二叉树Ti只有一个带权为Wi的根节点，左右孩子均空。

（2）在F中选取两棵根节点权值最小的作为树的左右孩子构造一棵新的二叉树，且置根节点的权值为左右孩子权值之和，在F中删除这两棵树，新二叉树放于集合F中。

（3）重复（2），直到F中只有一棵树为止，这棵树就是huffman树。

3、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
	说明：
    1、此程序用来构建Huffman树，对英文字母a-z根据词频统计生成Huffman码表；
    2、对指定文段进行Huffman编码，并计算编码总长度和平均码长；
    3、IDE为Dev C++ 5.4.1
*/
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

//构造树节点，parent作为判断这棵树是否在集合中，
//lchild为权值最小节点，rchild为权值第二小的节点，weight为节点的权值。
typedef struct {
	int weight;
	int parent, lchild, rchild;
}HuffmanNode, *HuffmanTree;

typedef char **HuffmanCode;

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n);
void HuffmanDecoding(HuffmanCode &HC, char* code_str, char* decode_str);
void select(HuffmanTree HT, int n, int &s1, int &s2);

//全局变量 
float w[26] = {8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 
	6.094, 6.966, 0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929,
	0.095, 5.987, 6.327, 9.056, 2.758, 0.978, 2.361, 0.150, 1.974, 0.074};
HuffmanTree HT;	
HuffmanCode HC;

//主函数 
//-----------------------------------------------------
int main (void) {
	
//	string code_str;
	string str;
	int i=0;
	double total_len=0.0, average_len=0.0;
	
	HuffmanCoding(HT, HC, w, 26);
	
	freopen("test_without_punctuation.txt", "r", stdin);
	char c;
	while( scanf("%c", &c) != EOF) {
		str+=c;
		if(str[i] >= 'a' && str[i] <= 'z')
			total_len += strlen(HC[str[i]-'a'+1]);
		//	cout << total_len << ' ' << i << endl;
		++i;
	}
	
	//输出 
	cout << "Total length of HuffmanCoding is: " << total_len << endl;
	average_len = total_len / i;
	cout << "Average length of HuffmanCoding is: " << average_len << endl; 

	free(HC);
	free(HT);
	return 0;
}
//-------------------------------------------------------

//Huffman编码函数 
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) {
	
	int m = 2*n-1;
	int s1, s2;
	HT = (HuffmanNode*)malloc((m+1)*sizeof(HuffmanNode));
	memset(HT, 0, (m+1)*sizeof(HuffmanNode));
	//初始化权值 
	for(int i=1; i<=n; i++)
		HT[i].weight = *w++;
	//创建Huffman tree
	for(int i=n+1; i<=m; i++) {
		//选择剩余节点中权值最小的节点s1,s2
		select(HT, i-1, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;		
	} 
	
	int start, c, f;
	HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
	char* cd = (char*)malloc(n*sizeof(char));
	cd[n-1] = '\0';
	for(int i=1; i<=n; i++) {
		
		start = n-1;
		for(c=i, f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
			if(HT[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		HC[i] = (char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i], &cd[start]);
	}
	//输出a-z的Huffman编码
	cout << "The HuffmanCode of a to z:\n"; 
	for(int i=1; i<=n; i++)
		cout << (char)('a'+i-1) << " : " << HC[i] << endl;
		
	free(cd);
} 
//最小权值选择函数 
void select(HuffmanTree HT, int n, int &s1, int &s2) {
	s1 = 1;
	s2 = 1;
	int min = 9999;
	int i;
	
	//找s1 
	for(int p = 1; p<=n; p++) {
		if(0 == HT[p].parent && min >= HT[p].weight) {
			s1 = p;
			min = HT[p].weight;
		}
	}
	//找s2
	min = 9999;
	for(int q = 1; q<=n; q++) {
		if(0 == HT[q].parent && min >= HT[q].weight) {
			if(q == s1)
				continue;
			s2 = q;
			min = HT[q].weight;
		}
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//Huffman译码函数,仅供参考，有BUG
void HuffmanDecoding(HuffmanCode &HC, char* code_str, char* decode_str) {
	
//	char decode_str[30];
	int j=0,k=0; //j为a-z序号，k为每段译码的序号 
	int t=0,s=0; //t变量作为检查是否编码被排除，s作为解码之后的字符数组序号 
	int cnt=0; 
	bool is_code[26];
	int test[26];
	memset(test, 0, sizeof(test));
	memset(is_code, true, sizeof(is_code));
	int len = strlen(code_str);
	for(int i=0; i<len; i++) {
		for(j=1; j<=26; j++)
			if(k>=strlen(HC[j]) || code_str[i] != HC[j][k])
				is_code[j-1] = false;
		k++;
		cnt=0;
		memset(test, 0, sizeof(test));
		for(t=0; t<26; t++)
			if(is_code[t]) {
				cnt++;
				test[cnt] = t;
			}
		if(cnt == 1 || (cnt == 2 && i == 15)) {
			for(t=0; t<26; t++)
				if(is_code[t]) {
					if(i == 15)
						decode_str[s++] = 'a'+7;
					else
						decode_str[s++] = 'a'+t;
					break;	
				}
			k=0;
			memset(is_code, true, sizeof(is_code));
		}	
	}
	cout << decode_str << endl;
}

二、Morse编码

1、概念(摘自wikipedia)

　　摩尔斯电码（英语：Morse Code）是一种时通时断的信号代码，通过不同的排列顺序来表达不同的英文字母、数字和标点符号。是由美国人萨缪尔·摩尔斯在1836年发明。

　　摩尔斯电码是一种早期的数码化通信形式，但是它不同于现代只使用0和1两种状态的二进制代码，它的代码包括五种：
　　1.点（.）
　　2.划（-）
　　3.每个字符间短的停顿（在点和划之间的停顿）
　　4.每个词之间中等的停顿
　　5.以及句子之间长的停顿

A-Z的Morse编码如下:

Morse code

2、算法

即将每个英文字母转化为对应的Morse码，在一个字母的内部、字母之间、单词之间都需要添加特定个数的空格。

3、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
	说明：
    1、根据英文字母a-z的Morse码表，对指定文段进行Morse编码，并计算编码总长度和平均码长；
    3、IDE为Dev C++ 5.4.1
*/
#include <iostream>
#include <string.h>
#include <fstream>
#include <stdlib.h>

using namespace std;

int main (void) {
	
	string str;
	string code_str;
	string MC[26];
	double total_len=0.0;
	double average_len=0.0;
	int i=0;

	//按行读取文件
	ifstream fin( "Morsecode.txt" );  
	while ( getline(fin, MC[i]) ) i++;
	fin.close(); 
	//输出morse码表 
	cout << "The MorseCode of a to z:\n"; 
	for(i=0; i<26; i++)
		cout << (char)('a'+i) << " : " << MC[i] << endl;
	//输出重定向并统计文段morse码总长度 
	i=0;
	freopen("test_without_punctuation.txt", "r", stdin);
	char c;
	while( scanf("%c", &c) != EOF) {
		str+=c;
		if(str[i] >= 'a' && str[i] <= 'z')
			total_len += MC[str[i]-'a'].length();
		//	cout << total_len << ' ' << i << endl;
		++i;
	}
	
	//输出 
	cout << "Total length of MorseCoding is: " << total_len << endl;
	average_len = total_len / i;
	cout << "Average length of MorseCoding is: " << average_len << endl; 
	return 0;
}

Reference:
[1].https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
[2].http://blog.csdn.net/qyee16/article/details/6664377
[3].https://zh.wikipedia.org/wiki/%E6%91%A9%E5%B0%94%E6%96%AF%E7%94%B5%E7%A0%81