// レーベンシュタイン符号化 - 漸近的に最適な再帰的ユニバーサル符号
長さの長さを 0 になるまで再帰的に符号化します。
大きな整数に対して理論上の最小に近づきます。
任意の非負整数に追加パラメータなしで対応します。
レーベンシュタイン符号（Levenstein や L* 符号とも呼ばれます）は、数のビット長を再帰的に符号化します。2 進長 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'
レーベンシュタイン符号（レーベンシュタイン距離とは異なります）は、整数の長さを再帰的に符号化するユニバーサル符号です。Vladimir Levenshtein によって提案され、大きな整数に対して漸近的に最適です。
この符号はビット長から 1 を引いた値を再帰的に符号化します。N ビットの n を符号化するには、まず (N-1) を符号化し、その後 '1' を付け、さらに n の下位 (N-1) ビットを付加します。再帰は 0 で止まり、'0' として符号化されます。
レーベンシュタイン符号は Elias Omega と同様に漸近的に最適ですが、異なる再帰構造を持ちます。Elias Gamma/Delta より複雑ですが、非常に大きな整数に対してより高い圧縮率を得られます。
レーベンシュタイン符号は主に情報理論とコルモゴロフ複雑性における理論的な対象です。実務で使われることは少ないですが、最適なユニバーサル符号化の原理を示す良い例です。