gfghh

#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;
}