Теория информации

1 байт (8 бит), то длина исходной последовательности равна: 23  8 бит = 184 бита, а коэффициент сжатия имеет значение: 42 бит / 184 бита  0.228. Необходимо отметить, что энтропия исходной последовательности равна 1.72 бита. Эта величина близка средней длине кода, равной 1.82 бита. Именно поэтому метод Хаффмана относится к энтропийным методам сжатия. На практике часто используется адаптивный вариант метода Хаффмана , при реализации которого частоты символов уточняются по мере сжатия. В отличие от первоначального алгоритма здесь требуется всего один проход по исходному файлу. Для этого вводится дополнительный символ ESC , который при декодировании показывает, что за ним следует несжатый символ. Символ ESC всегда имеет частоту 1 и размещается в конце списка. Алгоритм адаптивного сжатия по методу Хаффмана : 1. Создать список, состоящий только из одного символа ESC с частотой 1. 2. Прочитать символ последовательности. Если символ отсутствует в списке, то перейти к п. 3, иначе – к п. 4. 3. Присвоить код символу ESC , выдать этот код, выдать прочитанный символ, добавить его в конец списка перед символом ESC с частотой 1 и перейти к п. 2.