Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
если ты про сжатие Хаффмена то... 05.06.01 15:05 Число просмотров: 1725
Автор: XR <eXtremal Research> Статус: The Elderman Отредактировано 05.06.01 15:11 Количество правок: 2
|
суть заключается в кодировании часто встречающихся символов кодом меньшей
длины (чем чаще встречается символ тем меньшим количеством бит он закодирован) - алгоритм как правило сводится к построению "дерева Хаффмена"
на таком же принципе основано кодирование Шеннона-Фано и арифметическое кодирование (последнее считается наиболее эффективным)
subj ищется по кейворду .... правильно :) "Haffman encoding"
Haffman encoding
|
<theory>
|
Люди, объясните на пальцах суть кода Хаффмена! 05.06.01 12:45
Автор: dickhead Статус: Незарегистрированный пользователь
|
Никак не могу врубиться! Вроде все делаю по алгоритму, но назвать получающийся код эффективным язык не поворачивается. Может кто пришлет человеческое описание???
|
|
если ты про сжатие Хаффмена то... 05.06.01 15:05
Автор: XR <eXtremal Research> Статус: The Elderman Отредактировано 05.06.01 15:11 Количество правок: 2
|
суть заключается в кодировании часто встречающихся символов кодом меньшей
длины (чем чаще встречается символ тем меньшим количеством бит он закодирован) - алгоритм как правило сводится к построению "дерева Хаффмена"
на таком же принципе основано кодирование Шеннона-Фано и арифметическое кодирование (последнее считается наиболее эффективным)
subj ищется по кейворду .... правильно :) "Haffman encoding"
Haffman encoding
|
| |
спасибо, конечно... 07.06.01 12:16
Автор: dickhead Статус: Незарегистрированный пользователь
|
XR, это все замечательно, но исходники на С мне много не расскажут(туповат я для этого). Про сжатие Шеннона-Фэно я слыхал/делал/знаю, а вот с Хаффманом ничего кроме деревьев найти не могу. А, спрашивается, каким, извините, образом они строятся???
|
| | |
спасибо, конечно... 10.06.01 23:12
Автор: Dmit Статус: Незарегистрированный пользователь
|
> XR, это все замечательно, но исходники на С мне много не > расскажут(туповат я для этого). Про сжатие Шеннона-Фэно я > слыхал/делал/знаю, а вот с Хаффманом ничего кроме деревьев > найти не могу. А, спрашивается, каким, извините, образом > они строятся???
Дык, считаешь вероятность каждой кодируемой последовательности (напрмер, каждого кодируемого байта), и строишь такое двоичное дерево, чтобы сумма произведений вероятности последовательности на длину пути на дереве до представляющего ее листа была минимальной.
Например, у нас 4 возможных последовательности (символа): a, b, c, и d
Нам надо закодировать строку aadaabaaacdaaadadaaa (20 символов). Каждый символ может быть представлен 2 битами, итого 40 бит.
Если построить дерево с такими листьями:
a - 0
b - 110
c - 111
d - 10
то строка будет закодирована как 0-0-10-0-0-110-0-0-0-111-10-0-0-0-10-0-10-0-0-0
итого 28 бит
|
|
|