Гамма-код Элиаса
Поделись знанием:
– Что ты так мрачен? – спросил Несвицкий, заметив бледное с блестящими глазами лицо князя Андрея.
– Веселиться нечему, – отвечал Болконский.
В то время как князь Андрей сошелся с Несвицким и Жерковым, с другой стороны коридора навстречу им шли Штраух, австрийский генерал, состоявший при штабе Кутузова для наблюдения за продовольствием русской армии, и член гофкригсрата, приехавшие накануне. По широкому коридору было достаточно места, чтобы генералы могли свободно разойтись с тремя офицерами; но Жерков, отталкивая рукой Несвицкого, запыхавшимся голосом проговорил:
– Идут!… идут!… посторонитесь, дорогу! пожалуйста дорогу!
Генералы проходили с видом желания избавиться от утруждающих почестей. На лице шутника Жеркова выразилась вдруг глупая улыбка радости, которой он как будто не мог удержать.
– Ваше превосходительство, – сказал он по немецки, выдвигаясь вперед и обращаясь к австрийскому генералу. – Имею честь поздравить.
Он наклонил голову и неловко, как дети, которые учатся танцовать, стал расшаркиваться то одной, то другой ногой.
Генерал, член гофкригсрата, строго оглянулся на него; не заметив серьезность глупой улыбки, не мог отказать в минутном внимании. Он прищурился, показывая, что слушает.
– Имею честь поздравить, генерал Мак приехал,совсем здоров,только немного тут зашибся, – прибавил он,сияя улыбкой и указывая на свою голову.
Генерал нахмурился, отвернулся и пошел дальше.
– Gott, wie naiv! [Боже мой, как он прост!] – сказал он сердито, отойдя несколько шагов.
Несвицкий с хохотом обнял князя Андрея, но Болконский, еще более побледнев, с злобным выражением в лице, оттолкнул его и обратился к Жеркову. То нервное раздражение, в которое его привели вид Мака, известие об его поражении и мысли о том, что ожидает русскую армию, нашло себе исход в озлоблении на неуместную шутку Жеркова.
– Если вы, милостивый государь, – заговорил он пронзительно с легким дрожанием нижней челюсти, – хотите быть шутом , то я вам в этом не могу воспрепятствовать; но объявляю вам, что если вы осмелитесь другой раз скоморошничать в моем присутствии, то я вас научу, как вести себя.
Несвицкий и Жерков так были удивлены этой выходкой, что молча, раскрыв глаза, смотрели на Болконского.
– Что ж, я поздравил только, – сказал Жерков.
– Я не шучу с вами, извольте молчать! – крикнул Болконский и, взяв за руку Несвицкого, пошел прочь от Жеркова, не находившего, что ответить.
– Ну, что ты, братец, – успокоивая сказал Несвицкий.
– Как что? – заговорил князь Андрей, останавливаясь от волнения. – Да ты пойми, что мы, или офицеры, которые служим своему царю и отечеству и радуемся общему успеху и печалимся об общей неудаче, или мы лакеи, которым дела нет до господского дела. Quarante milles hommes massacres et l'ario mee de nos allies detruite, et vous trouvez la le mot pour rire, – сказал он, как будто этою французскою фразой закрепляя свое мнение. – C'est bien pour un garcon de rien, comme cet individu, dont vous avez fait un ami, mais pas pour vous, pas pour vous. [Сорок тысяч человек погибло и союзная нам армия уничтожена, а вы можете при этом шутить. Это простительно ничтожному мальчишке, как вот этот господин, которого вы сделали себе другом, но не вам, не вам.] Мальчишкам только можно так забавляться, – сказал князь Андрей по русски, выговаривая это слово с французским акцентом, заметив, что Жерков мог еще слышать его.
Гамма-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее.
Описание алгоритма
Чтобы закодировать число:
- Записать его в двоичной форме.
- Перед двоичным представлением числа дописать нули. Количество нулей на единицу меньше количества битов двоичного представления числа.
Аналогичный способ описания этого процесса:
- Выделить из целого числа старший значащий бит (самую большую степень 2, которую число включает — 2N) и младшие N бит.
- Записать N в унарном коде; то есть N нолей, за которыми следует единица.
- Дописать N младших двоичных цифр числа следом за этим унарным кодом.
Начало кодирования:
| Число | Значение | Кодирование | Предполагаемая вероятность |
|---|---|---|---|
| 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. Пусть N — количество этих нулей.
- Принимая во внимание единицу, которая станет первым (самая значащим) битом целого числа, со значением 2N, считать оставшиеся N цифр целого числа.
Гамма-кодирование используется в приложениях, где самое большое значение не может быть известно заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто чем большие.
Обобщение
Гамма-кодирование не подходит для кодирования нулевых значений или отрицательных чисел. Единственный способ закодировать ноль — прибавить к нему 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);
}
}
}См. также
Напишите отзыв о статье "Гамма-код Элиаса"
Отрывок, характеризующий Гамма-код Элиаса
Взволнованный и раздраженный этими мыслями, князь Андрей пошел в свою комнату, чтобы написать отцу, которому он писал каждый день. Он сошелся в коридоре с своим сожителем Несвицким и шутником Жерковым; они, как всегда, чему то смеялись.– Что ты так мрачен? – спросил Несвицкий, заметив бледное с блестящими глазами лицо князя Андрея.
– Веселиться нечему, – отвечал Болконский.
В то время как князь Андрей сошелся с Несвицким и Жерковым, с другой стороны коридора навстречу им шли Штраух, австрийский генерал, состоявший при штабе Кутузова для наблюдения за продовольствием русской армии, и член гофкригсрата, приехавшие накануне. По широкому коридору было достаточно места, чтобы генералы могли свободно разойтись с тремя офицерами; но Жерков, отталкивая рукой Несвицкого, запыхавшимся голосом проговорил:
– Идут!… идут!… посторонитесь, дорогу! пожалуйста дорогу!
Генералы проходили с видом желания избавиться от утруждающих почестей. На лице шутника Жеркова выразилась вдруг глупая улыбка радости, которой он как будто не мог удержать.
– Ваше превосходительство, – сказал он по немецки, выдвигаясь вперед и обращаясь к австрийскому генералу. – Имею честь поздравить.
Он наклонил голову и неловко, как дети, которые учатся танцовать, стал расшаркиваться то одной, то другой ногой.
Генерал, член гофкригсрата, строго оглянулся на него; не заметив серьезность глупой улыбки, не мог отказать в минутном внимании. Он прищурился, показывая, что слушает.
– Имею честь поздравить, генерал Мак приехал,совсем здоров,только немного тут зашибся, – прибавил он,сияя улыбкой и указывая на свою голову.
Генерал нахмурился, отвернулся и пошел дальше.
– Gott, wie naiv! [Боже мой, как он прост!] – сказал он сердито, отойдя несколько шагов.
Несвицкий с хохотом обнял князя Андрея, но Болконский, еще более побледнев, с злобным выражением в лице, оттолкнул его и обратился к Жеркову. То нервное раздражение, в которое его привели вид Мака, известие об его поражении и мысли о том, что ожидает русскую армию, нашло себе исход в озлоблении на неуместную шутку Жеркова.
– Если вы, милостивый государь, – заговорил он пронзительно с легким дрожанием нижней челюсти, – хотите быть шутом , то я вам в этом не могу воспрепятствовать; но объявляю вам, что если вы осмелитесь другой раз скоморошничать в моем присутствии, то я вас научу, как вести себя.
Несвицкий и Жерков так были удивлены этой выходкой, что молча, раскрыв глаза, смотрели на Болконского.
– Что ж, я поздравил только, – сказал Жерков.
– Я не шучу с вами, извольте молчать! – крикнул Болконский и, взяв за руку Несвицкого, пошел прочь от Жеркова, не находившего, что ответить.
– Ну, что ты, братец, – успокоивая сказал Несвицкий.
– Как что? – заговорил князь Андрей, останавливаясь от волнения. – Да ты пойми, что мы, или офицеры, которые служим своему царю и отечеству и радуемся общему успеху и печалимся об общей неудаче, или мы лакеи, которым дела нет до господского дела. Quarante milles hommes massacres et l'ario mee de nos allies detruite, et vous trouvez la le mot pour rire, – сказал он, как будто этою французскою фразой закрепляя свое мнение. – C'est bien pour un garcon de rien, comme cet individu, dont vous avez fait un ami, mais pas pour vous, pas pour vous. [Сорок тысяч человек погибло и союзная нам армия уничтожена, а вы можете при этом шутить. Это простительно ничтожному мальчишке, как вот этот господин, которого вы сделали себе другом, но не вам, не вам.] Мальчишкам только можно так забавляться, – сказал князь Андрей по русски, выговаривая это слово с французским акцентом, заметив, что Жерков мог еще слышать его.
