Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma once
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <Windows.h>
- #include <fstream>
- using namespace std;
- struct Node {
- int offset;
- int length;
- char next;
- };
- struct newNode {
- int number;
- char next;
- };
- struct SF {
- char el;
- double numOfoccurrences;
- string code;
- };
- class ShannonFanoTree {
- public:
- string el;
- int weight;
- string code;
- ShannonFanoTree* left;
- ShannonFanoTree* right;
- void buildTree(ShannonFanoTree* root);
- int getWeight(string s, int i);
- ShannonFanoTree(string el, int weight) {
- this->el = el;
- this->weight = weight;
- }
- };
- class HuffmanTree {
- public:
- string el;
- double probability;
- string code;
- HuffmanTree* left;
- HuffmanTree* right;
- void buildTree(HuffmanTree* root);
- double getProbability(string el);
- HuffmanTree(string el, double probability) {
- this->el = el;
- this->probability = probability;
- }
- };
- vector <Node> list;
- vector <newNode> newList;
- vector <string> LZ78dictionary;
- vector <SF> ShannonFanoTable;
- vector <string> codes;
- void RLE(string s);
- string compress_check(string compressed);
- void LZ77(string s);
- void copy_check(string s, int wPos, Node& rec);
- void LZ78(string s);
- int findInDictionary(string el);
- void ShannonFano(string s);
- void isInTable(char el);
- void ShannonTableSort();
- int findWeight();
- int find(char el);
- void Huffman(string s);
- ------------------------hh
- #include "Header.h"
- int main()
- {
- SetConsoleCP(1251);
- SetConsoleOutputCP(1251);
- string s;
- int ans = 100;
- while (ans != 0)
- {
- system("cls");
- cout << "Лабораторная работа №8 Резван Мурад ИКБО-11-21 Вариант 28" << endl << endl;
- cout << "Меню\n";
- cout << "1) Алгоритм сжатия RLE\n";
- cout << "2) Алгоритм сжатия LZ77\n";
- cout << "3) Алгоритм сжатия LZ78\n";
- cout << "4) Алгоритм сжатия Шеннона-Фано\n";
- cout << "5) Алгоритм сжатия Хаффмана\n";
- cout << "0) Выход\n";
- cout << "Ваш выбор: ";
- cin >> ans;
- system("cls");
- cout << "Лабораторная работа №8 Резван Мурад ИКБО-11-21 Вариант 28" << endl << endl;
- switch (ans)
- {
- case 1:
- {
- cout << "Введите строку, которую хотите сжать: \n";
- cin.ignore();
- getline(cin, s);
- cout << "Ваша строка:\n";
- RLE(s);
- system("pause");
- break;
- }
- case 2:
- {
- cout << "Введите строку, которую хотите сжать: \n";
- cin.ignore();
- getline(cin, s);
- cout << "Ваша строка:\n";
- LZ77(s);
- system("pause");
- break;
- }
- case 3:
- {
- cout << "Введите строку, которую хотите сжать: \n";
- cin.ignore();
- getline(cin, s);
- cout << "Ваша строка:\n";
- LZ78(s);
- system("pause");
- break;
- }
- case 4:
- {
- cout << "Введите строку, которую хотите сжать: \n";
- cin.ignore();
- getline(cin, s);
- cout << "Ваша строка:\n";
- ShannonFano(s);
- system("pause");
- break;
- }
- case 5:
- {
- cout << "Введите строку, которую хотите сжать: \n";
- cin.ignore();
- getline(cin, s);
- cout << "Ваша строка:\n";
- Huffman(s);
- system("pause");
- break;
- }
- default:
- break;
- }
- }
- system("pause");
- return 0;
- }
- void RLE(string s) {
- string compressed = "";
- double compress_rate, beg_size, end_size;
- int repeat = 1;
- char current_symbol = NULL;
- string number_repeat = "";
- for (int i = 0; i < s.size(); i++) {
- if (current_symbol == NULL) {
- current_symbol = s[i];
- }
- else {
- if (current_symbol == s[i]) {
- repeat++;
- }
- else {
- number_repeat = to_string(repeat);
- compressed += number_repeat;
- repeat = 1;
- compressed += current_symbol;
- current_symbol = s[i];
- }
- }
- if (i == s.size() - 1) {
- number_repeat = to_string(repeat);
- compressed += number_repeat;
- compressed += current_symbol;
- }
- }
- compressed = compress_check(compressed);
- cout << compressed << '\n';
- beg_size = s.size();
- end_size = compressed.size();
- if (beg_size > end_size) {
- compress_rate = beg_size / end_size;
- cout << "Коэффициент сжатия: " << compress_rate << '\n';
- }
- else {
- compress_rate = end_size / beg_size;
- cout << "Строка увеличилась в " << compress_rate << " раз" << '\n';
- }
- }
- string compress_check(string compressed) {
- string new_comressed = "";
- int one_repeats = 0;
- string number_unic = "";
- for (int i = 0; i < compressed.size(); i += 2) {
- if (compressed[i] == '1') {
- one_repeats++;
- }
- if ((compressed[i] != '1') || (i == compressed.size() - 2)) {
- if (one_repeats > 0) {
- number_unic = to_string(one_repeats);
- new_comressed += '-';
- new_comressed += number_unic;
- for (int j = 1; j <= one_repeats; j++) {
- new_comressed += compressed[2 * j - 1];
- }
- one_repeats = 0;
- if (compressed[i] != '1') {
- i -= 2;
- }
- }
- else {
- new_comressed += compressed[i];
- new_comressed += compressed[i + 1];
- }
- }
- }
- return new_comressed;
- }
- void LZ77(string s) {
- Node rec;
- for (int i = 0; i < s.size(); i++) {
- copy_check(s, i, rec);
- if (rec.length == 0) {
- rec.next = s[i];
- }
- else {
- i += rec.length;
- if (i >= s.size()) {
- rec.next = '\0';
- }
- else {
- rec.next = s[i];
- }
- }
- list.push_back(rec);
- }
- double k;
- double endSize = 0;
- for (int i = 0; i < list.size(); i++) {
- cout << "<" << list[i].offset << ", " << list[i].length << ", " << list[i].next << ">, ";
- if (list[i].offset != 0)
- endSize += 3;
- else
- endSize++;
- }
- double begSize = s.size();
- k = begSize / endSize;
- cout << "\nКоэффициент сжатия: " << k << '\n';
- }
- void copy_check(string s, int wPos, Node& rec) {
- int lenght = 0, offset = 0;
- string dictionary = "";
- for (int i = 5; i > 0; i--) {
- if (wPos >= 5) {
- dictionary += s[wPos - i];
- }
- else if ((wPos < 5) && (wPos > 0)) {
- int pos = 0;
- while (true) {
- dictionary += s[pos];
- pos++;
- if (pos == wPos) {
- break;
- }
- }
- break;
- }
- }
- bool find = false;
- if (dictionary.size() == 0) {
- rec.offset = 0;
- rec.length = 0;
- }
- else {
- int i = 0;
- while (i < s.size()) {
- if (i >= dictionary.size()) break;
- if (dictionary[i] == s[wPos]) {
- offset = dictionary.size() - i;
- find = true;
- lenght++;
- while ((dictionary[i + lenght] == s[wPos + lenght]) && (i + lenght < dictionary.size())) {
- lenght++;
- }
- }
- if (find) break;
- i++;
- if ((!find) && (i == dictionary.size())) {
- break;
- }
- }
- if (i + lenght == dictionary.size()) {
- while (true) {
- if (wPos + i + lenght >= s.size()) break;
- if (s[wPos + lenght] == s[wPos + i + lenght]) {
- lenght++;
- }
- else break;
- }
- }
- }
- rec.length = lenght;
- rec.offset = offset;
- }
- void LZ78(string s) {
- newNode rec;
- string newRec = "";
- LZ78dictionary.push_back(newRec);
- for (int i = 0; i < s.size(); i++) {
- string newRec = "";
- newRec += s[i];
- if (findInDictionary(newRec) == -1) {
- rec.number = 0;
- rec.next = s[i];
- }
- while (findInDictionary(newRec) != -1) {
- rec.number = findInDictionary(newRec);
- if (i < s.size()) {
- i++;
- newRec += s[i];
- }
- else {
- rec.next = '\0';
- break;
- }
- }
- rec.next = newRec[newRec.size() - 1];
- LZ78dictionary.push_back(newRec);
- newList.push_back(rec);
- }
- LZ78dictionary.erase(LZ78dictionary.begin() + (LZ78dictionary.size() - 1));
- string compressed = "";
- for (int i = 0; i < newList.size(); i++) {
- cout << "(" << newList[i].number << ", " << newList[i].next << "), ";
- }
- cout << '\n';
- for (int i = 0; i < newList.size(); i++) {
- cout << newList[i].number << newList[i].next;
- compressed += newList[i].number;
- compressed += newList[i].next;
- }
- double k;
- double begSize = s.size();
- double endSize = compressed.size();
- k = begSize / endSize;
- cout << "\nКоэффициент сжатия: " << k << '\n';
- /*cout << "LZ78 Dictionary: \n";
- for (int i = 0; i < LZ78dictionary.size(); i++) {
- cout << LZ78dictionary[i] << '\n';
- }*/
- }
- int findInDictionary(string el) {
- for (int i = 0; i < LZ78dictionary.size(); i++) {
- if (LZ78dictionary[i] == el) {
- return i;
- }
- }
- return -1;
- }
- void ShannonFano(string s) {
- for (int i = 0; i < s.size(); i++) {
- isInTable(s[i]);
- }
- ShannonTableSort();
- string allEl = "";
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- allEl += ShannonFanoTable[i].el;
- }
- ShannonFanoTree tree = ShannonFanoTree(allEl, findWeight());
- tree.buildTree(&tree);
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- cout << ShannonFanoTable[i].el << ": " << ShannonFanoTable[i].code << " -=-=- " << ShannonFanoTable[i].numOfoccurrences << '\n';
- }
- string compressed = "";
- for (int i = 0; i < s.size(); i++) {
- compressed += ShannonFanoTable[find(s[i])].code;
- }
- cout << compressed << '\n';
- double k;
- double begSize = s.size() * 8;
- double endSize = compressed.size();
- k = begSize / endSize;
- cout << "\nКоэффициент сжатия: " << k << '\n';
- }
- void isInTable(char el) {
- SF x;
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- if (ShannonFanoTable[i].el == el) {
- ShannonFanoTable[i].numOfoccurrences++;
- return;
- }
- }
- x.el = el;
- x.numOfoccurrences = 1;
- ShannonFanoTable.push_back(x);
- }
- void ShannonTableSort() {
- int max = 0, newNum;
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- for (int j = i; j < ShannonFanoTable.size(); j++) {
- if (ShannonFanoTable[j].numOfoccurrences > max) {
- max = ShannonFanoTable[j].numOfoccurrences;
- newNum = j;
- }
- }
- max = 0;
- swap(ShannonFanoTable[i], ShannonFanoTable[newNum]);
- }
- }
- int findWeight() {
- int weight = 0;
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- weight += ShannonFanoTable[i].numOfoccurrences;
- }
- return weight;
- }
- void ShannonFanoTree::buildTree(ShannonFanoTree* root) {
- string leftList = "", rightList = root->el;
- if (root->el.size() > 1) {
- for (int i = 0; i < el.size(); i++) {
- leftList += root->el[i];
- rightList.erase(0, 1);
- if (getWeight(leftList, leftList.size() - 1) >= getWeight(rightList, rightList.size() - 1)) {
- root->left = new ShannonFanoTree(leftList, getWeight(leftList, leftList.size() - 1));
- root->right = new ShannonFanoTree(rightList, getWeight(rightList, rightList.size() - 1));
- root->left->code += root->code;
- root->right->code += root->code;
- root->left->code += '0';
- root->right->code += '1';
- buildTree(root->left);
- buildTree(root->right);
- break;
- }
- }
- }
- else {
- char c = root->el[0];
- ShannonFanoTable[find(c)].code = root->code;
- }
- }
- int find(char el) {
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- if (el == ShannonFanoTable[i].el) {
- return i;
- }
- }
- }
- int ShannonFanoTree::getWeight(string s, int i) {
- int weight = 0;
- for (int j = 0; j <= i; j++) {
- for (int k = 0; k < ShannonFanoTable.size(); k++) {
- if (ShannonFanoTable[k].el == s[j]) {
- weight += ShannonFanoTable[k].numOfoccurrences;
- break;
- }
- }
- }
- return weight;
- }
- void Huffman(string s) {
- for (int i = 0; i < s.size(); i++) {
- isInTable(s[i]);
- }
- ShannonTableSort();
- string allEl = "";
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- allEl += ShannonFanoTable[i].el;
- }
- HuffmanTree tree = HuffmanTree(allEl, 1);
- tree.buildTree(&tree);
- for (int i = 0; i < ShannonFanoTable.size(); i++) {
- cout << ShannonFanoTable[i].el << ": " << ShannonFanoTable[i].code << " -=-=- " << ShannonFanoTable[i].numOfoccurrences/26 << '\n';
- }
- string compressed = "";
- for (int i = 0; i < s.size(); i++) {
- compressed += ShannonFanoTable[find(s[i])].code;
- }
- cout << compressed << '\n';
- double k;
- double begSize = s.size() * 8;
- double endSize = compressed.size();
- k = begSize / endSize;
- cout << "\nКоэффициент сжатия: " << k << '\n';
- }
- void HuffmanTree::buildTree(HuffmanTree* root) {
- string leftList = "", rightList = root->el;
- if (root->el.size() > 1) {
- for (int i = 0; i < el.size(); i++) {
- leftList += root->el[i];
- rightList.erase(0, 1);
- if (getProbability(leftList) >= getProbability(rightList)) {
- root->left = new HuffmanTree(leftList, getProbability(leftList));
- root->right = new HuffmanTree(rightList, getProbability(rightList));
- root->left->code += root->code;
- root->right->code += root->code;
- root->left->code += '0';
- root->right->code += '1';
- buildTree(root->left);
- buildTree(root->right);
- break;
- }
- }
- }
- else {
- char c = root->el[0];
- ShannonFanoTable[find(c)].code = root->code;
- }
- }
- double HuffmanTree::getProbability(string el) {
- double probability = 0;
- for (int i = 0; i < el.size(); i++) {
- probability += (ShannonFanoTable[find(el[i])].numOfoccurrences);
- }
- return probability;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement