Некорректно работает алгоритм Хаффмана

Пишу реализацию алгоритма Хаффмана на 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. это всё только предположения

→ Ссылка