Универсальный код (сжатие данных)
-
Основы универсального кодирования
- Универсальный код для целых чисел преобразует числа в двоичные слова с постоянным коэффициентом ожидаемой длины.
- Код асимптотически оптимален, если его соотношение с оптимальной ожидаемой длиной ограничено информационной энтропией.
-
Применение и ограничения универсальных кодов
- Универсальные коды используются для эффективного упорядочивания сообщений по вероятности.
- Они не подходят для точно известных распределений и не оптимальны для всех практических случаев.
-
Примеры универсальных кодов
- Гамма-кодирование Элиаса, дельта-кодирование Элиаса и кодировка Exp-Голомба являются универсальными кодами.
- Кодирование по Фибоначчи и кодировка Левенштейна также являются универсальными методами.
-
Связь с практическим сжатием
- Кодирование Хаффмана и арифметическое кодирование обеспечивают лучшее сжатие, но универсальные коды полезны в случаях, когда вероятности сообщений неизвестны.
-
Сравнение с другими кодами
- Универсальные коды проще и быстрее в кодировании и декодировании, чем коды Хаффмана и арифметическое кодирование.
-
Распределение вероятностей и оптимизация
- Универсальные коды имеют неявное распределение, соответствующее степенному закону.
- Для некоторых распределений, таких как экспоненциальное, код Голомба является оптимальным.
-
Дополнительные ресурсы
- Ссылки на литературу и статьи по универсальным кодам доступны в книге Дэвида Маккея и в других англоязычных источниках.
Полный текст статьи: