| GoodDron0 |
| Отправлено: 19.05.2006, 16:47 |
|
Не зарегистрирован
|
Алгоритм находится здесь : http://algolist.manual.ru/compress/standar...ard/huffman.php
Перепечатываю его сюда:
Huffman — Сначала кажется что создание файла меньших размеров из исходного без кодировки
последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим
себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много
времени мы приобретем знания и дополнительное место на дисках.
Сжимая файл по алгоритму Хаффмана первое что мы должны сделать — это необходимо прочитать файл
полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы
будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.
После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и
сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого
символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней
таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут
указывает на этот "узел". Для ясности давайте рассмотрим пример:
Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение
каждого из символов в файл и получили следующее :
|-----------------|-----|-----|-----|-----|-----|-----|
| cимвол | A | B | C | D | E | F |
|-----------------|-----|-----|-----|-----|-----|-----|
| число вхождений | 10 | 20 | 30 | 5 | 25 | 10 |
|-----------------|-----|-----|-----|-----|-----|-----|
Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу
как ниже.
|-----------------|-----|-----|-----|-----|-----|-----|
| cимвол | C | E | B | F | A | D |
|-----------------|-----|-----|-----|-----|-----|-----|
| число вхождений | 30 | 25 | 20 | 10 | 10 | 5 |
|-----------------|-----|-----|-----|-----|-----|-----|
Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо
символ из F или A (10), можно взять любой из них например A.
Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :
Частота 30 10 5 10 20 25
Символа C A D F B E
| |
|--|--|
||-|
|15| = 5 + 10
|--|
Номер в рамке — сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими
частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной
частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :
Частота 30 10 5 10 20 25
Символа C A D F B E
| | | | | |
| | | | | |
| | |--|| | | |
| |-|15|| | | |
| ||-| | | |
| | | | |
| | |--| | | |--| |
| |----|25|-| |-|45|-|
| ||-| ||-|
| |--| | |
|----|55|------| |
|-|| |
| |------------| |
|---| Root (100) |----|
|------------|
Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.
Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем
идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C
- 00. Для следующего символа ( А ) у нас получается — лево,право,лево,лево , что выливается в
последовательность 0100. Выполнив выше сказанное для всех символов получим
C = 00 ( 2 бита )
A = 0100 ( 4 бита )
D = 0101 ( 4 бита )
F = 011 ( 3 бита )
B = 10 ( 2 бита )
E = 11 ( 2 бита )
Каждый символ изначально представлялся 8-ю битами ( один байт ), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла.
Сжатие складывется следующим образом :
|----------|----------------|-------------------|--------------|
| Частота | первоначально | уплотненные биты | уменьшено на |
|----------|----------------|-------------------|--------------|
| C 30 | 30 x 8 = 240 | 30 x 2 = 60 | 180 |
| A 10 | 10 x 8 = 80 | 10 x 3 = 30 | 50 |
| D 5 | 5 x 8 = 40 | 5 x 4 = 20 | 20 |
| F 10 | 10 x 8 = 80 | 10 x 4 = 40 | 40 |
| B 20 | 20 x 8 = 160 | 20 x 2 = 40 | 120 |
| E 25 | 25 x 8 = 200 | 25 x 2 = 50 | 150 |
|----------|----------------|-------------------|--------------|
Первоначальный размер файла : 100 байт — 800 бит;
Размер сжатого файла : 30 байт — 240 бит;
240 — 30% из 800 , так что мы сжали этот файл на 70%.
Все это довольно хорошо, но неприятность находится в том факте, что для восстановления первоначального
файла, мы должны иметь декодирующее дерево, так как деревья будут различны для разных файлов.
Следовательно мы должны сохранять дерево вместе с файлом. Это превращается в итоге в увеличение размеров выходного файла.
В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.
Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз — 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику — наша таблица будет приблизительно 50 байтов длинны.
Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт — мы получили 20% сжатие информации.
Не плохо. То что мы действительно выполнили — трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным. Что мы можем получить на этом пути ?
Рассмотрим максимум которй мы можем получить для различных разрядных комбинацй в оптимальном
дереве, которое является несимметричным.
Мы получим что можно иметь только :
4 — 2 разрядных кода;
8 — 3 разрядных кодов;
16 — 4 разрядных кодов;
32 — 5 разрядных кодов;
64 — 6 разрядных кодов;
128 — 7 разрядных кодов;
Необходимо еще два 8 разрядных кода.
4 — 2 разрядных кода;
8 — 3 разрядных кодов;
16 — 4 разрядных кодов;
32 — 5 разрядных кодов;
64 — 6 разрядных кодов;
128 — 7 разрядных кодов;
--------
254
Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.
Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Например код A — 01011 и код B — 0101. Если мы будем получать эти коды побитно, то получив биты 0101 мы не сможем сказать какой код мы получили A или B , так как следующий бит
может быть как началом следующего кода, так и продолжением предыдущего.
Необходимо добавить, что ключем к построению префиксных кодов служит обычное бинарное дерево и если внимательно рассмотреть предыдущий пример с построением дерева , можно убедится , что все получаемые коды там префиксные.
Одно последнее примечание — алгоритм Хаффмана требует читать входной файл дважды , один раз считая
частоты вхождения символов , другой раз производя непосредственно кодирование.
Вообщем, на сайте есть исходный код на Паскале, однако мне это не поможет (((
Нужен на Builder'е.
Единственно, что я написал — открытие файла и создание таблицы, содержащей количество повторений. Круто,
правда? ((
Кто-нибудь может помочь советами насчет остальной части?
Вопрос №1
Я заполнял таблицу повторений следующим образом:
while (!feof(f1))
{
fread(&buf,1,1,f1);
table[buf]++;
}
Полагаю, используй я вместо fread() функцию fgetc() результат был бы такой же. Меня смущает фраза " Если
мы будем получать эти коды побитно... " Т.е. нужно считывать символы побитно? Если да, то как это сделать?
Вопрос №2
"Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A "
Может кто-нибудь объяснить, КАК должно происходить это самое формирование? Нужно использовать
какую-то структуру? И еще, вопрос непосредственно про кодирование : "Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. " Каким образом мы знаем куда поворачивать? Нужно быдет организовывать поиск по струтктуре?
Вообще, не мог бы кто-нибудь написать то, как он решил бы эту задачу? Хотя бы в общем виде, вроде " считывае символы ф-ей fread, создаем структуру такую-то, куда записываем то-то ".
Буду очень признателен.
|
|
|
