|
|
|
23 января 2011
Оглавление:
1. Гамма-код Элиаса
2. Обобщение
это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее.
Описание алгоритма
Чтобы закодировать число:
- Записать его в двоичной форме.
- Перед двоичным представлением числа дописать нули. Количество нулей на единицу меньше количества битов двоичного представления числа.
Аналогичный способ описания этого процесса:
- Разделить целое число на самую большую степень 2, которую оно включает, и на оставшиеся N двоичных цифр от данного целого числа.
- Записать N в унарном коде; то есть N нолей, следующих за единицей.
- Присоединить оставшиеся N двоичных цифр к этому представлению N.
Начало кодирования:
| Число |
Значение |
Кодирование |
Предполагаемая
вероятность |
| 1 |
2 + 0 |
1 |
1/2 |
| 2 |
2 + 0 |
01 0 |
1/8 |
| 3 |
2 + 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 |
2 + 0 |
00001 0000 |
1/512 |
| 17 |
2 + 1 |
00001 0001 |
1/512 |
| … |
|
|
|
Распределение предполагаемых вероятностей для кодов добавлено для ясности.
Чтобы декодировать закодированное гамма-кодом Элиаса число следует:
- Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.
- Принимая во внимание единицу, которая была достигнута как первая цифра целого числа, со значением 2, считать оставшиеся N цифр целого числа.
Гамма-кодирование используется в приложениях, где самое большое значение не может быть известно заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто чем большие.
Просмотров: 2242
|