// Elias Omega — асимптотически оптимальный код для целых чисел произвольного размера
При больших числах приближается к теоретическому минимуму длины.
Элегантно кодирует длины рекурсивным образом.
Работает для любого положительного целого числа без параметров.
Elias Omega рекурсивно кодирует длину числа, пока значение не станет равным 1. Начиная с n, кодируем log₂(n), затем log₂(log₂(n)) и продолжаем до 1. Код состоит из этих значений в обратном порядке и заканчивается 0. Это даёт log(n) + log(log(n)) + log(log(log(n))) + ... бит.
n=16: 16 → двоичный: 10000 (длина 5) 5 → двоичный: 101 (длина 3) 3 → двоичный: 11 (длина 2) 2 → двоичный: 10 (длина 2) 1 → стоп Построение кода с конца: Начинаем с 0 (завершающий бит) Добавляем спереди 10 (кодирует 2) Добавляем спереди 11 (кодирует 3) Добавляем спереди 101 (кодирует 5) Добавляем спереди 10000 (кодирует 16) Результат: 10 11 101 10000 0 Сравнение эффективности: n=100: Gamma=13, Delta=12, Omega=10 бит n=1000: Gamma=19, Delta=16, Omega=14 бит
Elias Omega — самый сложный код из семейства Элиаса. Он использует рекурсивное кодирование длины для достижения асимптотической оптимальности. Кодируется длина представления, затем длина этой длины и так далее до 1, что делает код очень эффективным для очень больших целых чисел.
Для малых чисел (< 10) чаще всего лучше подходит Gamma. Для средних значений (10–1000) Delta даёт более короткие коды. Для больших чисел (> 1000) преимущество Omega становится всё более заметным. Omega использует итерации log*(n) и обеспечивает оптимальное асимптотическое поведение.
Код называется асимптотически оптимальным, если отношение его длины к теоретическому минимуму стремится к 1 при n → ∞. Для Omega выполняется: length(n)/log₂(n) → 1.
Несмотря на теоретические преимущества, Omega сложнее реализовать и декодировать. Для практических данных с ограниченным диапазоном значений более простые коды, такие как Exp-Golomb или Rice, часто удобнее. Omega особенно полезен в теоретическом анализе и в задачах с неограниченными целыми числами.