Думаю все, кто так или иначе интересовался сжатием информации или каким-то другим способом кодирования данных - слышали о кодах переменной длины. Я не корифей в этой области, поэтому мои познания ограничены кодами Элиаса и Голомба (причём последнее я только читал на вики и скорее знаю чисто академически).
Пару лет, уже в практическом смысле, а не только в умственных разминках, я стал заниматься изысканиями в области LZSS вариаций сжатия. В частности основными признаками были: окно на предыдущие данные, смещение и длина повтора. Изначально я пользовался фиксированными кодами, но быстро понял, что даже 1 бит без полезной нагрузки загромождал результирующий файл, особенно когда речь шла о тысячах бит. Вот тогда я и стал изобретать что-то с переменной длиной и как всегда, до изобретения очередного велосипеда - узнал о кодах Элиаса. Я ими пользуюсь и сейчас, но при кодировании смещений в окне я стал пользоваться способом который подсмотрел у Эйнара Саукаса в его ZX0.
Не скажу что Эйнар тут первооткрыватель, но он был для меня вдохновителем. Суть в том, что для больших значений имеет смысл представлять число не одним кодом, а делить его на старшую и младшую части - MSB и LSB. Это позволяет для значений MSB пользоваться меньшим числом бит при использовании кодов Элиаса. И это хорошо работает на практических данных.
Но позже я заметил, что например Эйнар пользуется границей для перехода к MSB в 128 (а не в 256 как можно было бы подумать), как он сам пишет - это даёт лучшие результаты (я их проверял практически и это действительно так). И получается, что при кодировании гамма-кодом Элиаса, как мне казалось, мы тратим больше бит, чем могли бы.
Особенность гамма-кода в том, что он быстро растёт, еще и ступенями по 2 бита, что например для значения в 126 уже требует 13 бит для кодирования. И так как меня в первую очередь интересовал интервал 0-127 (мы же помним, что Эйнар и мои тесты выбрали это значение как основную границу), где данные чаще всего равномерно распределены (даже при росте MSB значение LSB продолжает по кругу меняться от 0 до 127), то я стал думать как именно можно изменить представление через те же принципы, что и для кодов Элиаса, но с меньшим расходами битов.
В итоге я придумал вот что. Коды Элиаса симметричны и разделены надвое одним битом. Таким образом код всегда имеет нечётную длину, но число значащих бит справа задаётся числом нулей до разделителя в центре. То есть число бит кодируется не числовым представлением, а просто набором битов, фактически используемый бит "ноль" работает, а бит "единица" - нет.
Я же предлагаю левую часть кодировать фиксированным числом битов, в моём случае тремя битами.
(в таблице пример кодов и разница в количестве битов, минус - это показатель эффективности моего кода)
Число | Гамма-код Элиаса (n-1) | Моя реализация | Число бит |
0 | 1 | 000 | +2 |
1 | 0 1 0 | 001 0 | +1 |
2 | 0 1 1 | 001 1 | +1 |
3 | 00 1 00 | 010 00 | 0 |
4 | 00 1 01 | 010 01 | 0 |
5 | 00 1 10 | 010 10 | 0 |
6 | 00 1 11 | 010 11 | 0 |
7 | 000 1 000 | 011 000 | -1 |
8 | 000 1 001 | 011 001 | -1 |
9 | 000 1 010 | 011 010 | -1 |
10 | 000 1 011 | 011 011 | -1 |
11 | 000 1 100 | 011 100 | -1 |
12 | 000 1 101 | 011 101 | -1 |
13 | 000 1 110 | 011 110 | -1 |
14 | 000 1 111 | 011 111 | -1 |
15 | 0000 1 0000 | 100 0000 | -2 |
16 | 0000 1 0001 | 100 0001 | -2 |
31 | 00000 1 00000 | 101 00000 | -3 |
63 | 000000 1 000000 | 110 000000 | -4 |
126 | 000000 1 111111 | 110 111111 | -4 |
Как видно из таблицы выше - я не использую весь диапазон, а ограничиваюсь только значением до 126, что укладывается в диапазон 0-127, используемый в ZX0 и в моём варианте LZSS. Если сравнивать с кодами Элиаса, то мой вариант проигрывает для значений 0-2, причем только для значений 0, 1, 2 мы видим увеличение значения в битах, остальные значения или равнозначны или всегда даёт меньшее значение.
В итоге мы получаем более равномерный рост размера кода только по одному биту и для значения 64, например, разница между моим кодом и кодом Элиаса составляет уже 4 бита. Например для кодирования части MSB эти коды не подходят, так как на представление малых значений будет очень большой перерасход битов. Для значения MSB 7 это окно размером в 7*128 = 896 байт. Практические тесты показали достоверность этих умозаключений.
Как видно по коду в таблице я в первой части использую три фиксированных бита, которые говорят о размере последующего блока, это позволяет однозначно разделять код, например, 001 0 от кода 010 00, что и требуется для кодов переменной длины.
В тестах на разных типах файлов применение такого кодирования даёт прирост степени сжатия от 2 до 12%. Ну и чтобы не быть голословным я привожу таблицу результата кодирования моей реализацией LZSS на части набора файлов, который я взял из статьи пользователя Introspec.
Размер | Сжато LZSS (Элиас) | Сжато LZSS (авторский) | Эффективность % | |
[ Calgary ] | ||||
obj1 | 21 504 | 11 700 | 10 836 | 8,385 |
paper1 | 53 161 | 24 079 | 21 646 | 10,105 |
progc | 39 611 | 17 051 | 15 318 | 10,163 |
[ Сanterbury ] | ||||
sum | 38 240 | 14 778 | 13 599 | 7,978 |
xargs.1 | 4 227 | 2 252 | 1 996 | 11,367 |
fields.c | 11 150 | 3 950 | 3 511 | 11,113 |
cp.html | 24 603 | 10 181 | 9 240 | 9,242 |
grammar.lsp | 3 721 | 1 549 | 1 394 | 10,006 |
[ Graphics ] | ||||
diver_mercenary_3_(2013).bsc | 11 136 | 3 963 | 3 800 | 4,113 |
craig_stevenson-rewind_to_side_a_(2015).ch$ | 13 831 | 4 877 | 4 587 | 5,946 |
diver_tbk_logo_(2001).img | 13 824 | 3 588 | 3 501 | 2,424 |
agyagos_graphics-robin_(2000).mc | 12 288 | 3 735 | 3 533 | 5,408 |
bfox-dont_go_away_(2010).mg1 | 19 456 | 7 322 | 7 080 | 3,305 |
darklight_when_i_sleep_i_see_demons_(2016).scr | 6 912 | 4 503 | 4 376 | 2,82 |
[ Mixedzx ] | ||||
chronos.bin | 49 152 | 25286 | 23 530 | 6,944 |
bomb.tap | 61 264 | 39 200 | 36 226 | 7,586 |
alterego.tzx | 38 948 | 15 991 | 15 291 | 4,377 |
[ Music ] | ||||
ben_daglish_dark_fusion_(1988).ay | 2 811 | 2 220 | 2 069 | 5,9 |
sairoos_inbetween_(2002).psc | 10 048 | 2 712 | 2 500 | 7,817 |
fatal_snipe_machined.pt2 | 5 339 | 2 241 | 2 069 | 7,675 |
ksa_19_mng.w_(1996).stp | 4 710 | 2 650 | 2 463 | 7,056 |
В заключение - если такой способ представления кодов переменной длины уже имел место, то значит я изобрёл велосипед. Ранее мне на глаза такое не попадалось.
UPD: корректировка первой таблицы и текста
