Алгоритм Хафмана

Алгоритм Хафмана

В основе этого алгоритма лежит кодирование не байтами, а битовыми группами.

• Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов.

• Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность).

Образующаяся в результате кодирования иерархическая структура приклады­вается к сжатому документу в качестве таблицы соответствия.

Пример кодирования символов русского алфавита представлен на рис. 14.1.

Как видно из схемы, представленной на рис. 14.1, используя 16 бит, можно закоди­ровать до 256 различных символов. Однако ничто не мешает использовать и пос­ледовательности длиной до 20 бит — тогда Алгоритм Хафмана можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова).

В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответ­ствия, на файлах малых размеров алгоритм Хафмана малоэффективен. Практика также показывает, что его эффективность зависит и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до1024 единиц (длина кода до 18-20 бит).


documentagkihyv.html
documentagkipjd.html
documentagkiwtl.html
documentagkjedt.html
documentagkjlob.html
Документ Алгоритм Хафмана