Как мне представить вывод LZW в байтах?

Question

Я нашел реализацию алгоритма LZW, и мне было интересно, как я могу представить его вывод, который представляет собой список int, в байтовый массив.

Я пробовал с одним байтом, но в случае длинных входов словарь имеет более 256 записей, и поэтому я не могу преобразовать.

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

Как я могу оптимизировать это?

Answer 1

Как биты, а не байты. Вам просто нужна простая подпрограмма, которая записывает произвольное количество бит в поток байтов. Он просто сохраняет однобайтовый буфер, в который вы помещаете биты, пока у вас не будет восьми битов. Затем запишите байты, очистите буфер и начните все сначала. Процесс перевернут с другой стороны.

Когда вы доберетесь до конца, просто запишите последний байтовый буфер, если он не пустой, с остальными битами, установленными в ноль.

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

Answer 2

В своей статье 1984 года о LZW Т. А. Уэлч фактически не указал, как "кодировать коды", но описал отображение "строк входных символов в коды фиксированной длины", продолжая "использование 12-битных кодов является обычным явлением". (Позволяет биективное отображение между тремя октетами и двумя кодами.)
BSD compress(1) Команда буквально не следовала, но ввела заголовок, интересной частью которого является спецификация максимального числа битов, используемых для кодирования выходного кода LZW, что позволяет декомпрессорам соответствующим образом определять размер таблиц декомпрессии или рано или неудачно и контролируемым образом. (Но для самого первого) Коды были закодированы только необходимым количеством целых битов, начиная с 9.
Альтернативой может быть использование арифметического кодирования, особенно если использование модели, отличной от каждого кода, в равной степени вероятно.