fork download 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <map>
  4. #include <vector>
  5. #include <climits>
  6. using namespace std;
  7. struct Node{
  8. 	int x;
  9. 	Node* l;
  10. 	Node* r;
  11. 	Node(int X=0, Node* L=NULL, Node* R=NULL) : x(X), l(L), r(R) {}
  12. };
  13. Node* huffman_tree(const string &s){
  14. 	if(!s.size())	return NULL;
  15. 	unordered_map<char,int> h;
  16. 	for(char c: s)
  17. 		h[c]++;
  18. 	multimap<int, Node*> v;
  19. 	for(auto p: h)
  20. 		v.insert({p.second, new Node(p.first)});
  21. 	pair<int,Node*> p = *v.begin();
  22. 	v.erase(v.begin());
  23. 	while(!v.empty()){
  24. 		auto it = v.begin();
  25. 		v.insert({p.first+it->first, new Node(p.first+it->first,p.second,it->second)});
  26. 		v.erase(it);
  27. 		it = v.begin();
  28. 		p = *it;
  29. 		v.erase(it);
  30. 	}
  31. 	return p.second;
  32. }
  33. void huffman_helper(unordered_map<char,vector<bool>> &t, Node* node, vector<bool> v){
  34. 	if(!(node->l||node->r)){
  35. 		t[node->x] = v;
  36. 		return;
  37. 	}
  38. 	v.push_back(false);
  39. 	huffman_helper(t,node->l,v);
  40. 	v.back() = true;
  41. 	huffman_helper(t,node->r,v);
  42. }
  43. unordered_map<char,vector<bool>> huffman_table(Node* h){
  44. 	unordered_map<char,vector<bool>> t;
  45. 	if(!h)	return t;
  46. 	huffman_helper(t,h,vector<bool>());
  47. 	return t;
  48. }
  49. void print(char c){
  50. 	if(c=='\s')	cout<<"\\s";
  51. 	else if(c=='\t')	cout<<"\\t";
  52. 	else if(c=='\n')	cout<<"\\n";
  53. 	else cout<<c;
  54. }
  55. void print_binary_tree(Node* node, int depth=0, bool leaf_check=false){
  56. 	// this will print a leaf node differently if the leaf_check is set to true
  57. 	// print format for leaf can be defined in else block below.
  58. 	if(!node)	return;
  59. 	print_binary_tree(node->r, depth+1, leaf_check);
  60. 	string str = "";
  61. 	for(int i=0; i<depth; i++)
  62. 		cout<<"|\t";
  63. 	if(!leaf_check||node->l||node->r)	cout<<node->x;
  64. 	else	print(node->x);	// print in this format if it's a leaf
  65. 	cout<<endl;
  66. 	print_binary_tree(node->l, depth+1, leaf_check);
  67. 	return;
  68. }
  69. void print(const vector<bool> &v){
  70. 	for(const auto &x: v)
  71. 		cout<<x;
  72. 	cout<<endl;
  73. }
  74. vector<bool> encode(const string &s, unordered_map<char,vector<bool>> &t){
  75. 	vector<bool> v;
  76. 	for(char c: s)
  77. 		for(bool b: t[c])
  78. 			v.push_back(b);
  79. 	return v;
  80. }
  81. string decode(const vector<bool> &v, Node* h){
  82. 	string s = "";
  83. 	Node* node = h;
  84. 	for(bool b: v){
  85. 		node = b?node->r:node->l;
  86. 		if(!(node->l||node->r)){
  87. 			s.push_back(char(node->x));
  88. 			node = h;
  89. 		}
  90. 	}
  91. 	return s;
  92. }
  93. int main() {
  94. 	// CAUTION: this method is an exception for the case 
  95. 	// when all text contains just one unique character.
  96. 	// E.g. ccccccccccccccccccccccccccccccc, without any whitespace etc.
  97. 	string s;
  98. 	string p="";
  99. 	while(getline(cin,s))
  100. 		p += s + "\n";
  101. 	Node* h = huffman_tree(p);
  102. 	print_binary_tree(h,0,true);
  103. 	cout<<endl<<endl;
  104. 	unordered_map<char,vector<bool>> t = huffman_table(h);
  105. 	int sum = 0;
  106. 	for(auto p: t){
  107. 		print(p.first);
  108. 		cout<<'\t';
  109. 		print(p.second);
  110. 		sum += p.second.size();
  111. 	}
  112. 	cout<<endl;
  113. 	cout<<"Size of text: text_length*char_size = ";
  114. 	cout<<p.size()<<" * "<<sizeof(char)*CHAR_BIT<<" = ";
  115. 	cout<<p.size()*sizeof(char)*CHAR_BIT<<endl;
  116. 	cout<<"Size of table: uniq_chars*(char_size + avg_encoding_size) = ";
  117. 	cout<<t.size()<<" * ("<<sizeof(char)*CHAR_BIT<<" + "<<sum<<"/"<<t.size()<<") = ";
  118. 	cout<<t.size()*sizeof(char)*CHAR_BIT+sum<<endl;
  119. 	vector<bool> v = encode(p,t);
  120. 	cout<<"Size of encoded string: "<<v.size()<<endl;
  121. 	print(v);
  122. 	cout<<endl;
  123. 	string text = decode(v,h);
  124. 	cout<<"Check if the original text and decoded text matches? ";
  125. 	cout<<(p==text?"Yes.":"No.")<<endl;
  126. 	cout<<endl<<text<<endl;
  127. 	return 0;
  128. }
Success #stdin #stdout 0s 4252KB
comments ()
stdin 
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time linear to the number of input weights if these weights are sorted. However, although optimal among methods encoding symbols separately, Huffman coding is not always optimal among all compression methods - it is replaced with arithmetic coding or asymmetric numeral systems if better compression ratio is required.
stdout 
|	|	|	|	|	r
|	|	|	|	109
|	|	|	|	|	|	|	|	H
|	|	|	|	|	|	|	14
|	|	|	|	|	|	|	|	,
|	|	|	|	|	|	27
|	|	|	|	|	|	|	|	v
|	|	|	|	|	|	|	13
|	|	|	|	|	|	|	|	|	\n
|	|	|	|	|	|	|	|	6
|	|	|	|	|	|	|	|	|	A
|	|	|	|	|	52
|	|	|	|	|	|	p
|	|	|	202
|	|	|	|	|	m
|	|	|	|	93
|	|	|	|	|	c
|	|	393
|	|	|	 
|	707
|	|	|	|	o
|	|	|	163
|	|	|	|	|	|	g
|	|	|	|	|	41
|	|	|	|	|	|	|	|	|	M
|	|	|	|	|	|	|	|	6
|	|	|	|	|	|	|	|	|	-
|	|	|	|	|	|	|	10
|	|	|	|	|	|	|	|	|	|	5
|	|	|	|	|	|	|	|	|	2
|	|	|	|	|	|	|	|	|	|	x
|	|	|	|	|	|	|	|	4
|	|	|	|	|	|	|	|	|	|	2
|	|	|	|	|	|	|	|	|	2
|	|	|	|	|	|	|	|	|	|	S
|	|	|	|	|	|	20
|	|	|	|	|	|	|	w
|	|	|	|	80
|	|	|	|	|	|	y
|	|	|	|	|	39
|	|	|	|	|	|	b
|	|	314
|	|	|	|	|	l
|	|	|	|	78
|	|	|	|	|	d
|	|	|	151
|	|	|	|	|	h
|	|	|	|	73
|	|	|	|	|	f
1214
|	|	|	|	i
|	|	|	137
|	|	|	|	a
|	|	270
|	|	|	|	\s
|	|	|	133
|	|	|	|	t
|	507
|	|	|	|	|	|	|	.
|	|	|	|	|	|	18
|	|	|	|	|	|	|	|	|	|	1
|	|	|	|	|	|	|	|	|	2
|	|	|	|	|	|	|	|	|	|	R
|	|	|	|	|	|	|	|	4
|	|	|	|	|	|	|	|	|	I
|	|	|	|	|	|	|	8
|	|	|	|	|	|	|	|	|	D
|	|	|	|	|	|	|	|	4
|	|	|	|	|	|	|	|	|	C
|	|	|	|	|	33
|	|	|	|	|	|	|	|	|	"
|	|	|	|	|	|	|	|	4
|	|	|	|	|	|	|	|	|	'
|	|	|	|	|	|	|	8
|	|	|	|	|	|	|	|	|	(
|	|	|	|	|	|	|	|	4
|	|	|	|	|	|	|	|	|	)
|	|	|	|	|	|	15
|	|	|	|	|	|	|	|	T
|	|	|	|	|	|	|	7
|	|	|	|	|	|	|	|	|	q
|	|	|	|	|	|	|	|	3
|	|	|	|	|	|	|	|	|	9
|	|	|	|	63
|	|	|	|	|	u
|	|	|	126
|	|	|	|	n
|	|	237
|	|	|	e


,	11110110
v	11110101
A	111101000
p	111100
m	11101
c	11100
 	110
o	1011
g	101011
M	101010111
-	101010110
S	1010101000
H	11110111
w	1010100
y	101001
b	101000
l	10011
r	11111
C	001111000
q	001110001
"	001110111
'	001110110
)	001110100
n	0010
(	001110101
T	00111001
u	00110
e	000
x	1010101010
I	001111010
R	0011110110
i	0111
1	0011110111
.	0011111
D	001111001
\s	0101
t	0100
2	1010101001
a	0110
f	10000
\n	111101001
9	001110000
h	10001
5	1010101011
d	10010

Size of text: text_length*char_size = 1214 * 8 = 9712
Size of table: uniq_chars*(char_size + avg_encoding_size) = 45 * (8 + 317/45) = 677
Size of encoded string: 5396
00111101000101101110010111110111110000110010000011111110010111100011100000101110000011001100010100101100111001010000101111111111010110010001111011001011001001000100010111111110100111110110110011011011110111001101000010000111010110001011011100101110010000110011101011100110110111100011011111010001111110000110100110110111111100100101001111100000110101110000110101111110001000111111010110100111101111001111100010000011110101010101101110010111001000011001001000101100100110011101011101110010111110111101101100101001110100111000110010100010010110100001011111111101001110110101010110011000010101011101001001100100011011011100101111101111100111110000101010101111011001000111111100011100110001000110111100111111011111000000101010111010111000011010000011100101001001110010101011110101111111110001100101011100101010111100101001101110010001110011011011100101110010000110111100111111011111000000001001001011101010001010011101110100001100010010111010111000011011110111001101000010000111010110001011011100101110010011100101010111111011011001100010110011010011101011101111111011101001000111101110100100001111010100010011101111110000010010110101000101001110001111001011011110101011110010110111101000001111111011110111001101000010000111010110001011010101001000101111001100011010001000110101010001100101110011011010101010001110000111110011110010011111110010101000011010010000001001001100110010011010101011100111101000111001111101101100110001010010110111100001101010001001101110101100010001001011001110010110010010001000110001111011100111000010101010111010101001110111100011011110000011111110001110111111101000110101010111000010010001101110010110100001011111111100100100010001100011110001011001001010100111110011011100010001111011001011010111000011010101011101110010011111101001101110110101011000111101100001001000110001010010011000101110010100111000111100010111001000001010011101110011111111101001111101001001110011000100011010110011001001111000011001001101000011111101111101110111101110011010000100001110101100010001110110010111001101001110101110111111101110100100011110111011100011000101101010000001101111010101110001010100000100101100110010111001101101111010101101111101110110101000100110001010101101001100000101010110100100011101110010111001000011001000110101000100110001101000010111111111000000101110010111001001110010101011110011011001011011001101111111100000110010110100111101101000101110011110001110101010100110111001000111001100101110011011011100100010110111110110111000100000111111100111001011001101101000001111001100000111010000111111100011100110001000110011010011101011101111111011101001000111101110100100001111101111111010100001011100100100010111010111001000110101000100110001101000011111101111101110010010001000110000010101000111111010110010000010010110111100111111011101000011010100001111001101110100101001110101111111110100001111100000111000100110000001011100101001110101110000110101111100111000011011111111110000010111000001100011101011010100000011110101110001010000111010011010000101111111110000011011100100011101111001011010101010111101000100110001101111010101101001100110000110101110000110010010001000110010110110011011111111000001100101101001111011010001011100110011111110111101000010111001110010110101101001000100011111110000001001001111110111111001010011100000010111001011100100111001010101111011101000010010001101110010010111110110110111011011111110001101110010111110111101101100101100101101001111011010001011100110101110011011111000110101011000001000011111011010011100111010011101111100011110011111000010100000100100000100101100011001010111001010101111010000000101010000011111110101000011101000101110010010001011000101101001100001010101110111001011111011110110110010110010110100111101101000101110011010100111111101111011100110100001000011101011000100011101100101110111010000100100011011100101101110001100010110101000000110000100001000001111110001110000010010010011101001110011111101111100100110001110100000100100000100101111011011010000011100101001001110010101011110011011011100101110010000110011100101100100011111101000110100110111001000001101111111001001011110010010001000110001000110111011010000001111111010111000011001110010111100001100100110101010000001111010111000101000101110011110000110010010001000010100011010101000000111101011100010100010111001101111100011001011011111110100000100100011111110111101111011101010000011110101000111111111011011001101001101001000110110011010101110001110101111110001000111111010110100111100110111011011001010101111011101000010010001101110010010111000000101110010111001001110010101011110010110100111101101000101110011010111001010001111000110111110110010000010011101001111101101101111011100110100001000011101011000101101110010111001001110010101011110011101011100010101101001100110100111010100011010100101011101011111100010001111110101101001111001101110110110010101011110011010011100111101110010111110111110011111000010101010111101100101101110100001001000110111001001011101010101101100111010011001110101110111110001111001001101101110000010010110101010001110100100011100110111110111010010001111010000100011111100110111001011100100111001010101111010111111111001100101101001111011110100001001111101111110011000100011011101000111110110100111100101101001010101000001110101011100111100001101010000000100010000011111110111001011111011111001111100001010101011110110010110111110110010001111011110011101011101111100000111000100110011111111000100100011111111101001

Check if the original text and decoded text matches? Yes.

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time linear to the number of input weights if these weights are sorted. However, although optimal among methods encoding symbols separately, Huffman coding is not always optimal among all compression methods - it is replaced with arithmetic coding or asymmetric numeral systems if better compression ratio is required.
https://ideone.com/7BBdMz
Huffman Coding
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!