Advertisement
selebry

gfghh

Jan 25th, 2023
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.00 KB | None | 0 0
  1. #pragma once
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <Windows.h>
  7. #include <fstream>
  8. using namespace std;
  9. struct Node {
  10. int offset;
  11. int length;
  12. char next;
  13. };
  14. struct newNode {
  15. int number;
  16. char next;
  17. };
  18. struct SF {
  19. char el;
  20. double numOfoccurrences;
  21. string code;
  22. };
  23. class ShannonFanoTree {
  24. public:
  25. string el;
  26. int weight;
  27. string code;
  28. ShannonFanoTree* left;
  29. ShannonFanoTree* right;
  30. void buildTree(ShannonFanoTree* root);
  31. int getWeight(string s, int i);
  32. ShannonFanoTree(string el, int weight) {
  33. this->el = el;
  34. this->weight = weight;
  35. }
  36. };
  37. class HuffmanTree {
  38. public:
  39. string el;
  40. double probability;
  41. string code;
  42. HuffmanTree* left;
  43. HuffmanTree* right;
  44. void buildTree(HuffmanTree* root);
  45. double getProbability(string el);
  46. HuffmanTree(string el, double probability) {
  47. this->el = el;
  48. this->probability = probability;
  49. }
  50. };
  51. vector <Node> list;
  52. vector <newNode> newList;
  53. vector <string> LZ78dictionary;
  54. vector <SF> ShannonFanoTable;
  55. vector <string> codes;
  56. void RLE(string s);
  57. string compress_check(string compressed);
  58. void LZ77(string s);
  59. void copy_check(string s, int wPos, Node& rec);
  60. void LZ78(string s);
  61. int findInDictionary(string el);
  62. void ShannonFano(string s);
  63. void isInTable(char el);
  64. void ShannonTableSort();
  65. int findWeight();
  66. int find(char el);
  67. void Huffman(string s);
  68. ------------------------hh
  69. #include "Header.h"
  70.  
  71. int main()
  72. {
  73. SetConsoleCP(1251);
  74. SetConsoleOutputCP(1251);
  75. string s;
  76. int ans = 100;
  77. while (ans != 0)
  78. {
  79. system("cls");
  80. cout << "Лабораторная работа №8 Резван Мурад ИКБО-11-21 Вариант 28" << endl << endl;
  81. cout << "Меню\n";
  82. cout << "1) Алгоритм сжатия RLE\n";
  83. cout << "2) Алгоритм сжатия LZ77\n";
  84. cout << "3) Алгоритм сжатия LZ78\n";
  85. cout << "4) Алгоритм сжатия Шеннона-Фано\n";
  86. cout << "5) Алгоритм сжатия Хаффмана\n";
  87. cout << "0) Выход\n";
  88. cout << "Ваш выбор: ";
  89. cin >> ans;
  90. system("cls");
  91. cout << "Лабораторная работа №8 Резван Мурад ИКБО-11-21 Вариант 28" << endl << endl;
  92. switch (ans)
  93. {
  94. case 1:
  95. {
  96. cout << "Введите строку, которую хотите сжать: \n";
  97. cin.ignore();
  98. getline(cin, s);
  99. cout << "Ваша строка:\n";
  100. RLE(s);
  101. system("pause");
  102. break;
  103. }
  104. case 2:
  105. {
  106. cout << "Введите строку, которую хотите сжать: \n";
  107. cin.ignore();
  108. getline(cin, s);
  109. cout << "Ваша строка:\n";
  110. LZ77(s);
  111. system("pause");
  112. break;
  113. }
  114. case 3:
  115. {
  116. cout << "Введите строку, которую хотите сжать: \n";
  117. cin.ignore();
  118. getline(cin, s);
  119. cout << "Ваша строка:\n";
  120. LZ78(s);
  121. system("pause");
  122. break;
  123. }
  124. case 4:
  125. {
  126. cout << "Введите строку, которую хотите сжать: \n";
  127.  
  128. cin.ignore();
  129. getline(cin, s);
  130. cout << "Ваша строка:\n";
  131. ShannonFano(s);
  132. system("pause");
  133. break;
  134. }
  135. case 5:
  136. {
  137. cout << "Введите строку, которую хотите сжать: \n";
  138. cin.ignore();
  139. getline(cin, s);
  140. cout << "Ваша строка:\n";
  141. Huffman(s);
  142. system("pause");
  143. break;
  144. }
  145. default:
  146. break;
  147. }
  148. }
  149. system("pause");
  150. return 0;
  151. }
  152. void RLE(string s) {
  153. string compressed = "";
  154. double compress_rate, beg_size, end_size;
  155. int repeat = 1;
  156. char current_symbol = NULL;
  157. string number_repeat = "";
  158. for (int i = 0; i < s.size(); i++) {
  159. if (current_symbol == NULL) {
  160. current_symbol = s[i];
  161. }
  162. else {
  163. if (current_symbol == s[i]) {
  164. repeat++;
  165. }
  166. else {
  167. number_repeat = to_string(repeat);
  168. compressed += number_repeat;
  169. repeat = 1;
  170. compressed += current_symbol;
  171. current_symbol = s[i];
  172. }
  173. }
  174. if (i == s.size() - 1) {
  175. number_repeat = to_string(repeat);
  176. compressed += number_repeat;
  177. compressed += current_symbol;
  178. }
  179. }
  180. compressed = compress_check(compressed);
  181. cout << compressed << '\n';
  182. beg_size = s.size();
  183. end_size = compressed.size();
  184. if (beg_size > end_size) {
  185. compress_rate = beg_size / end_size;
  186. cout << "Коэффициент сжатия: " << compress_rate << '\n';
  187. }
  188. else {
  189. compress_rate = end_size / beg_size;
  190. cout << "Строка увеличилась в " << compress_rate << " раз" << '\n';
  191. }
  192. }
  193. string compress_check(string compressed) {
  194. string new_comressed = "";
  195. int one_repeats = 0;
  196. string number_unic = "";
  197. for (int i = 0; i < compressed.size(); i += 2) {
  198. if (compressed[i] == '1') {
  199. one_repeats++;
  200. }
  201. if ((compressed[i] != '1') || (i == compressed.size() - 2)) {
  202. if (one_repeats > 0) {
  203. number_unic = to_string(one_repeats);
  204. new_comressed += '-';
  205. new_comressed += number_unic;
  206. for (int j = 1; j <= one_repeats; j++) {
  207. new_comressed += compressed[2 * j - 1];
  208. }
  209. one_repeats = 0;
  210. if (compressed[i] != '1') {
  211. i -= 2;
  212. }
  213. }
  214. else {
  215. new_comressed += compressed[i];
  216. new_comressed += compressed[i + 1];
  217. }
  218. }
  219. }
  220. return new_comressed;
  221. }
  222. void LZ77(string s) {
  223. Node rec;
  224. for (int i = 0; i < s.size(); i++) {
  225. copy_check(s, i, rec);
  226. if (rec.length == 0) {
  227. rec.next = s[i];
  228. }
  229. else {
  230. i += rec.length;
  231. if (i >= s.size()) {
  232. rec.next = '\0';
  233. }
  234. else {
  235. rec.next = s[i];
  236. }
  237. }
  238. list.push_back(rec);
  239. }
  240. double k;
  241. double endSize = 0;
  242. for (int i = 0; i < list.size(); i++) {
  243. cout << "<" << list[i].offset << ", " << list[i].length << ", " << list[i].next << ">, ";
  244. if (list[i].offset != 0)
  245. endSize += 3;
  246. else
  247. endSize++;
  248. }
  249. double begSize = s.size();
  250. k = begSize / endSize;
  251. cout << "\nКоэффициент сжатия: " << k << '\n';
  252. }
  253. void copy_check(string s, int wPos, Node& rec) {
  254. int lenght = 0, offset = 0;
  255. string dictionary = "";
  256. for (int i = 5; i > 0; i--) {
  257. if (wPos >= 5) {
  258. dictionary += s[wPos - i];
  259. }
  260. else if ((wPos < 5) && (wPos > 0)) {
  261. int pos = 0;
  262. while (true) {
  263. dictionary += s[pos];
  264. pos++;
  265. if (pos == wPos) {
  266. break;
  267. }
  268. }
  269. break;
  270. }
  271. }
  272. bool find = false;
  273. if (dictionary.size() == 0) {
  274. rec.offset = 0;
  275. rec.length = 0;
  276. }
  277. else {
  278. int i = 0;
  279. while (i < s.size()) {
  280. if (i >= dictionary.size()) break;
  281. if (dictionary[i] == s[wPos]) {
  282. offset = dictionary.size() - i;
  283. find = true;
  284. lenght++;
  285. while ((dictionary[i + lenght] == s[wPos + lenght]) && (i + lenght < dictionary.size())) {
  286. lenght++;
  287. }
  288. }
  289. if (find) break;
  290. i++;
  291. if ((!find) && (i == dictionary.size())) {
  292. break;
  293. }
  294. }
  295. if (i + lenght == dictionary.size()) {
  296. while (true) {
  297. if (wPos + i + lenght >= s.size()) break;
  298. if (s[wPos + lenght] == s[wPos + i + lenght]) {
  299. lenght++;
  300. }
  301. else break;
  302. }
  303. }
  304. }
  305. rec.length = lenght;
  306. rec.offset = offset;
  307. }
  308. void LZ78(string s) {
  309. newNode rec;
  310. string newRec = "";
  311. LZ78dictionary.push_back(newRec);
  312. for (int i = 0; i < s.size(); i++) {
  313. string newRec = "";
  314. newRec += s[i];
  315. if (findInDictionary(newRec) == -1) {
  316. rec.number = 0;
  317. rec.next = s[i];
  318. }
  319. while (findInDictionary(newRec) != -1) {
  320. rec.number = findInDictionary(newRec);
  321. if (i < s.size()) {
  322. i++;
  323. newRec += s[i];
  324. }
  325. else {
  326. rec.next = '\0';
  327. break;
  328. }
  329. }
  330. rec.next = newRec[newRec.size() - 1];
  331. LZ78dictionary.push_back(newRec);
  332. newList.push_back(rec);
  333. }
  334. LZ78dictionary.erase(LZ78dictionary.begin() + (LZ78dictionary.size() - 1));
  335. string compressed = "";
  336. for (int i = 0; i < newList.size(); i++) {
  337. cout << "(" << newList[i].number << ", " << newList[i].next << "), ";
  338. }
  339. cout << '\n';
  340. for (int i = 0; i < newList.size(); i++) {
  341. cout << newList[i].number << newList[i].next;
  342. compressed += newList[i].number;
  343. compressed += newList[i].next;
  344. }
  345. double k;
  346. double begSize = s.size();
  347. double endSize = compressed.size();
  348. k = begSize / endSize;
  349. cout << "\nКоэффициент сжатия: " << k << '\n';
  350. /*cout << "LZ78 Dictionary: \n";
  351. for (int i = 0; i < LZ78dictionary.size(); i++) {
  352. cout << LZ78dictionary[i] << '\n';
  353. }*/
  354. }
  355. int findInDictionary(string el) {
  356.  
  357. for (int i = 0; i < LZ78dictionary.size(); i++) {
  358. if (LZ78dictionary[i] == el) {
  359. return i;
  360. }
  361. }
  362. return -1;
  363. }
  364. void ShannonFano(string s) {
  365. for (int i = 0; i < s.size(); i++) {
  366. isInTable(s[i]);
  367. }
  368. ShannonTableSort();
  369. string allEl = "";
  370. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  371. allEl += ShannonFanoTable[i].el;
  372. }
  373. ShannonFanoTree tree = ShannonFanoTree(allEl, findWeight());
  374. tree.buildTree(&tree);
  375. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  376. cout << ShannonFanoTable[i].el << ": " << ShannonFanoTable[i].code << " -=-=- " << ShannonFanoTable[i].numOfoccurrences << '\n';
  377. }
  378. string compressed = "";
  379. for (int i = 0; i < s.size(); i++) {
  380. compressed += ShannonFanoTable[find(s[i])].code;
  381. }
  382. cout << compressed << '\n';
  383. double k;
  384. double begSize = s.size() * 8;
  385. double endSize = compressed.size();
  386. k = begSize / endSize;
  387. cout << "\nКоэффициент сжатия: " << k << '\n';
  388. }
  389. void isInTable(char el) {
  390. SF x;
  391. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  392. if (ShannonFanoTable[i].el == el) {
  393. ShannonFanoTable[i].numOfoccurrences++;
  394. return;
  395. }
  396. }
  397. x.el = el;
  398. x.numOfoccurrences = 1;
  399. ShannonFanoTable.push_back(x);
  400. }
  401. void ShannonTableSort() {
  402. int max = 0, newNum;
  403. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  404. for (int j = i; j < ShannonFanoTable.size(); j++) {
  405. if (ShannonFanoTable[j].numOfoccurrences > max) {
  406. max = ShannonFanoTable[j].numOfoccurrences;
  407. newNum = j;
  408. }
  409. }
  410. max = 0;
  411. swap(ShannonFanoTable[i], ShannonFanoTable[newNum]);
  412. }
  413. }
  414. int findWeight() {
  415. int weight = 0;
  416. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  417. weight += ShannonFanoTable[i].numOfoccurrences;
  418. }
  419. return weight;
  420. }
  421. void ShannonFanoTree::buildTree(ShannonFanoTree* root) {
  422. string leftList = "", rightList = root->el;
  423. if (root->el.size() > 1) {
  424. for (int i = 0; i < el.size(); i++) {
  425. leftList += root->el[i];
  426. rightList.erase(0, 1);
  427. if (getWeight(leftList, leftList.size() - 1) >= getWeight(rightList, rightList.size() - 1)) {
  428. root->left = new ShannonFanoTree(leftList, getWeight(leftList, leftList.size() - 1));
  429. root->right = new ShannonFanoTree(rightList, getWeight(rightList, rightList.size() - 1));
  430. root->left->code += root->code;
  431. root->right->code += root->code;
  432. root->left->code += '0';
  433. root->right->code += '1';
  434. buildTree(root->left);
  435. buildTree(root->right);
  436. break;
  437. }
  438. }
  439. }
  440. else {
  441. char c = root->el[0];
  442. ShannonFanoTable[find(c)].code = root->code;
  443. }
  444. }
  445. int find(char el) {
  446. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  447. if (el == ShannonFanoTable[i].el) {
  448. return i;
  449. }
  450. }
  451. }
  452. int ShannonFanoTree::getWeight(string s, int i) {
  453. int weight = 0;
  454. for (int j = 0; j <= i; j++) {
  455. for (int k = 0; k < ShannonFanoTable.size(); k++) {
  456. if (ShannonFanoTable[k].el == s[j]) {
  457. weight += ShannonFanoTable[k].numOfoccurrences;
  458. break;
  459. }
  460. }
  461. }
  462. return weight;
  463. }
  464. void Huffman(string s) {
  465. for (int i = 0; i < s.size(); i++) {
  466. isInTable(s[i]);
  467. }
  468. ShannonTableSort();
  469. string allEl = "";
  470. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  471. allEl += ShannonFanoTable[i].el;
  472. }
  473. HuffmanTree tree = HuffmanTree(allEl, 1);
  474. tree.buildTree(&tree);
  475. for (int i = 0; i < ShannonFanoTable.size(); i++) {
  476. cout << ShannonFanoTable[i].el << ": " << ShannonFanoTable[i].code << " -=-=- " << ShannonFanoTable[i].numOfoccurrences/26 << '\n';
  477. }
  478. string compressed = "";
  479. for (int i = 0; i < s.size(); i++) {
  480. compressed += ShannonFanoTable[find(s[i])].code;
  481. }
  482. cout << compressed << '\n';
  483. double k;
  484. double begSize = s.size() * 8;
  485. double endSize = compressed.size();
  486. k = begSize / endSize;
  487. cout << "\nКоэффициент сжатия: " << k << '\n';
  488. }
  489. void HuffmanTree::buildTree(HuffmanTree* root) {
  490. string leftList = "", rightList = root->el;
  491. if (root->el.size() > 1) {
  492. for (int i = 0; i < el.size(); i++) {
  493. leftList += root->el[i];
  494. rightList.erase(0, 1);
  495. if (getProbability(leftList) >= getProbability(rightList)) {
  496. root->left = new HuffmanTree(leftList, getProbability(leftList));
  497. root->right = new HuffmanTree(rightList, getProbability(rightList));
  498. root->left->code += root->code;
  499. root->right->code += root->code;
  500. root->left->code += '0';
  501. root->right->code += '1';
  502. buildTree(root->left);
  503. buildTree(root->right);
  504. break;
  505. }
  506. }
  507. }
  508. else {
  509. char c = root->el[0];
  510. ShannonFanoTable[find(c)].code = root->code;
  511. }
  512. }
  513. double HuffmanTree::getProbability(string el) {
  514. double probability = 0;
  515. for (int i = 0; i < el.size(); i++) {
  516. probability += (ShannonFanoTable[find(el[i])].numOfoccurrences);
  517. }
  518. return probability;
  519. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement