24-05-2023
Гамма-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее.
Содержание |
Чтобы закодировать число:
Аналогичный способ описания этого процесса:
Начало кодирования:
Число | Значение | Кодирование | Предполагаемая вероятность |
---|---|---|---|
1 | 20 + 0 | 1 | 1/2 |
2 | 21 + 0 | 01 0 | 1/8 |
3 | 21 + 1 | 01 1 | 1/8 |
4 | 2² + 0 | 001 00 | 1/32 |
5 | 2² + 1 | 001 01 | 1/32 |
6 | 2² + 2 | 001 10 | 1/32 |
7 | 2² + 3 | 001 11 | 1/32 |
8 | 2³ + 0 | 0001 000 | 1/128 |
9 | 2³ + 1 | 0001 001 | 1/128 |
10 | 2³ + 2 | 0001 010 | 1/128 |
11 | 2³ + 3 | 0001 011 | 1/128 |
12 | 2³ + 4 | 0001 100 | 1/128 |
13 | 2³ + 5 | 0001 101 | 1/128 |
14 | 2³ + 6 | 0001 110 | 1/128 |
15 | 2³ + 7 | 0001 111 | 1/128 |
16 | 24 + 0 | 00001 0000 | 1/512 |
17 | 24 + 1 | 00001 0001 | 1/512 |
… |
Распределение предполагаемых вероятностей для кодов добавлено для ясности.
Чтобы декодировать закодированное гамма-кодом Элиаса число следует:
Гамма-кодирование используется в приложениях, где самое большое значение не может быть известно заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто чем большие.
Гамма-кодирование не подходит для кодирования нулевых значений или отрицательных чисел. Единственный способ закодировать ноль — прибавить к нему 1 до кодирования и отнять после декодирования. Другой способ — приписать в начале любой ненулевой код с 1 , а затем кодировать ноль как простой 0. Единственный способ закодировать все целые числа — перед началом кодирования установить биекцию (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …).
// Кодирование void eliasGammaEncode(char* source, char* dest) { IntReader intreader(source); BitWriter bitwriter(dest); while(intreader.hasLeft()) { int num = intreader.getInt(); int l = log2(num); for (int a=0; a < l; a++) { bitwriter.putBit(false); //поместить нули, чтобы показать, сколько бит будут следовать } bitwriter.putBit(true); //пометить конец нолей for (int a=0; a < l; a++) //записать биты как простые двоичные числа { if (num & (1 << a)) bitwriter.putBit(true); else bitwriter.putBit(false); } } intreader.close(); bitwriter.close(); } // Декодирование void eliasGammaDecode(char* source, char* dest) { BitReader bitreader(source); BitWriter bitwriter(dest); int numberBits = 0; while(bitreader.hasLeft()) { while(!bitreader.getBit() || bitreader.hasLeft())numberBits++; //продолжить чтение пока не встретится единица... int current = 0; for (int a=0; a < numberBits; a++) //прочитать numberBits битов { if (bitreader.getBit()) current += 1 << a; } //записать его как 32-битное число current = current | ( 1 << numberBits ) ;//последний бит не декодируется! for (int a=0; a < 32; a++) //прочитать numberBits битов { if (current & (1 << a)) bitwriter.putBit(true); else bitwriter.putBit(false); } } }
Гамма-код Элиаса.