Метод Хаффмана

Метод Хаффмана. Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 1 байта, а для записи редких символов–более длинные, то суммарный объем файла уменьшится.

Например буквы а, о, е, и – встречаются очень часто в русском тексте, объем каждой буквы равен 1 байт (8 бит), их можно заменить на цифры 0,1,2,3, которые можно разместить в 2-х битах. Т.е. коэффициент сжатия будет равен 25%.Используя метод Хаффмана, буквам можно присвоить кода: и- 11, н- 01; ф – 101; т – 001; в – 000. После кодирования слово «инфинитив» будет записываться как: 110110111011100111000 и иметь длину 21 бит. Так как исходное слово имело 72 (=9*8) бит, получаем сжатие больше чем в три раза.

Обратите внимание, что в коде Хаффмана ни один код символа не является начало любого другого символа. Это позволяет получателю однозначно обновлять код сжатого файла, даже если он не знает длину кода переданного символа. Во время приёма кода получатель сначала отделить первый символ, в нашем примере: 11 – 0110111011100111000. Затем будет выделен второй символ: 11 – 01 – 10111011100111000 и так до полной расшифровки кода: 11 – 01 – 101 – 11 – 01 – 11 – 001 – 11 – 000.

Недостатком метода Хаффмана является то, что к закодированному файлу необходимо прилагать таблицу кодирования символов (у каждого файла она будет своя). Но, если файл достаточно большой, существование таблицы несущественно повлияет на суммарный размер архивного файла.