Сжатия по алгоритму Хаффмана на Qt Опции

[dsp]

Здравствуйте.

Задали в универе реализовать данный алгоритм на Делфи, но к Делфи я равнодушен и тратить на него время не хочу, а посему решил поизучать Qt, т.к. познаю на данный момент самостоятельно С++. Я не прошу писать за меня код, но, т.к. с Qt я почти не знаком, хотелось бы получать от вас помощь в качестве наводок на тот или иной класс, дабы я смог написать программу и чему-то научился.

Сам алгоритм, как я себе его представляю:

1) Читаем файл, который требуется подвергнуть сжатию. Это нужно для того, что бы подсчитать частоту повторяющихся в нем символов. Читаем побайтно (какой класс для этого использовать?);
2) Записываем считанные символы и их частоту в какую-то структуру данных (map?);
3) Сортируем по возрастанию считанные символы (есть ли смысл сортировать map, или лучше сделать отдельный массив ссылок на каждый элемент map, и сортировать ссылки?);
4) Далее, строим дерево, выбирая каждый раз два символа с наименьшим числом вхождения и суммирем их, получая новый узел. Это делать до тех пор, пока не останется один узел (пример можно посмотреть тут (как это делать, пока не знаю. не думал ) );
5) Следует начать кодирование файла, начиная обход каждого узла дерева с корня (как работать с деревьями, пока не знаю);
6) Выполнив обход для всех символов, получим таблицу для каждого символа;
7) Упаковка и сохранение файла вместе с деревом.

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

P.S. Пишу на Qt 4.7, Ubuntu 10.10

Спасибо!

[Алексей1153]

1) QFile , QByteArray

2) посчитать частОты символов - используй вектор
#include <vector>
std::vector<uchar> freq_counter(256,0);

3)
#include <algorithm>
std::sort(...)

4) элемент дерева должен содержать
- указатель (или идентификатор) на узел-родитель
- указатель (или идентификатор) на правый потомок (бит 0)
- указатель (или идентификатор) на левый потомок (бит 1)
- частоту

дерево строится так: организуется стек, куда кладутся все одиночные узлы. Частота символа - это вес узла. Узел - это лист будущего деерва.

создаётся новый узел, затем из стека извлекаются два узла с наименьшими весами, и присоединяются к новому узлу. Получившийся родительский узел кладётся в стек (его вес равен сумме весов листьев)

повторять, пока стек не пуст

в итоге получается требуемое дерево

5,6) тут всё очень просто, когда разберёшься со структурой дерева.

7) в архиве нужно будет сохранить дерево в компактном формате, плюс сами данные архива - последовательность БИТОВ. Для удобства и скорости тут можно написать класс-буфер, который будет накапливать 256*8, скажем, битов и разом скидывать в файл. Ну, и не забыть остаток тоже скинуть потом (дополнить нулями до кратности 8 )

(я тут ещё мудрил с битностью - если размер дерева позволял, то я уменьшал длину логического байта с 8 бит до требуемого максимального значения. Но это как оптимизация сжатия, пока можешь не заморачиваться)

Qt тут ни при чём, в общем-то. Пункт 1 можно сделать статическим массивом (или вектором), заполненным вручную - для тестов

Сообщение отредактировал Алексей1153 - 11.11.2010, 8:08