36. Коды Хаффмена. Общие сведения. Префиксные к..


36. Коды Хаффмена. Общие сведения. Префиксные коды.
Коды Хаффмена:
Используются при сжатии информации (в тип. ситуации выигрыш 20-90%). Алгоритм Хаффмена находит оптимальные коды символов исходя из частоты использования этих символов в сжимаемом тексте.
Файл из 100000 символов:
a b c d e f
В тысячах 45 13 12 16 9 5
Равномерный код 000 001 010 011 100 101
Неравномерный код (Хаффмена) 0 101 100 111 1101 1100
1) 100000*3 = 300000
2) 45*1+13*3+12*3+16*3+9*4+5*4 = 224000
Необходимо построить двоичный код, в котором каждый символ представляется в виде конечной последовательности битов. Будем называть его кодовым словом.
При использовании равномерного кода необходимо потратить, как минимум три бита на каждый символ.
Неравномерный код будет экономнее, если часто встречающиеся символы закодировать короткой последовательностью битов, а редко встречающиеся - длинными.
Неравномерный бинарный код можно представить в виде бинарного дерева:

Префиксные коды:
Префиксные коды - коды, в которых из двух кодовых слов (последовательность битов) представляющих различные коды ни одна не является префиксом другой
Префикс - последовательность битов, из которой данный код получается приписыванием другого кода. Для префиксного кода декодирование выполняется слева направо. Первый символ текста, закодированного префиксным кодом определяется однозначно, так как кодирующая его последовательность не может быть началом кода какого-то иного символа (согласно определению). Найдя этот первый символ, и отбросив кодировавшую его последовательность битов, повторяем процесс для оставшихся битов. И так далее.
0 101 0 0 1100 100 11
101. 0. 0. 1100. 100
a b a a f c
Для эффективной реализации декодирования надо хранить информацию о коде в удобной форме. Одна из возможностей представить код в виде бинарного дерева, листья которого соответствуют кодируемым символам, при этом путь от вершины дерева до кодируемого символа определяет кодирующую последовательность. Поворот налево дает ноль, поворот направо дает единицу. Оптимальному коду всегда соответствует бинарное дерево, в котором вершина, не являющаяся листом, имеет два поддерева, в отличие от неравномерного кода.
С – мн-во символов.
|c| - кол-во символов.
с (= С – символ.f(c) – частота появления символа.
h+(c) – уровень символа или размер кодового слова.
Bt=c∈Cfch+(c)- кол-во битов.

Приложенные файлы

  • docx 15638589
    Размер файла: 47 kB Загрузок: 0

Добавить комментарий