// Levenshtein Kodlama - asimptotik olarak optimal özyinelemeli evrensel kod
0'a ulaşıncaya kadar uzunluğun uzunluğunu özyinelemeli olarak kodlar.
Büyük tamsayılar için teorik minimuma yaklaşır.
Ek parametre olmadan herhangi bir negatif olmayan tamsayı için çalışır.
Levenshtein kodlama (Levenstein veya L* kodu olarak da bilinir) bir sayının bit uzunluğunu özyinelemeli olarak kodlar. İkilik uzunluğu N olan tamsayı n için: önce C(N-1) özyinelemeli olarak kodlanır, ardından '1' eklenir ve daha sonra baştaki 1 biti olmadan n'nin kalan bitleri eklenir. Özyineleme 0'da sonlanır. Bu da asimptotik olarak optimal kodlar üretir.
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') Özyinelemeli yapı: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
Levenshtein kodlama (Levenshtein mesafesiyle karıştırılmamalıdır), tamsayıların uzunluğunu özyinelemeli olarak kodlayan evrensel bir koddur. Vladimir Levenshtein tarafından geliştirilmiş olup, büyük tamsayılar için asimptotik olarak optimaldir.
Kod, bit uzunluğu eksi bir değerini özyinelemeli olarak kodlar. N bitlik n sayısını kodlamak için önce (N-1) kodlanır, ardından '1' eklenir ve daha sonra n'nin son (N-1) biti eklenir. Özyineleme 0'da biter ve 0 '0' olarak kodlanır.
Levenshtein kodlama, Elias Omega gibi asimptotik olarak optimaldir ancak farklı bir özyinelemeli yapıya sahiptir. Elias Gamma/Delta'dan daha karmaşıktır, ancak çok büyük tamsayılar için daha iyi sıkıştırma sağlar.
Levenshtein kodlama çoğunlukla bilgi teorisi ve Kolmogorov karmaşıklığı gibi alanlarda teorik ilgi konusudur. Pratikte nadiren kullanılır, ancak optimal evrensel kodlamanın prensiplerini gösterir.