Что не так с реализацией алгоритма Хаффмана?

Question

[Никита Гусаков]

вот код

Все работает, за исключением преобразования последнего символа. Вообще ни в какую не преобразовывается, и я не понимаю почему, хотя подозреваю что не совсем правильно работаю с файлами.

PS Также вопрос было бы полезно для новичков в виде туториала? Описать реализацию этого алгоритма? Видел несколько статей, но ни в одной не описывается обратный процесс преобразования.

Answer 1

[mayorovp]

Так, а какие файлы называются «большими»?
Навскидку я вижу две проблемы — файлы более 2Гб (переполнение int) и нулевые символы (которым ошибочно не назначается код).

Первая проблема лечится использованием большего типа данных, а вторая таким вот патчем:

void Compressor::buildCodeTable(Node *root)
{
    if (root->hasChild())
    {
        code.push_back(0);
        buildCodeTable(root->getChild(true));
        code.pop_back();

        code.push_back(1);
        buildCodeTable(root->getChild(false));
        code.pop_back();
    } else {
        codeTable[letter] = root->getLetter();
    }
}

Answer 2

[B@rmaley.e><e]

Для последнего байта нужно знать количество значащих бит. Ведь разные символы, сжатые по Хаффману, имеют различную битовую длину, а писать можно только байты.
Может быть, этот случай Вами уже учтён, но при поверхностном взгляде я этого не увидел.

Answer 3

[mayorovp]

Вот этот кусок надо добавить в функцию compress перед закрытием потока:

if (count > 0)
    out << buf;

Это связано с тем, что после цикла в buf могли оказаться значимые биты, не образующие полного байта и потому еще не записанные в поток.

Answer 4

[mayorovp]

Да, еще замечание по структуре: мне не кажется хорошей идеей объединение методов compress и decompress в одном классе, хранящем входной файл в виде поля. Как мне кажется, еще на этапе создания экземпляра пользователь библиотеки будет знать, что ему с этим файлом делать — упаковывать или распаковывать.

ИМХО лучше выделить поля charMap, charTree и inputFile в базовый класс, а остальное разбросать по классам Compressor и Decompressor. Еще лучше ограничиться двумя глобальными функциями.

Еще один вариант — убрать сущность «входной файл» из полей класса. Это позволит собирать статистику по одному потоку, а сжимать — другой, что может быть полезным для сжатия «на лету». Или можно хранить статистику отдельно от сжатых данных, чему тоже можно найти применение.

Comments

[Никита Гусаков]

Я так и делал, просто делаю девушке — она не объяснит, наследования у них небыло, а сама не знает.

[mayorovp]

Остаются второй и третий варианты. Они столь же просты для понимания.

Answer 5

[mayorovp]

Еще две ошибки — вы не удаляете созданные сущности Node, что вызывает утечку памяти. Кроме того, выполнение tree.sort в цикле — ужасная идея. Правильная реализация алгоритма использует тот факт, что сущности Node в алгоритме создаются в порядке возрастания частот, благодаря чему можно обойтись одной сортировкой исходных нод в начале.

Comments

[Никита Гусаков]

Утечки вроде как убрал (как проверить?)
Как можно обойтись одной сортировкой? Когда мы соеденили две ноды — ее верхушка становится новой нодой, с новым весом. Другой вопрос что возможно можно не полностью сортировать, а просто подвинуть эту ноду как раз.
Еще такой вопрос — есть идеи почему не разжимаются большие файлы?
И если вдруг знаете — ткните пожалуйста носом, где посмотреть правильную реализацию?

[mayorovp]

Проверить на утечки просто — запустите связку «конструктор-compress-деструктор» в цикле с достаточным числом итераций.

Вот реализация с одной сортировкой (не проверял, писал прямо тут):

static Node* pop_less(list<Node*> &first, list<Node*> &second) {
    Node* node1 = first.size() ? first.front() : NULL;
    Node* node2 = second.size() ? second.front() : NULL;

    if (node1 && (!node2 || Node::compare(node1, node2))) {
        first.pop_front();
        return node1;
    } else {
        second.pop_front();
        return node2;
    }
}

void Compressor::buildCharTree()
{
    list<Node*> first, second;

    for(CharMap::iterator i = charMap.begin(); i != charMap.end(); i++)
        first.push_back(new Node(i->second, i->first));

    first.sort(Node::compare);

    while (first.size() + second.size() > 1)
    {
        Node *left = pop_less(first, second);
        Node *right = pop_less(first, second);

        second.push_back(new Node(left, right));
    }

    charTree = pop_less(first, second);
}

Можете попытаться оформить лучше, чтобы девушка поняла.

Answer 6

[mayorovp]

Да, только что заметил: метод decompress теперь может распаковать несколько мусорных символов в конце файла (попробуйте упаковать файл, содержащий всего один символ). Надо бы записывать перед сжатым потоком длину исходного, или хотя бы ее последние три бита.

Comments

[mayorovp]

Еще один вариант — закончить сжатый поток спецсимволом «конец данных» (это будет символ с номером 256).