Проблема с написанием архиватора!
Здравствуйте. Пишу архиватор по методу Хафмана.
В некоторых способах этого метода бинарное дерево не нужно вообше, я писал черновой
архиватор по методу Хафмана, тоже не пользуясь деревом частот символов. НО в этом
случае надо было к каждому коду, заменяюшему символ, крисоединять префиксные нули, чтобы при разархивации эти самые коды не сливались, что очень понижает степень сжатия (а не редко и наоборот увеличивает объем файла). А в статье этого сайта, как я понял можно обойтись без разделяющих префиксов,
но чтобы коды не сливались (понимались что это начало другого кода а не продолжение предыдущего), требуется это самое дерево, над
структурой которого я уже мечаюсь не одну неделю. Тоесть я понял саму идею
дерева и алгоритм, НО ту последовательность байт этого дерева, уже лежашего в
архивном файле я так и не вразумил (т.е. в статье об этом ничего не написано). Вот к примеру, в статье пишеться, что на
инициализацию (задание или кодирование) каждого узла (суммы частот) этого
дерева требуесться 4 байта и что максимальное дерево для 256 быйтов займет
около одного Kb. Но, одноко, ничего не скозано о том, как именно эти четыре
байта задают этот узел. Вот я и не пойму, какой последовательностью байт мне
загнать это деревце в файл, чтобы потом можно было по нему декодировать? Вобщем
вот такие у меня проблемы.
Не хочу показаться вам назойлевым, но немогли бы вы мне написать об этой
узкой древеснобинареой бласти на [EMAIL]nomata@mail.ru.[/EMAIL]
С уважением, Василий Резник.
P.S.
Ошибок наверное многo, в ворде не проверял, ПРаВильНоПисаНиЕ хромает.
В некоторых способах этого метода бинарное дерево не нужно вообше, я писал черновой
архиватор по методу Хафмана, тоже не пользуясь деревом частот символов. НО в этом
случае надо было к каждому коду, заменяюшему символ, крисоединять префиксные нули, чтобы при разархивации эти самые коды не сливались, что очень понижает степень сжатия (а не редко и наоборот увеличивает объем файла). А в статье этого сайта, как я понял можно обойтись без разделяющих префиксов,
но чтобы коды не сливались (понимались что это начало другого кода а не продолжение предыдущего), требуется это самое дерево, над
структурой которого я уже мечаюсь не одну неделю. Тоесть я понял саму идею
дерева и алгоритм, НО ту последовательность байт этого дерева, уже лежашего в
архивном файле я так и не вразумил (т.е. в статье об этом ничего не написано). Вот к примеру, в статье пишеться, что на
инициализацию (задание или кодирование) каждого узла (суммы частот) этого
дерева требуесться 4 байта и что максимальное дерево для 256 быйтов займет
около одного Kb. Но, одноко, ничего не скозано о том, как именно эти четыре
байта задают этот узел. Вот я и не пойму, какой последовательностью байт мне
загнать это деревце в файл, чтобы потом можно было по нему декодировать? Вобщем
вот такие у меня проблемы.
Не хочу показаться вам назойлевым, но немогли бы вы мне написать об этой
узкой древеснобинареой бласти на [EMAIL]nomata@mail.ru.[/EMAIL]
С уважением, Василий Резник.
P.S.
Ошибок наверное многo, в ворде не проверял, ПРаВильНоПисаНиЕ хромает.
Аноним
Дерево строим так, для простоты положим, что получившийся код влезет в 32 бита, а также что все байты от 0 до 255 задействованы
typedef struct
{
int nCount;
bool fUsed;
int nChildren[2];
} node_t;
#define MAX_NODES 512
node_t g_tNodes[MAX_NODES] = {0};
int g_cNodes = 0;
unsigned g_uCodes[256] = {0};
int g_nCodesLen[256] = {0};
...
char *pData=...; //входные данные
int cDataSize=...; // их размер
// заполняем счётчики
for (int i=0; i<cDataSize; i++)
g_tNodes[pData].nCount++;
// строим дерево, ф-ция SmallestNode()
// просто возвращает индекс в g_tNodes узла с наименьшим счетчиком
// и выставляет у него fUsed в true, чтобы в следующий раз его не брать
g_cNodes = 256;
while (g_cNodes < MAX_NODES)
{
node_t* pNode = g_tNodes + g_cNodes;
// выбираем два самых маленьких счетчика
if ((pNode->nСhildren[0] = SmallestNode()) == -1)
break; // нету больше узлов
if ((pNode->nСhildren[1] = SmallestNode()) == -1)
break;
// и создаём узел их объединяющий (его счётчик и их сумма)
pNode->nCount = g_tNodes[pNode->nChildren[0]].nCount + g_tNodes[pNode->nChildren[1]].nCount;
g_cNodes++;
}
// на этом этапе мы имеем дерево
// коды строятся проходом по этому дереву с помощью рекурсивной ф-ции SetupBits (см ниже)
// начинаем строить код, пробегая от корня дерева к листьям.
SetupBits (g_cNodes-1, 0, 0);
// коды построены остаётся используя полученые коды закодировать инфу (разделители между кодовыми комбинациями не нужны кстати т.к. коды переменной длины, будет получаться что комбинации пересекают границы байт) и её сохранить вместе со словарём (счётчики), словарь нужен для того чтобы потом восстановить дерево при распаковке.
void SetupBits(int nNode, unsigned uBits, int cBits)
{
// если это начальный узел(один из тех для которых мы считали коды в начале),
// то назначаем ему построеный код
if (nNode < 256)
{
g_uCodes[nNode] = uBits;
g_nCodesLen[nNode] = cBits;
return;
}
node_t *pNode = g_tNodes + nNode;
// левому потомку добавляем в код 0
uBits <<= 1;
SetupBits(pNode->nChildren[0], uBits, cBits+1);
// а правому 1
uBits |= 1;
SetupBits(pNode->nChildren[1], uBits, cBits+1);
}
Вот такие дела.
Могу сказать что простое кодирование по байтам неэффективно и сжать произвольный файл используя только кодирование Хаффмана, особо не удастся. Следует обратить внимание на алгоритм Лемпеля-Зива-Уэлша(может не правильно фамилии написал) он известен как LZW используется повсеместно как наиболее простой (ZIP, GIF, в модеме). Также есть сжатие с потерей качества для мультимедиа, тоже фича прикольная. И block-sorting алгоритмы, на которых, по-моему, сделан RAR, если я не ошибаюсь.
Простой пример
Имеем слово 'abacabcad' 9байт, тогда
символ счетчик дерево код
a 4 -------9- 1
b 2 -----5-| 01
c 2 --3--| 001
d 1 --| 0001
на дереве цифры это промежуточные узлы, корень за девяткой.
кодируем a-1, b-01, c-001 и т.д.
101100110100110001 - 18 бит ~ 3байта (два полных)
раскодировать можно не имея разделителей!
финальный файл это счетчики и наш поток бит 101..
4 2 2 1 x y z - 7 байт всего, негусто против 9 бывших.
xyz это байты потока.
Вот и всё что я хотел рассказать