6.5 Сжатие данных¶

Бинарный код сопоставляет каждому символу строки кодовое слово, состоящее из битов. Мы можем сжать строку с помощью такого кода, заменив каждый символ соответствующим кодовым словом.

Например, рассмотрим следующий код для символов A–D:

Это код фиксированной длины, то есть все кодовые слова имеют одинаковую длину.

Возьмём строку AABADACA. Тогда её кодирование выглядит так:

0000010011001000

Длина получившейся строки равна 16 битам.

Однако строку можно сжать лучше, если использовать код переменной длины, где кодовые слова могут иметь разную длину. Тогда часто встречающимся символам можно назначить короткие коды, а редким — длинные.

Для той же строки один из оптимальных вариантов таков:

Тогда строка AABADACA кодируется так:

00110011101010

Теперь требуется только 14 бит вместо 16. Экономия составила 2 бита.

Оптимальный код — это код, который делает сжатую строку как можно короче.

Почему нельзя допускать префиксы¶

Будем требовать, чтобы ни одно кодовое слово не было префиксом другого. Например, нельзя одновременно иметь коды 10 и 1011.

Причина в том, что после сжатия мы должны уметь однозначно восстановить исходную строку. Если одно кодовое слово является префиксом другого, декодирование может стать неоднозначным.

Например, такой код некорректен:

Тогда сжатую строку 1011 можно было бы интерпретировать либо как AB, либо как C.

Кодирование Хаффмана¶

Кодирование Хаффмана — это жадный алгоритм, который строит оптимальный префиксный код для заданной строки.

Алгоритм строит бинарное дерево на основе частот символов в строке. Кодовое слово каждого символа получается при движении от корня дерева к соответствующему листу:

• переход влево соответствует биту 0;
• переход вправо соответствует биту 1.

Сначала каждый символ представляется отдельной вершиной, вес которой равен числу его вхождений в строку. Затем на каждом шаге берутся две вершины с минимальными весами, объединяются в новую вершину, а её вес равен сумме их весов. Процесс продолжается, пока все вершины не сольются в одно дерево.

Рассмотрим, как это работает для строки AABADACA.

Частоты символов таковы:

• A встречается 4 раза,
• B встречается 1 раз,
• C встречается 1 раз,
• D встречается 1 раз.

Изначально имеем четыре отдельные вершины:

• A: 4
• B: 1
• C: 1
• D: 1

Сначала объединим, например, B и C:

• получаем новую вершину веса 2.

Затем объединим D и вершину веса 2:

• получаем вершину веса 3.

Наконец, объединим вершины весов 4 и 3:

• получаем корень веса 7.

Ниже показано одно из возможных деревьев Хаффмана:

graph TD
    R[7]
    A[A: 4]
    X[3]
    D[D: 1]
    Y[2]
    B[B: 1]
    C[C: 1]

    R -->|0| A
    R -->|1| X
    X -->|0| D
    X -->|1| Y
    Y -->|0| B
    Y -->|1| C

Из этого дерева читаются кодовые слова:

Обратите внимание: если на каком-то шаге есть несколько символов с одинаковой частотой, дерево может получиться другим. Поэтому оптимальных кодов может быть несколько. Но их суммарная длина для данной строки будет одинаково минимальной.

Главное наблюдение¶

Идея Хаффмана очень типична для жадных алгоритмов:

• мы всегда делаем локально выгодный выбор — объединяем два наименее частых символа или поддерева;
• этот выбор в итоге приводит к глобально оптимальному коду.

Чем чаще встречается символ, тем ближе к корню дерева он располагается и тем короче его кодовое слово. Именно это и даёт хорошее сжатие.

Краткий итог¶

• Код фиксированной длины прост, но часто не самый выгодный.
• Код переменной длины позволяет сильнее сжимать строку.
• Чтобы декодирование было однозначным, код должен быть префиксным.
• Алгоритм Хаффмана строит оптимальный префиксный код с помощью жадной стратегии.
• Основа метода — объединять два наименее частых узла, пока не получится одно дерево.