если ты про сжатие Хаффмена то...05.06.01 15:05 Число просмотров: 1827 Автор: XR <eXtremal Research> Статус: The Elderman Отредактировано 05.06.01 15:11 Количество правок: 2
суть заключается в кодировании часто встречающихся символов кодом меньшей
длины (чем чаще встречается символ тем меньшим количеством бит он закодирован) - алгоритм как правило сводится к построению "дерева Хаффмена"
на таком же принципе основано кодирование Шеннона-Фано и арифметическое кодирование (последнее считается наиболее эффективным)
subj ищется по кейворду .... правильно :) "Haffman encoding"
Никак не могу врубиться! Вроде все делаю по алгоритму, но назвать получающийся код эффективным язык не поворачивается. Может кто пришлет человеческое описание???
если ты про сжатие Хаффмена то...05.06.01 15:05 Автор: XR <eXtremal Research> Статус: The Elderman Отредактировано 05.06.01 15:11 Количество правок: 2
суть заключается в кодировании часто встречающихся символов кодом меньшей
длины (чем чаще встречается символ тем меньшим количеством бит он закодирован) - алгоритм как правило сводится к построению "дерева Хаффмена"
на таком же принципе основано кодирование Шеннона-Фано и арифметическое кодирование (последнее считается наиболее эффективным)
subj ищется по кейворду .... правильно :) "Haffman encoding"
XR, это все замечательно, но исходники на С мне много не расскажут(туповат я для этого). Про сжатие Шеннона-Фэно я слыхал/делал/знаю, а вот с Хаффманом ничего кроме деревьев найти не могу. А, спрашивается, каким, извините, образом они строятся???
> 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 бит
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
