// लेवेनश्टाइन कोडिंग - पुनरावर्ती सार्वभौमिक कोड जिसकी आसिम्पटोटिक इष्टतमता है
लंबाई की लंबाई को 0 तक पुनरावर्ती रूप से एन्कोड करता है।
बड़े पूर्णांकों के लिए सैद्धांतिक न्यूनतम के क़रीब पहुँचता है।
किसी भी गैर-ऋणात्मक पूर्णांक के लिए बिना अतिरिक्त पैरामीटर के काम करता है।
लेवेनश्टाइन कोडिंग (जिसे Levenstein या L* कोड भी कहा जाता है) किसी संख्या की बिट लंबाई को पुनरावर्ती रूप से एन्कोड करती है। बाइनरी लंबाई N वाले पूर्णांक n के लिए: हम पुनरावर्ती रूप से C(N-1) एन्कोड करते हैं, '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 के अंतिम (N-1) बिट जोड़ें। पुनरावृत्ति 0 पर समाप्त होती है, जिसे '0' के रूप में एन्कोड किया जाता है।
लेवेनश्टाइन कोडिंग, Elias Omega की तरह, आसिम्पटोटिक रूप से इष्टतम है, लेकिन इसकी पुनरावर्ती संरचना अलग है। यह Elias Gamma/Delta से अधिक जटिल है, लेकिन बहुत बड़े पूर्णांकों के लिए बेहतर संपीड़न देता है।
लेवेनश्टाइन कोडिंग मुख्य रूप से सूचना सिद्धांत और कोल्मोगोरोव जटिलता में सैद्धांतिक रुचि का विषय है। व्यवहार में इसे कम उपयोग किया जाता है, लेकिन यह इष्टतम सार्वभौमिक कोडिंग के सिद्धांतों को अच्छी तरह दर्शाता है।