fork(25) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6.  
  7. struct ltcode
  8. {
  9. 	unsigned long long frequency;
  10. 	unsigned char letter;
  11. 	string code = "";
  12. };
  13.  
  14. void zeroset(ltcode *c)
  15. {
  16. 	for (unsigned int i = 0; i < 256; ++i)
  17. 	{
  18. 		c[i].frequency = 0;
  19. 		c[i].letter = i;
  20. 	}
  21. }
  22.  
  23. bool f(ltcode x, ltcode y)
  24. {
  25. 	if (x.frequency != y.frequency) return x.frequency > y.frequency;
  26. 	else return x.letter > y.letter;
  27. }
  28.  
  29. struct B
  30. {
  31. 	string list;
  32. 	int i;
  33.  
  34. 	int left;
  35. 	int right;
  36.  
  37. 	string code = "";
  38.  
  39. 	B()
  40. 	{
  41. 		list = "";
  42. 		i = 0;
  43. 	}
  44. };
  45.  
  46. void print_binary_tree(int num, vector <B> &tree)
  47. {
  48. 	if (tree[num].list.size() > 1)
  49. 	{
  50. 		cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
  51. 		cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
  52. 		print_binary_tree(tree[num].left, tree);
  53. 		print_binary_tree(tree[num].right, tree);
  54. 	}
  55. }
  56.  
  57. void print_tree_graph(vector <B> &tree)
  58. {
  59. 	cout << "digraph G {\n";
  60. 	print_binary_tree(tree.size()-1, tree);
  61. 	cout << "}\n";
  62. }
  63.  
  64. void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
  65. {
  66. 	tree[num].code = code;
  67. 	if (tree[num].list.size() > 1)
  68. 	{
  69. 		huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
  70. 		huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
  71. 	}
  72. 	else
  73. 	{
  74. 		for (int j = 0; ; ++j)
  75. 		{
  76. 			if (letter_codes[j].letter == tree[num].list[0])
  77. 			{
  78. 				letter_codes[j].code = code;
  79. 				break;
  80. 			}
  81. 		}
  82. 	}
  83. }
  84.  
  85. void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
  86. {
  87. 	huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
  88. }
  89.  
  90. int main() {
  91. 	unsigned char c;
  92. 	string S;
  93. 	ltcode count[256], stringlinks[256];
  94. 	zeroset(count);
  95.  
  96. 	while (scanf("%c", &c))
  97. 	{
  98. 		if (c == '\n') break;
  99. 		S += c;
  100. 		++count[c].frequency;
  101. 	}
  102. 	sort(count, count+256, f);
  103.  
  104. 	vector <B> tree;
  105. 	B tmp;
  106. 	tmp.list = "0";
  107. 	int j = 0, letter_amount;
  108. 	for (j = 0; (count[j].frequency); ++j)
  109. 	{
  110. 		tmp.i = count[j].frequency;
  111. 		tmp.list[0] = count[j].letter;
  112. 		tree.push_back(tmp);
  113. 	}
  114. 	int maxsize = j-1, size;
  115.  
  116. 	sort(tree.begin(), tree.end(), [] (B a, B b)
  117. 	{
  118. 		if (a.i != b.i) return (a.i < b.i);
  119. 		else return (a.list.size() < b.list.size());
  120. 	});
  121.  
  122. 	for (j = 0; size < maxsize;)
  123. 	{
  124. 		tmp.list = tree[j].list + tree[j+1].list;
  125. 		tmp.i = tree[j].i + tree[j+1].i;
  126. 		tmp.left = j;
  127. 		tmp.right = j+1;
  128.  
  129. 		size = tmp.list.size();
  130.  
  131. 		tree.push_back(tmp);
  132. 		j += 2;
  133. 		sort(tree.begin()+j, tree.end(), [] (B a, B b)
  134. 		{
  135. 			if (a.i != b.i) return (a.i < b.i);
  136. 			else return (a.list.size() < b.list.size());
  137. 		}
  138. 		);
  139. 	}
  140. 	huffman_encoding(tree, count);
  141. 	print_tree_graph(tree);
  142. 	cout << "\nCodes of letters:\n";
  143. 	for (j = 0; (count[j].frequency); ++j)
  144. 	{
  145. 		cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
  146. 		stringlinks[count[j].letter].code = count[j].code;
  147. 	}
  148. 	cout << "\n\nEncoded string:\n";
  149. 	for (unsigned int i = 0; i < S.size(); ++i)
  150. 	{
  151. 		cout << stringlinks[S[i]].code;
  152. 	}
  153. 	cout << '\n';
  154. 	return 0;
  155. }
Success #stdin #stdout 0s 16112KB
comments (?)
stdin
copy 
MOLOKO KIPIT
stdout
copy 
digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01)  'K'(101)  'I'(110)  'T'(1110)  'P'(1111)  'M'(000)  'L'(001)  ' '(100)  

Encoded string:
00001001011010110010111011111101110
https://ideone.com/G50aSn
Huffman's Coding. F
language:
C++14 (gcc 8.3)
created:
7 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!