Гамма-кодирование Элиаса
-
Основы гамма-кода Элиаса
- Гамма-код Элиаса — универсальный код для кодирования положительных целых чисел.
- Используется для кодирования чисел, верхняя граница которых неизвестна.
-
Процесс кодирования
- Для кодирования числа x ≥ 1 вычисляется N = ⌊log2x⌋.
- Выписываются N нулей и добавляется двоичная форма x, дополненная (N+1) битами.
- Эквивалентно кодированию N в унарном виде и добавлением оставшихся N двоичных цифр из x.
- Для кодирования используется 2N+1 бит.
-
Процесс расшифровки
- Для расшифровки считываются 0 секунд из потока до первой единицы.
- Полученное количество нулей N используется для определения первой цифры числа.
- Остальные N цифр считываются для получения исходного числа.
-
Применение и обобщения
- Гамма-кодирование используется в приложениях с неизвестными максимальными значениями и для сжатия данных с частым появлением малых значений.
- Является составной частью дельта-кода Элиаса.
- Не кодирует ноль или отрицательные числа, но есть способы обработки этих случаев.
- Можно кодировать все целые числа, сопоставляя их с другими числами.
- Экспоненциально-голомбовское кодирование расширяет гамма-код на числа с более «плоским» распределением.
-
Дополнительные коды Элиаса
- Упоминаются кодировка Элиаса delta для целых страниц и кодировка Элиаса Омеги для положительных целых чисел.
- Упоминается формат чисел Posit для описания перенаправлений на компьютерных страницах.
-
Рекомендации
- Предлагается дальнейшее чтение по теме.
Полный текст статьи: