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

5da77d7c523e50905d801391c8b4a269.png

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

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

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

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

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

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

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

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

Число

Гамма-код Элиаса

Моя реализация

Число бит

0

нет

000

+3

1

1

001 0

+3

2

0 1 0

001 1

+1

3

0 1 1

010 00

+2

4

00 1 00

010 01

0

5

00 1 01

010 10

0

6

00 1 10

010 11

0

7

00 1 11

011 000

+1

8

000 1 000

011 001

-1

9

000 1 001

011 010

-1

10

000 1 010

011 011

-1

11

000 1 011

011 100

-1

12

000 1 100

011 101

-1

13

000 1 101

011 110

-1

14

000 1 110

011 111

-1

15

000 1 111

100 0000

0

16

0000 1 0000

100 0001

-2

31

0000 1 1111

101 00000

-1

63

00000 1 11111

110 000000

-2

126

000000 1 111110

110 111111

-4

Как видно из таблицы выше — я не использую весь диапазон, а ограничиваюсь только значением до 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.

Размер

Сжато 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

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

© Habrahabr.ru