Кодировка Хаффмана

Рассмотрим задачу кодирования данных без потерь. Это означает следующее:

  • есть два множества A и B, называемые входным и выходным алфавитами
  • требуется построить биекцию f между множествами LA и LB конечных последовательностей элементов A и элементов B

Кодирование называется посимвольным, если существует отображение g: A -> LB, для которого f определено как конкатенация результатов g на элементах входной последовательности.

Говоря проще, посимвольное кодирование получается как результат монадного связывания функтора моноидального освобождения. В терминах языка Haskell:

encodeBy: (a -> [b]) -> [a] -> [b]
encodeBy f xs = xs >>= f

Посимвольное кодирование (порождённое отображением g) называется равномерным, если длины всех g-образов одинаковы. Равномерное кодирование называется минимальным, если длины g-образов минимально возможны (для данной пары алфавитов A и B).

Взглянем на наиболее распространённые текстовые кодировки: ASCII, UTF8, UTF16, UTF32. Все они посимвольные; ASCII и UTF32 ещё и равномерные. При этом, если считать, что выходной алфавит состоит только из 0 и 1, то используемая в реальности разновидность ASCII (кодирующая каждый символ восемью битами) не является минимальной (зато лишний восьмой бит можно использовать по своему усмотрению без потери возможности обратного преобразования).

Эксплуатация неравномерности частот

Сообщения, встречающиеся в реальности, обычно сильно неоднородны: некоторые их участки встречаются сильно чаще, чем другие. Например, в текстах русского языка буква «й» встречается существенно реже буквы «а». Этот факт можно эксплуатировать с целью сжатия без потерь.

А именно, если кодировать более частые символы более короткими последовательностями, можно добиться меньшего математического ожидания длины сообщения, чем при минимальном равномерном кодировании. Соответственно, определим эффективность сжатия как отношение математических ожиданий длины кодировки одного символа при равномерном и при рассматриваемом кодировании. Например, эффективность сжатия настоящего (7-битного) ASCII по сравению с 8-битным, используемым в реальности, равна 8/7.

Кодировка Хаффмана — это как раз один из способов сжатия без потерь, эксплуатирующего неравномерность частот.

Дерево кодировки

Напомним, что если выходной алфавит состоит только из 0 и 1, то посимвольные кодировки принято изображать в виде дерева, на котором 0 соответствует перемещению в левый потомок, а 1 — перемещению в правый.

Например, на языке Haskell дерево посимвольной кодировки может выглядеть так:

data Encoding a = ENode (Maybe a) (Encoding a) (Encoding a) | ENull
type Bits = [Bool]

encodingTable :: Encoding a -> [(a, Bits)]
encodingTable e = encode [] e
  where
    encodeChar _ Nothing = []
    encodeChar code (Just c) = [(c, code)]
  
    encode _ ENull = []
    encode prefix (ENode mc l r) =
        encode (prefix ++ [False]) l ++ 
        encode (prefix ++ [True]) r ++
        encodeChar prefix mc

А на C++ — вот так:

template<typename T>
struct EncodingNode {
    bool hasData;
    T data;
    size_t left, right;
};

template<typename T>
using Encoding = std::vector<EncodingNode<T>>;

using Bits = std::vector<bool>;

template<typename T>
using EncodingTable = std::map<T, Bits>;

template<typename T>
EncodingTable<T> encoding_table(Encoding<T> &e) {
    return _encode(Bits{}, e, e.size() - 1);
}

template<typename T> EncodingTable<T> 
_encode(Bits prefix, Encoding<T> &e, size_t index) {
    EncodingTable<T> res;

    if (index == (size_t)(-1)) {
        return res;
    }
    
    if (e[index].hasData) {
        res[e[index].data] = prefix;
    }
    
    Bits left_prefix = prefix;
    left_prefix.push_back(false);
    auto leftTable = _encode(left_prefix, e, e[index].left);
    
    for (auto p: leftTable) { res[p.first] = p.second; }
    
    Bits right_prefix = prefix;
    right_prefix.push_back(true);
    auto rightTable = _encode(right_prefix, e, e[index].right);
    
    for (auto p: rightTable) { res[p.first] = p.second; }
    
    return res;
}

Этот код был лишь иллюстрацией того, как в C++ можно моделировать древообразные структуры без использования указателей (указатели в C++, конечно, полезная штука, но их очень трудно корректно напрямую использовать; особенно при необходимости обеспечить возможность глубокого копирования дерева). Больше мы не будем использовать в этой главе C++, тем более что уже по приведённому куску видно, что он является дословной трансляцией соответствующего кода на Haskell, только существенно более многословной.

Префиксные кодировки

Посимвольная кодировка называется префиксной, если ни один результат кодирования символа не является префиксом другого. Другими словами, в дереве кодировки символы могут находиться только в «листьях».

Префиксные кодировки легко декодируются:

-- у префиксных кодировок проще структура:
data Encoding a = ENode (Encoding a) (Encoding a) | ELeaf a | Enull
type Bits = [Bool]


encodingTable :: Encoding a -> [(a, Bits)]
encodingTable e = encode [] e
  where
    encode _ ENull = []
    encode prefix (ELeaf x) = [(x, prefix)]
    encode prefix (ENode l r) =
        encode (prefix ++ [False]) l ++ 
        encode (prefix ++ [True]) r
        
-- без обработки ошибок декодирования, зато ленивое
decode :: Encoding a -> Bits -> [a]
decode e bits = go e bits
  where
    go pos [] = []
    go ENull _ = [] -- дальше явно нельзя декодировать
    go (ELeaf x) bits = x : go e bits
    go (ENode l _) (False:rest) = go l rest
    go (ENode _ r) (True:rest)  = go r rest

Кодировка Хаффмана

Кодировка Хаффмана строится так (алгоритм здесь короче словесного описания):

import Data.Map as Map

type Frequency = Int

huffmanEncoding :: [(a,Frequency)] -> Encoding a
huffmanEncoding freqs = go forest
  where
    forest = Map.fromList $
        ( \(i,(x,f)) -> ((f,i),ELeaf x) ) <$> zip [0..] freqs
    
    go forest = case Map.minViewWithKey forest of
        Nothing -> ENull
        Just (((f1,_),e1), forest1) -> case Map.minViewWithKey forest1 of
            Nothing -> e1
            Just (((f2,i),e2), forest2) ->
                go $ Map.insert (f1+f2,i) (ENode e1 e2) forest2

Грубо говоря, изначально у нас есть для каждого символа тривиальное дерево, помеченное частотой этого символа. На каждом шаге выбираются два дерева, помеченные наименьшими частотами, и сливаются (с суммированием частот).

Конкретно в вышеприведённой программе метки-частоты были реализованы при помощи упорядоченного мультисловаря (с ключами-частотами). Мультисловарь был сделан из обычного словаря при помощи трюка с уникальными штампами (см. главу про алгоритм Дейкстры).

Кодировка Хаффмана является самой эффективной среди всевозможных префиксных кодировок: это означает, что матожидание (по всем символам) длины кода символа в ней минимально среди всех префиксных кодировок. Доказательство — несложное упражнение на перестроение дерева с полуинвариантом.