От кода Голомба и Элиаса до своей реализации24.05.2024 13:30

Думаю все, кто так или иначе интересовался сжатием информации или каким-то другим способом кодирования данных — слышали о кодах переменной длины. Я не корифей в этой области, поэтому мои познания ограничены кодами Элиаса и Голомба (причём последнее я только читал на вики и скорее знаю чисто академически).

Пару лет, уже в практическом смысле, а не только в умственных разминках, я стал заниматься изысканиями в области LZSS вариаций сжатия. В частности основными признаками были: окно на предыдущие данные, смещение и длина повтора. Изначально я пользовался фиксированными кодами, но быстро понял, что даже 1 бит без полезной нагрузки загромождал результирующий файл, особенно когда речь шла о тысячах бит. Вот тогда я и стал изобретать что-то с переменной длиной и как всегда, до изобретения очередного велосипеда — узнал о кодах Элиаса. Я ими пользуюсь и сейчас, но при кодировании смещений в окне я стал пользоваться способом который подсмотрел у Эйнара Каускаса в его ZX0.

Не скажу что Эйнар тут первооткрыватель, но он был для меня вдохновителем. Суть в том, что для больших значений имеет смысл представлять число не одним кодом, а делить его на старшую и младшую части — MSB и LSB. Это позволяет для значений MSB пользоваться меньшим числом бит при использовании кодов Элиаса. И это хорошо работает на практических данных.

Но позже я заметил, что например Эйнар пользуется границей для перехода к MSB в 128 (а не в 256 как можно было бы подумать), как он сам пишет — это даёт лучшие результаты (я их проверял практически и это действительно так). И получается, что при кодировании гамма-кодом Элиаса, как мне казалось, мы тратим больше бит, чем могли бы.

Особенность гамма-кода в том, что он быстро растёт, еще и ступенями по 2 бита, что например для значения в 126 уже требует 13 бит для кодирования. И так как меня в первую очередь интересовал интервал 0–127 (мы же помним, что Эйнар и мои тесты выбрали это значение как основную границу), где данные чаще всего равномерно распределены (даже при росте MSB значение LSB продолжает по кругу меняться от 0 до 127), то я стал думать как именно можно изменить представление через те же принципы, что и для кодов Элиаса, но с меньшим расходами битов.

В итоге я придумал вот что. Коды Элиаса симметричны и разделены надвое одним битом. Таким образом код всегда имеет нечётную длину, но число значащих бит справа задаётся числом нулей до разделителя в центре. То есть число бит кодируется не числовым представлением, а просто набором битов, фактически используемый бит «ноль» работает, а бит «единица» — нет.

Я же предлагаю левую часть кодировать фиксированным числом битов, в моём случае тремя битами.

(в таблице пример кодов и разница в количестве битов, минус — это показатель эффективности моего кода)

Как видно из таблицы выше — я не использую весь диапазон, а ограничиваюсь только значением до 126, что укладывается в диапазон 0–127, используемый в ZX0 и в моём варианте LZSS. Если сравнивать с кодами Элиаса, то мой вариант проигрывает для значений 0–7, причем только для значений 0, 1, 2, 3 и 7 мы видим увеличение значения в битах, остальные значения или равнозначны или всегда даёт меньшее значение.

В итоге мы получаем более равномерный рост размера кода только по одному биту и для значения 126, например, разница между моим кодом и кодом Элиаса составляет уже 4 бита. Например для кодирования части MSB эти коды не подходят, так как на представление малых значений будет очень большой перерасход битов. Для значения MSB 7 это окно размером в 7×128 = 896 байт. Практические тесты показали достоверность этих умозаключений.

Как видно по коду в таблице я в первой части использую три фиксированных бита, которые говорят о размере последующего блока, это позволяет однозначно разделять код, например, 001 0 от кода 010 00, что и требуется для кодов переменной длины.

В тестах на разных типах файлов применение такого кодирования даёт прирост степени сжатия от 2 до 12%. Ну и чтобы не быть голословным я привожу таблицу результата кодирования моей реализацией LZSS на части набора файлов, который я взял из статьи пользователя Introspec.

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

© Habrahabr.ru