Как записать уже сгенерированные коды Хаффмана в файл в Rust

Там куча вопросов.

Код Хаффмана для символа имеет длину, измеряемую в битах. Когда вы записываете файл, вы записываете его в байтах, где каждый байт состоит из восьми бит. Так как же соединить эти два? Вам нужно рассматривать поток байтов в файле как поток, в восемь раз превышающий количество битов. Вам нужно будет решить, является ли первый бит вашего битового потока старшим битом первого байта или наименее значимым битом первого байта. Давайте выберем самое значимое.

В вашем коде вы используете целое число без знака в качестве битового буфера. Допустим, это 64-битное целое число, u64. У вас есть код Хаффмана, который вы хотите написать, длиной в k бит. Используйте битовые операции или и сдвиг, чтобы поместить эти биты в буфер целочисленных битов, сдвигая уже находящиеся там биты. Также увеличьте счетчик, который отслеживает количество битов в буфере, инициализированном нулем. Так:

    buf = (buf << k) | code;
    bits += k;

где code — целое число без знака с кодом Хаффмана в младших битах k и нулями в битах выше него.

Если вы продолжите это делать, вы в конечном итоге потеряете биты верхней части буфера. Здесь мы сопоставляем поток байтов, который представляет собой файл. Всякий раз, когда количество бит в буфере равно восьми и более, нам достаточно, чтобы записать байт. Так что продолжайте записывать байты, оставляя незаписанными не более семи битов в буфере:

    while bits >= 8 {
        bits -= 8;
        put(buf >> bits);
    }

где put() записывает один байт в ваш вывод. Делайте это каждый раз, когда помещаете биты в битовый буфер.

64-битный буфер допускает использование до 57-битных кодов. Это должно охватывать любое кодирование, которое вы делаете, поскольку для генерации 58-битного кода вам потребуется, чтобы общее количество частот составляло не менее 2 139 295 485 798. Коды Хаффмана должны генерироваться одновременно на фрагментах данных, чтобы коды могли адаптироваться к изменениям в статистике данных.

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

    // flush
    if bits != 0 {
        put(buf << (8 - bits));
        bits = 0;
    }

Как повернуть это вспять, чтобы прочитать байты из файла и использовать их в виде потока битов, остается в качестве упражнения для читателя.

Теперь другой вопрос. Если вы просто запишете в файл коды Хаффмана, получатель файла не будет знать, как интерпретировать эти биты. Им необходимо описание кода Хаффмана перед данными, закодированными Хаффманом. Так как же это записывается на выходе?

Существует множество способов кодирования кода Хаффмана в выходные данные. Возможно, самый простой и относительно компактный способ — пройти рекурсивно сверху по дереву, которое вы построили, записывая бит 0 для каждой встреченной ветви или бит 1, за которым следуют биты, описывающие символ на этом листе (например, восемь битов). если вы Хаффман, кодирующий серию байтов). Это самозавершающееся описание, и поэтому за ним сразу же могут следовать данные, закодированные Хаффманом. Вы можете использовать описанный выше подход для записи этого потока битов на выход.

Меньшее представление можно получить, уделив немного больше внимания самому коду Хаффмана, используя «канонический» код Хаффмана. Для этого кода вы сохраняете только то количество битов, которое необходимо для кода для каждого символа. Затем вы выбрасываете дерево. Коды Хаффмана затем присваиваются символам в порядке от самых коротких кодов к самым длинным кодам, а затем внутри каждой длины путем лексикографического упорядочения символов. Тогда вам нужно будет отправить получателю только эти длины, а не описание всего дерева. Пример такой схемы вы можете найти в описании формата сжатых данных deflate.

Наконец, вам нужно быть осторожным с форматом сжатых данных и этими битами заполнения нулями 0–7 в конце последнего байта. Как получатель узнает, когда битовый поток закончится? Эти последние несколько нулевых битов с таким же успехом можно интерпретировать как один или несколько символов, если в вашем коде Хаффмана есть несколько коротких кодов по несколько битов каждый. Чтобы предотвратить это, вы можете либо добавить к своим данным количество символов, которые необходимо декодировать, либо добавить к тому, что вы кодируете, символ «конца потока», имеющий частоту, равную единице. Завершите трансляцию кодом этого символа. Тогда декодер будет знать, что нужно остановиться, когда получит этот код.