Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
спасибо, конечно... 10.06.01 23:12 Число просмотров: 1514
Автор: 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 бит
|
|
|