Некорректно работает алгоритм Хаффмана
Пишу реализацию алгоритма Хаффмана на C++ CLR. Архивация происходит правильно, а при разархивации иногда выдаёт неверный изначальный текст. Думаю, что ошибка, возможно, в том, что изначальный файл хранится в utf-8, а закодированный и дерево в ANSI. Буду рад любой помощи.
Класс для архивации/разархивации:
#include "Haffman.h"
using namespace std;
struct MyCompare
{
bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
void Haffman::encode()
{
ifstream f(this->Path);
map<char, int> m;
while (!f.eof())
{
char c = f.get();
m[c]++;
}
string full_endpath = this->EndPath;
full_endpath += "\\file_with_table.txt";
ofstream file_with_table(full_endpath);
map<char, int>::iterator i;
for (i = m.begin(); i != m.end(); ++i)
file_with_table << i->first << " " << i->second << endl;
file_with_table.close();
list<Node*> t;
for (map<char, int>::iterator itr = m.begin(); itr != m.end(); ++itr)
{
Node* p = new Node;
p->c = itr->first;
p->a = itr->second;
t.push_back(p);
}
while (t.size() != 1)
{
t.sort(MyCompare());
Node* SonL = t.front();
t.pop_front();
Node* SonR = t.front();
t.pop_front();
Node* parent = new Node(SonL, SonR);
t.push_back(parent);
}
Node* root = t.front();
BuildTable(root);
f.clear(); f.seekg(0);
full_endpath = this->EndPath;
full_endpath += "\\file_with_cods_table.txt";
ofstream file_with_cods_table(full_endpath);
while (!f.eof())
{
char c;
f >> c;
vector <bool> x = table[c];
for (int n = 0; n < x.size(); n++)
if ((x[n] + 1) % 8 == 0)
file_with_cods_table << x[n];
}
f.clear(); f.seekg(0);
full_endpath = this->EndPath;
full_endpath += "\\output.bin";
ofstream g(full_endpath);
int count = 0;
char buf = 0;
int n;
while (!f.eof())
{
char c = f.get();
vector<bool> x = table[c];
for (n = 0; n < x.size(); n++)
{
buf = buf | x[n] << (7 - count);
count++;
if (count == 8)
{
count = 0;
g << buf;
buf = 0;
}
}
}
f.close();
g.close();
}
void Haffman::decode()
{
list<Node*> t;
string full_path = this->Path;
full_path += "\\file_with_table.txt";
std::ifstream in(full_path);
char sym;
int freq;
ofstream test("test.txt");
while (in >> sym >> freq)
{
Node* p = new Node;
p->a = freq;
p->c = sym;
t.push_back(p);
test << p->a << " " << p->c;
}
test.close();
while (t.size() != 1)
{
t.sort(MyCompare());
Node* SonL = t.front();
t.pop_front();
Node* SonR = t.front();
t.pop_front();
Node* parent = new Node(SonL, SonR);
t.push_back(parent);
}
Node* root = t.front();
string full_endpath = this->EndPath;
full_endpath += "\\Decoded text.txt";
full_path = this->Path;
full_path += "\\output.bin";
ifstream F(full_path, ios::in | ios::binary);
ofstream D(full_endpath);
Node* p = root;
int count = 0;
char byte;
byte = F.get();
while (!F.eof())
{
bool b = byte & (1 << (7 - count));
if (b == 1)
p = p->right;
else p = p->left;
if ((p->left == NULL) && (p->right == NULL))
{
D << p->c;
p = root;
}
count++;
if (count == 8)
{
count = 0;
byte = F.get();
}
}
F.close();
}
Haffman::Haffman(const char* path, const char* endpath, bool action)
{
this->Path = path;
this->EndPath = endpath;
if (action)
{
encode();
}
else
{
decode();
}
}
void Haffman::BuildTable(Node* root)
{
if (root->left != NULL)
{
this->code.push_back(0);
BuildTable(root->left);
}
if (root->right != NULL)
{
this->code.push_back(1);
BuildTable(root->right);
}
if (root->c)
this->table[root->c] = code;
if (this->code.size() != 0)
{
this->code.pop_back();
}
}
Код кнопки для архивации/разархивации:
private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {
using namespace Runtime::InteropServices;
const char* chars =
(const char*)(Marshal::StringToHGlobalAnsi(textBox1->Text)).ToPointer();
std::string pathStr = chars;
const char* chars2 =
(const char*)(Marshal::StringToHGlobalAnsi(textBox2->Text)).ToPointer();
std::string endpathStr = chars2;
const char* cstr = pathStr.c_str();
const char* cstr2 = endpathStr.c_str();
if (radioButton1->Checked)
{
Haffman h(cstr, cstr2, true);
}
else if (radioButton2->Checked)
{
Haffman h(cstr, cstr2, false);
}
};
Ответы (1 шт):
Могу предположить следующее
Вы используете char для хранения закодированных битов. Однако, когда вы записываете их в файл, вы не всегда правильно интерпретируете эти байты.
В методе encode() походу не учитывается ситуация, когда последний байт не заполнен полностью. Это может приводить к тому, что часть информации может потеряться. Я вот об этом
if (count == 8)
{
count = 0;
g << buf;
buf = 0;
}
Что если после выхода из цикла добавить проверку на оставшиеся биты:
if (count > 0) {
g << buf; // Записываем финальный байт, если он неполный
}
Ну а метод decode() можно попробовать сделать так
void Haffman::decode()
{
// ... ваш код для построения дерева ...
std::string full_endpath = this->EndPath + "\\Decoded text.txt";
std::string full_path = this->Path + "\\output.bin";
std::ifstream F(full_path, std::ios::in | std::ios::binary);
std::ofstream D(full_endpath);
Node* p = root;
int count = 0;
char byte;
while (F.get(byte)) // Читаем байты до конца файла
{
for (int i = 0; i < 8; ++i)
{
bool b = byte & (1 << (7 - i)); // Проверяем каждый бит
p = b ? p->right : p->left; // Перемещаемся по дереву
if (!p->left && !p->right) // Если листовой узел
{
D << p->c; // Пишем символ
p = root; // Возвращаемся к корню
}
}
}
F.close();
D.close();
}
ps. это всё только предположения