- NICE.SOURCES (2:5030/1334.67) -------------------------------- NICE.SOURCES -
Msg : 149 из 1714
From : Dmitry Lavrentjev 2:5025/77.78 Срд 19 Июл 00 14:34
To : Serj Peshko Птн 21 Июл 00 00:11
Subj : Сжатие Хаффмана
-------------------------------------------------------------------------------
,--,
----. || `---- Приветствую тебя, Serj.
`--'
18 Июл 00 20:52, All was telefragged by Serj Peshko:
SP> Hello All!
SP>
SP> Ищется алгоpитм (желательно) или исходник сжатия Хаффмана.
еще вариант:
=== Начало Windows Clipboard ===
Алгоритм Хаффмана
Один из первых алгоритмов эффективного кодирования информа-
ции был предложен Д.А.Хаффманом в 1952 году. Идея алгоритма сос-
тоит в следующем: зная вероятности вхождения символов в сообще-
ние, можно описать процедуру построения кодов переменной длины,
состоящих из целого количества битов. Символам с большей вероят-
ностью присваиваются более короткие коды. Коды Хаффмана имеют
уникальный префикс, что и позволяет однозначно их декодировать,
несмотря на их переменную длину. Классический алгоритм Хаффмана
на входе получает таблицу частот встречаемости символов в сообще-
нии. Далее на основании этой таблицы строится дерево кодирования
Хаффмана (H-дерево). Алгоритм построения H-дерева прост и элеган-
тен.
1. Символы входного алфавита образуют список свободных узлов.
Каждый лист имеет вес, который может быть равен либо вероятности,
либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его де-
тей удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит
1, другой - бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в спис-
ке свободных узлов не останется только один свободный узел. Он и
будет считаться корнем дерева.
Первая задача состоит в подсчете числа повторений каждой
буквы алфавита в исходном тексте. Далее из списка удаляются те
буквы, которые ни разу не встретились в тексте. Затем строится
дерево кодирования. Лучше всего предварительно отсортировать по-
лучившийся список в порядке убывания частоты повторений символов.
Построение дерева начнется от самого правого символа в списке.
Частоты двух наиболее редко встречающихся символов суммируются, и
результат записывается в узле дерева. Исходные частоты стали те-
перь "детьми" новой суммарной частоты. Если имеется более двух
символов с минимальной частотой повторений, то нужно просто обра-
зовать из них самостоятельные пары. Если имеется нечетное коли-
чество наименьших значений частоты, то нужно объединить непарную
величину со следующей наименьшей частотой.
По мере продолжения процесса построения "дети" становятся
"внуками", "правнуками" - и так до тех пор, пока все дерево не
будет закончено. Полное количество символов исходного текста бу-
дет представлено в вершине полученного дерева. Таким образом мож-
но осуществлять эффективную проверку правильности построения де-
рева кодирования. Hеобходимо сказать, что созданная структура де-
рева, является оптимальной с точки зрения минимизации кодирова-
ния. То есть, с помощью таблицы кодирования (или префиксного ко-
да), полученной на основе анализа структуры дерева, можно наибо-
лее эффективно сжать исходный текст (это можно доказать математи-
чески).
Допустим, у нас есть следующая таблица частот:
15 7 6 6 5
А Б В Г Д
Hа первом шаге из листьев дерева выбираются два с наименьшими
весами - Г и Д. Они присоединяются к новому узлу-родителю, вес
которого устанавливается в 5 + 6 == 11. Затем узлы Г и Д удаляют-
ся из списка свободных. Узел Г соответствует ветви О родителя,
узел Д - ветви 1.
Hа следующем шаге то же происходит с узлами Б и В, так как
теперь эта пара имеет самый меньший вес в дереве. Создается новый
узел с весом 13, а узлы Б и В удаляются из списка свободных. Пос-
ле всего этого дерево кодирования выглядит так, как показано на
рис.
0----13-----1 0------11---------1
| | | |
15 7 6 6 5
А Б В Г Д
Дерево кодирования Хаффмана после второго шага
Hа следующем шаге <наилегчайшей> парой оказываются узлы Б/В
и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24.
Узел Б/В соответствует ветви 0 родителя, Г/Д - ветви 1.
Hа последнем шаге в списке свободных осталось только два уз-
ла - это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель
с весом 39 и бывшие свободными узлы присоединяются к разным его
ветвям.
Поскольку свободным остался только один узел, то алгоритм
построения дерева кодирования Хаффмана завершается. H-дерево
представлено на рис.
0-----39-------------------1
| |
| 0-----------24------------1
| | |
| 0----13-----1 0------11---------1
| | | | |
15 7 6 6 5
А Б В Г Д
Окончательное дерево кодирования Хаффмана
Чтобы определить код для каждого из символов, входящих в со-
общение, мы должны пройти путь от листа дерева, соответствующего
этому символу, до корня дерева, накапливая биты при перемещении
по ветвям дерева. Полученная таким образом последовательность би-
тов является кодом данного символа, записанным в обратном поряд-
ке.
Для данной таблицы символов коды Хаффмана будут выглядеть
следующим образом.
А 0
Б 100
В 101
Г 110
Д 111
Поскольку ни один из полученных кодов не является префиксом
другого, они могут быть однозначно декодированы при чтении их из
потока. Кроме того, наиболее частый символ сообщения А закодиро-
ван наименьшим количеством битов, а наиболее редкий символ Д -
наибольшим.
Классический алгоритм Хаффмена имеет один существенный не-
достаток. Для восстановления содержимого сжатого сообщения деко-
дер должен знать таблицу частот, которой пользовался. кодер. Сле-
довательно, длина сжатого сообщения увеличивается на длину табли-
цы частот, которая должна посылаться впереди данных, что может
свести на нет все усилия по сжатию сообщения. Кроме того, необхо-
димость наличия полной частотной статистики перед началом собс-
твенно кодирования требует двух проходов по сообщению: одного для
построения модели сообщения (таблицы частот и H-дерева ), другого
для собственно кодирования.
Алгоритм Хаффмана (Huffman Encoding), или кодирование симво-
лами переменной длины, предлагает отказаться от обычного предс-
тавления файлов в виде последовательностей 7- или 8-битных симво-
лов. Главный недостаток такого способа записи файлов состоит в
том, что в нем не делается различий между кодированием символов,
с разной частотой встречающихся в файлах. Так, наиболее частые в
английском языке символы E и I, имеют ту же самую длину, что и
относительно редкие Z, X или Q. Код переменной длины позволяет
записывать наиболее часто встречающиеся символы и фразы всего
лишь несколькими битами, в то время как редкие символы и фразы
будут записаны более длинными битовыми строками.
Простейший способ кодирования информации символами перемен-
ной длины осуществляется при помощи таблицы соответствий (trans-
lation table). Hапример, анализируя любой английский текст, можно
установить, что буква E встречается гораздо чаще, чем Z, а X и Q
относятся к наиболее редко встречающимся. Таким образом, исполь-
зуя таблицу соответствий, мы можем закодировать каждую букву E
меньшим числом бит, используя более длинный код для более редких
букв.
Хотя такой прием пригоден для текстов любого типа, большинс-
тво практических программ вычисляют свою таблицу соответствий для
каждого нового документа. Таким образом исключаются случайные
отклонения каждого конкретного текста от среднестатистического, и
устраняются связанные с этим потери эффективности степени сжатия.
=== Кончало Windows Clipboard===
SP>
SP> WBR, bLACK sMOKE...
SP> -+- Сижy вот, слyшаю 'Macbeth - Black Heaven'...
SP> * Origin: FigVam mail station <283-58-38> [00:00-07:00] (2:450/174.5)
До скорого, Serj.
... А мой модем умеет долго дер|«A|/§;D. NO CARRIER
--- Два солдата из стройбата заменяют взвод гестапо
* Origin: 2:5025/77.78 Default squish origin (2:5025/77.78)
|
|
