Генерация кода Хаффмана, который никогда не создает строку «00» при кодировании

Думаю, я бы начал с правила, согласно которому за любым «0» в коде должна следовать «1». Это удовлетворяет ограничению, согласно которому коды не могут содержать «00». Это также позволяет избежать проблемы создания подстроки «00» при кодировании двух соседних символов.

Результирующее дерево кода показано ниже, где

• узлы в областях, заштрихованных красным, представляют собой коды, содержащие «00».
• узлы, содержащие красный X, - это коды, оканчивающиеся на «0».
• зеленые узлы - доступные действительные коды

Обратите внимание, что, поскольку код Хаффмана является кодом без префиксов, выбор одного из допустимых кодов исключает все потомки этого узла. Например, выбор кода «01» исключает все остальные узлы в левой части дерева. Другими словами, выбор «01» делает «01» листом и разрывает два соединения ниже «01».

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

Самый простой способ — вообще не связываться с кодом Хаффмана. Вместо этого выполните постобработку вывода.

Мы начнем с простой битовой начинки. При кодировании возьмите закодированный битовый поток и всякий раз, когда есть 0, вставьте 1 после него. В конце декодирования всякий раз, когда вы видите 0, удалите следующий бит (который будет вставленным 1). Затем выполните обычное декодирование Хаффмана.

Это не оптимально, но отклонение от оптимальности ограничено. Вы можете уменьшить влияние наполнения битами, поменяв местами ветви в каждом узле по мере необходимости, чтобы поместить более низкие вероятности или веса на 0 сторонах.

Это простое вложение битов увеличивает входные данные в среднем в 1,5 раза.

Итак, насколько близка эта простая битовая начинка к оптимальной? Оказывается, количество возможных n-битных паттернов, в которых не встречаются два 0 бита подряд, равно Fn+2, где Fn — nth число Фибоначчи. С такой последовательностью мы можем закодировать не более log2(Fn+2) бит. Тогда оптимальный коэффициент расширения n бит равен n / log2(Fn+2). В пределе больших n это 1 / log2(𝜑), где 𝜑 — золотое сечение. Этот оптимальный коэффициент расширения равен 1,44042.

Так что 1,5 от простой битовой начинки на самом деле не так уж и плохо. Это в пределах 4% от оптимального.

Но мы можем сделать лучше.

Мы можем использовать последовательность Фибоначчи, которая представляет количество возможных закодированных значений для каждого бита, добавленного к последовательности без повторения 0s, для кодирования входных битов. Мы показываем такой подход ниже, хотя для удобства мы избегаем повторяющихся 1 вместо повторяющихся 0. (Просто инвертируйте вывод, чтобы избежать повторения 0s.) Вот пример кода C, который выполняет кодирование и декодирование для ввода и вывода фиксированного размера:

typedef unsigned __int128 u128_t;

// Encode 87 bits to a 125-bit sequence that does not have two 1 bits in a row
// anywhere. Note that if such sequences are concatenated and the high bit of
// the 125 is a 1, then a 0 bit needs to be appended to make it 126 bits. This
// will occur 38.2% of the time (1 / goldenratio^2). The final expansion ratio
// of this encoding is then 125.382 / 87 = 1.44117. The theoretical optimum
// ratio is 1 / lg(goldenratio) = 1.44042. This encoding gets within 0.05% of
// optimal.
u128_t encode87to125(u128_t n) {
    n &= ((u128_t)1 << 87) - 1;
    u128_t e = 0;

    // Fibonacci numbers 126 and 125. (gcc and clang do not support 128-bit
    // literals, so these are assembled, which will occur at compile time.)
    u128_t fn = ((u128_t)0x4f88f2 << 64) | 0x877183a413128aa8u,
           fnm1 = ((u128_t)0x3127c1 << 64) | 0xed0f4dff88ba1575u;
    for (;;) {
        // Encode one bit.
        e <<= 1;
        if (n >= fn) {
            e |= 1;
            n -= fn;
        }

        if (fn == 1)
            // Done when the start of the Fibonacci sequence (1, 1) reached.
            break;

        // Compute the Fibonacci number that precedes fnm1, and move fn and
        // fnm1 both down one in the sequence.
        u128_t fnm2 = fn - fnm1;
        fn = fnm1;
        fnm1 = fnm2;
    }
    return e;
}

// Decode a 125-bit value encoded by encode87to125() back to the orignal 87-bit
// value.
u128_t decode125to87(u128_t e) {
    // Start at the beginning of the Fibonacci sequence (1, 1).
    u128_t d = 0, fn = 1, fnm1 = 1;
    for (;;) {
        // Decode the low bit of e.
        if (e & 1)
            d += fn;
        e >>= 1;

        if (e == 0)
            // Done when there are no more 1 bits in e, since nothing more will
            // be added to d.
            break;

        // Advance fnm1 and fn up one spot in the Fibonacci sequence.
        u128_t fnp1 = fn + fnm1;
        fnm1 = fn;
        fn = fnp1;
    }
    return d;
}

Затем ввод кодируется по 87 бит за раз, а вывод составляет 125 или 126 бит для каждого входного блока, последнее, если 125 бит имеет бит 1 в верхней позиции, и в этом случае 0 необходимо заполнить.

Значения 87 и 125 были выбраны, поскольку они являются наиболее эффективным набором, позволяющим уместить выходные данные в 128 бит. Это дает коэффициент расширения 1,44117, в пределах 0,05% от оптимального. Возможны многие другие варианты. Выходные данные кодируются побитно и декодируются побитно, поэтому нет необходимости накапливать их в виде целого числа. Тогда мы могли бы перейти к 112 битам, закодированным в 161 бит. Или мы могли бы ограничиться 64-битной арифметикой и преобразовать 62 бита в 89 бит (в пределах 0,09% от оптимального).

В конце битовой последовательности оставшиеся биты могут быть расширены до 87 битов со старшими нулями, и тогда закодированные биты будут иметь старшие нули, которые не нужно отправлять. При декодировании заполните последние биты 125 старшими 0s. Если вы не знаете, сколько бит ожидать при декодировании, добавьте к входным данным один старший бит 1 перед кодированием, за которым следуют старшие биты 0. Затем при декодировании просканируйте с конца через 0 биты, чтобы добраться до первого 1 бита, а затем отбросьте все это.

Этот подход к постобработке для удовлетворения ограничений на битовый поток, возможно, предпочтительнее любой попытки изменить код Хаффмана, чтобы он был оптимальным для букв разного веса. Он не только позволяет использовать быстрые и хорошо протестированные реализации алгоритма Хаффмана как есть, но также будет работать с любой схемой энтропийного кодирования, будь то алгоритм Хаффмана, арифметические или асимметричные системы счисления.