霍夫曼编码
英文名 Huffman Coding
中文名：霍夫曼、赫夫曼、哈夫曼
具体原理不重述，见百科
维基百科：http://zh.wikipedia.org/zh/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
百度百科：http://baike.baidu.com/view/189694.htm
几个点：
树节点的表示
霍夫曼树的建立
得到编码映射
编码
解码，根据霍夫曼树解码
演示 I
A 1 B 2 C 3 D 4 E 5
^Z
A 010
B 011
C 00
D 10
E 11
Encoding:
A
B
C
D
E
^Z
010011001011
Decoding:
010011001011
ABCDE
演示 II
asdf 23 asdfwoeri 232 ljljkl 2398 agslk;jfqwoeijasldfjals 988
^Z
agslk;jfqwoeijasldfjals 01
asdf 000
asdfwoeri 001
ljljkl 1
Encoding:
asdf
^Z
000
Decoding:
010000011111111
agslk;jfqwoeijasldfjalsasdfasdfwoeriljljklljljklljljklljljklljljklljljklljljkl
实现：
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 #include <vector>
5 #include <map>
6 using namespace std;
7
8 struct node
9 {
10 string trueform;
11 double probability;
12 string encoding;
13 node* left;
14 node* right;
15 node(string tt = "", double tp = 0.0, string te = "", node* tl = 0, node* tr = 0)
16 : trueform(tt), probability(tp), encoding(te), left(tl), right(tr) {}
17 friend bool operator < (const node& lhs, const node& rhs);
18 friend bool operator == (const node& lhs, const node& rhs);
19 };
20
21 bool operator < (const node& lhs, const node& rhs)
22 {
23 return lhs.probability < rhs.probability;
24 }
25
26 bool operator == (const node& lhs, const node& rhs)
27 {
28 return lhs.probability == rhs.probability;
29 }
30
31 void init(vector<node>& treenodes)
32 {
33 treenodes.clear();
34 string tt;
35 double tp;
36 while (cin >> tt >> tp)
37 {
38 treenodes.push_back(node(tt, tp));
39 }
40 sort(treenodes.begin(), treenodes.end());
41 }
42
43 void generateTree(node*& htree, vector<node>& treenodes)
44 {
45 while (treenodes.size() >= 2)
46 {
47 node* left = new node(treenodes[0]);
48 node* right = new node(treenodes[1]);
49 treenodes.erase(treenodes.begin(), treenodes.begin() + 2);
50 node temp("", left->probability + right->probability, "", left, right);
51 treenodes.push_back(temp);
52 sort(treenodes.begin(), treenodes.end());
53 }
54 htree = new node(treenodes[0]);
55 }
56
57 void generateCoding(map<string, string>& encodingmap, node* htree, string coding = "")
58 {
59 if (htree != 0)
60 {
61 if (htree->left != 0)
62 {
63 generateCoding(encodingmap, htree->left, coding + '0');
64 }
65 if (htree->right != 0)
66 {
67 generateCoding(encodingmap, htree->right, coding + '1');
68 }
69 if (htree->left == 0 && htree->right == 0)
70 {
71 encodingmap[htree->trueform] = coding;
72 htree->encoding = coding;
73 // codingnodes.push_back(node(htree->trueform, htree->probability, coding, htree->left, htree->right));
74 }
75 }
76 }
77
78 void inputCiphertext(string& ciphertext)
79 {
80 cin.clear();
81 cin >> ciphertext;
82 //for (string::size_type i = 0; i != ciphertext.size(); ++i)
83 //{
84 // if (ciphertext[i] != '0' && ciphertext[i] != '1')
85 // {
86 // cerr << "Ciphertext error!" << endl;
87 // exit(1);
88 // }
89 //}
90 }
91
92 string decodeCiphertext(string& result, const string& ciphertext, node* htree)
93 {
94 result.clear();
95 node* temp;
96 for (string::size_type i = 0; i != ciphertext.size();)
97 {
98 temp = htree;
99 while (temp->left != 0 && i != ciphertext.size())
100 {
101 if (ciphertext[i] == '0')
102 {
103 temp = temp->left;
104 }
105 else if (ciphertext[i] == '1')
106 {
107 temp = temp->right;
108 }
109 else
110 {
111 cerr << "Illegal character!" << endl;
112 exit(1);
113 }
114 ++i;
115 }
116 result += temp->trueform;
117 }
118
119 if (temp->left != 0)
120 {
121 cerr << "Ciphertext cannot be decoded!" << endl;
122 }
123 return result;
124 }
125
126 void inputPlaintext(vector<string>& plaintext)
127 {
128 cin.clear();
129 string temp;
130 while (cin >> temp)
131 {
132 plaintext.push_back(temp);
133 }
134 }
135
136 string encodePlaintext(string& result, const vector<string>& plaintext, map<string, string>& encodingmap)
137 {
138 result.clear();
139 for (vector<string>::const_iterator cit = plaintext.begin(); cit != plaintext.end(); ++cit)
140 {
141 if (encodingmap.find(*cit) != encodingmap.end())
142 {
143 // const map<string, string>& encodingmap
144 //result += encodingmap[*cit];
145 result += encodingmap[*cit];
146 }
147 else
148 {
149 cerr << "Cannot encode!" << endl;
150 }
151 }
152 return result;
153 }
154
155 int main()
156 {
157 vector<node> treenodes;
158 init(treenodes);
159 node* htree = 0;
160 generateTree(htree, treenodes);
161 //for (vector<node>::size_type i = 0; i != treenodes.size(); ++i)
162 //{
163 // cout << treenodes[i].trueform << '\t' << treenodes[i].probability << endl;
164 //}
165 map<string, string> encodingmap;
166 generateCoding(encodingmap, htree);
167 for (map<string, string>::const_iterator cit = encodingmap.begin(); cit != encodingmap.end(); ++cit)
168 {
169 cout << cit->first << '\t' << cit->second << endl;
170 }
171 cout << "Encoding:" << endl;
172 vector<string> plaintext;
173 inputPlaintext(plaintext);
174 string encoderesult;
175 encodePlaintext(encoderesult, plaintext, encodingmap);
176 cout << encoderesult << endl;
177
178 cout << "Decoding:" << endl;
179 string ciphertext;
180 inputCiphertext(ciphertext);
181 string result;
182 decodeCiphertext(result, ciphertext, htree);
183 cout << result << endl;
184 }
posted on 2011-09-09 20:39
unixfy 阅读(594)
评论(0) 编辑 收藏 引用