> levenshtein | рекурсивный | оптимальный <
// Кодирование Левенштейна — рекурсивный универсальный код с асимптотической оптимальностью
Рекурсивная структура
Рекурсивно кодирует длину длины, пока не достигает 0.
Асимптотически оптимальный
Приближается к теоретическому минимуму для больших чисел.
Универсальный код
Работает для любого неотрицательного целого без параметров.
>> техническая информация
Как работает кодирование Левенштейна:
Кодирование Левенштейна (также называемое кодом Levenstein или L*) рекурсивно кодирует битовую длину числа. Для целого n с бинарной длиной N: рекурсивно кодируется C(N-1), затем добавляется '1', после чего добавляются биты n без ведущей единицы. Рекурсия заканчивается на 0. Это даёт асимптотически оптимальные коды.
Процесс кодирования:
0 → 0 1 → 10 (C(0) + 1 + '') 2 → 110 (C(1) + 1 + '0') 3 → 111 (C(1) + 1 + '1') 4 → 11000 (C(2) + 1 + '00') 5 → 11001 (C(2) + 1 + '01') Рекурсивная структура: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
Зачем использовать кодирование Левенштейна:
- ▸Асимптотическая оптимальность
- ▸Отсутствие предположений о распределении
- ▸Теоретическая важность в теории информации
- ▸Универсальный код для целых чисел
- ▸Хорошо подходит для очень больших чисел
>> часто задаваемые вопросы
Что такое кодирование Левенштейна?
Кодирование Левенштейна (не путать с расстоянием Левенштейна) — это универсальный код, который рекурсивно кодирует длину целых чисел. Разработанный Владимиром Левенштейном, он асимптотически оптимален для больших целых чисел.
Как здесь работает рекурсия?
Код рекурсивно кодирует длину в битах минус один. Чтобы закодировать n с N битами, сначала кодируется (N-1), затем добавляется '1', а затем последние (N-1) битов n. Рекурсия останавливается на 0, который кодируется как '0'.
Левенштейн против кодов Элиаса?
Кодирование Левенштейна асимптотически оптимально, как и Elias Omega, но использует другую рекурсивную структуру. Оно сложнее, чем Elias Gamma/Delta, но даёт лучшую компрессию для очень больших чисел.
Где используется этот код?
Кодирование Левенштейна в основном представляет теоретический интерес в теории информации и колмогоровской сложности. На практике применяется редко, но демонстрирует принципы оптимального универсального кодирования.