// Kodowanie Levenshteina – rekurencyjny kod uniwersalny o asymptotycznej optymalności
Rekurencyjnie koduje długość długości aż do 0.
Zbliża się do teoretycznego minimum dla dużych liczb.
Działa dla każdej nieujemnej liczby całkowitej bez dodatkowych parametrów.
Kodowanie Levenshteina (znane również jako kod Levensteina lub L*) rekurencyjnie koduje długość bitową liczby. Dla liczby całkowitej n o długości binarnej N: rekurencyjnie kodujemy C(N-1), dodajemy '1', a następnie dołączamy n bez wiodącego bitu 1. Rekurencja kończy się na 0. Daje to asymptotycznie optymalne kody.
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') Struktura rekurencyjna: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
Kodowanie Levenshteina (nie mylić z odległością Levenshteina) to kod uniwersalny, który rekurencyjnie koduje długość liczb całkowitych. Opracowany przez Vladimira Levenshteina, jest asymptotycznie optymalny dla dużych liczb całkowitych.
Kod rekurencyjnie koduje długość w bitach pomniejszoną o jeden. Aby zakodować n o długości N bitów, najpierw kodujemy (N-1), dodajemy '1', a następnie ostatnie (N-1) bitów n. Rekurencja kończy się na 0, które jest kodowane jako '0'.
Kodowanie Levenshteina jest asymptotycznie optymalne podobnie jak Elias Omega, ale używa innej struktury rekurencyjnej. Jest bardziej złożone niż Elias Gamma/Delta, ale zapewnia lepszą kompresję dla bardzo dużych liczb.
Kodowanie Levenshteina ma głównie znaczenie teoretyczne w teorii informacji i złożoności Kolmogorowa. Rzadko jest stosowane w praktyce, ale dobrze ilustruje zasady optymalnego kodowania uniwersalnego.