#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
struct Node {
char byte; // для хранения байта
int freq; // частота
string code; // для кодирования
Node* left;
Node* right;
Node* parent;
Node() : byte(NULL), freq(0), code("0"), left(nullptr), right(nullptr), parent(nullptr) {};
Node(char byte, int freq) : byte(byte), freq(freq), code("0"), left(nullptr), right(nullptr), parent(nullptr) {};
};
class Archive {
protected:
Node** tree; //дерево
int qua; //кол-во уникальных байтов
int size; // текущий размер дерева
Node** haffman_table; //таблица Хаффмана
int ind_table; //индекс для таблицы
struct Header {
char byte;
int freq;
};
Header haffman_header[256];
public:
Archive() : qua(0), size(0), ind_table(0) {}
public:
void archive(string file_name) {
get_symbols(file_name);
create_header();
create_tree();
create_table(tree[0], ind_table);
print_table();
ofstream archive("archive_" + file_name + ".bin", ios::binary);
if (!archive.is_open()) {
return;
}
char padding = 0; // для последнего байта
archive.put(padding);
archive.write((const char*)&haffman_header, sizeof(haffman_header));
ifstream input(file_name, std::ios::binary);
if (!input.is_open()) {
return;
}
input.seekg(0);
char byte;
string buffer = "";
while (input.get(byte)) {
for (int i = 0; i < qua; i++) {
if (byte == haffman_table[i]->byte) {
for (int j = 0; j < haffman_table[i]->code.length(); j++) {
if (buffer.length() < 8) {
buffer += haffman_table[i]->code[j];
}
else {
archive.put(convert_to_byte(buffer));
buffer = haffman_table[i]->code[j];
}
}
}
}
}
if (buffer.length() != 8) {
archive.put(convert_to_byte(buffer));
padding = 8 - buffer.length();
archive.seekp(0);
archive.put(padding);
}
archive.close();
input.close();
}
protected:
char convert_to_byte(string code) {
char result = 0;
for (char bit : code) {
result = (result << 1) | (bit - '0');
}
return result;
}
void sort() { //по возрастанию частот
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (tree[j]->freq > tree[j + 1]->freq) {
Node* tmp = tree[j];
tree[j] = tree[j + 1];
tree[j + 1] = tmp;
}
}
}
}
void push(Node* node) {
size++;
Node** new_tree = new Node * [size];
for (int i = 0; i < size - 1; i++) {
new_tree[i] = tree[i];
}
new_tree[size - 1] = node;
delete[] tree;
tree = new_tree;
}
Node* pop() {
Node* pop_node = tree[0];
size--;
Node** new_tree = new Node * [size];
for (int i = 0; i < size; i++) {
new_tree[i] = tree[i + 1];
}
delete[] tree;
tree = new_tree;
return pop_node;
}
void create_table(Node* node, int& ind) {
if (node->parent != nullptr) if (node->parent->parent != nullptr) node->code += node->parent->code;
if (node->left == nullptr && node->right == nullptr) {
reverse(node->code.begin(), node->code.end());
haffman_table[ind] = node;
ind++;
}
if (node->left != NULL) create_table(node->left, ind);
if (node->right != NULL) create_table(node->right, ind);
}
void print_table() {
for (int i = 0; i < qua; i++) {
cout << haffman_table[i]->byte << " " << haffman_table[i]->code << endl;
}
}
void create_header() {
for (int i = 0; i < qua; i++) {
haffman_header[i].byte = tree[i]->byte;
haffman_header[i].freq = tree[i]->freq;
}
}
void create_tree() { // при равных частотах - беру тот узел, что был создан раньше
while (size > 1) {
sort();
Node* left = pop();
Node* right = pop();
Node* parent_node = new Node;
parent_node->freq = left->freq + right->freq;
left->parent = parent_node;
right->parent = parent_node;
right->code = "1";
parent_node->left = left;
parent_node->right = right;
push(parent_node);
}
}
void get_symbols(string file_name) {
ifstream input(file_name, ios::binary);
if (!input.is_open()) {
cout << "Ошибка открытия файла - " << file_name << endl;
return;
}
Node** tmp = new Node * [256];
char byte;
bool f;
while (input.get(byte)) {
f = false;
for (int i = 0; i < qua; i++) {
if (tmp[i]->byte ==
byte) {
tmp[i]->freq++;
f = true;
}
}
if (!f) {
Node* node = new Node(byte, 1);
tmp[qua] = node;
qua++;
}
}
input.close();
size = qua;
tree = new Node * [qua];
for (int i = 0; i < qua; i++) {
tree[i] = tmp[i];
}
delete[] tmp;
haffman_table = new Node * [qua];
}
};
class Unarchive : public Archive {
private:
char padding;
public:
void unzip(string file_name) {
get_header(file_name);
create_tree();
ifstream archive(file_name, ios::binary);
if (!archive.is_open()) {
cout << "Ошибка открытия файла - " << file_name << endl;
return;
}
ofstream file(change_name(file_name), ios::binary);
if (!file.is_open()) {
return;
}
archive.seekg(sizeof(haffman_header) + 1, ios::beg); // чтобы не считывать заголовок снова
char byte;
Node* current = tree[0];
while (archive.get(byte)) {
string binary = convert_to_string(byte);
if (archive.peek() == EOF) {
binary = binary.substr(padding);
}
for (int i = 0; i < binary.length(); i++) {
if (binary[i] == '0') {
current = current->left;
}
if (binary[i] == '1') {
current = current->right;
}
if (current->left == nullptr && current->right == nullptr) {
file.put(current->byte);
current = tree[0];
}
}
}
}
private:
string convert_to_string(char byte) {
string binary;
for (int i = 7; i >= 0; --i) {
char bit = char((byte >> i) & 1) + '0';
binary += bit;
}
return binary;
}
void get_header(string file_name) {
ifstream archive(file_name, ios::binary);
if (!archive.is_open()) {
return;
}
archive.get(padding);
archive.read((char*)&haffman_header, sizeof(haffman_header));
for (int i = 0; i < 256; i++) {
if (haffman_header[i].freq == 0) {
qua = i;
break;
}
}
tree = new Node * [qua];
for (int i = 0; i < qua; i++) {
Node* node = new Node(haffman_header[i].byte, haffman_header[i].freq);
push(node);
}
archive.close();
}
string change_name(string file_name) {
int pos = file_name.find("archive");
if (pos != std::string::npos) {
file_name.erase(pos, 7);
}
pos = file_name.find(".bin");
if (pos != std::string::npos) {
file_name.erase(pos, 4);
}
string a = "back_";
return a + file_name;
}
};
int main() {
setlocale(LC_ALL, "rus");
Archive test;
test.archive("123.txt");
Unarchive test_2;
test_2.unzip("archive_123.txt.bin");
system("pause");
return 0;
}
