// Кодирование Левенштейна — рекурсивный универсальный код с асимптотической оптимальностью
Рекурсивно кодирует длину длины, пока не достигает 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, но даёт лучшую компрессию для очень больших чисел.
Кодирование Левенштейна в основном представляет теоретический интерес в теории информации и колмогоровской сложности. На практике применяется редко, но демонстрирует принципы оптимального универсального кодирования.