> levenshtein | 再帰 | 最適 <
// レーベンシュタイン符号化 - 漸近的に最適な再帰的ユニバーサル符号
0 文字
0 文字
[RECURSIVE]
再帰構造
長さの長さを 0 になるまで再帰的に符号化します。
[OPTIMAL]
漸近的に最適
大きな整数に対して理論上の最小に近づきます。
[UNIVERSAL]
ユニバーサル符号
任意の非負整数に追加パラメータなしで対応します。
>> 技術情報
レーベンシュタイン符号化の仕組み:
レーベンシュタイン符号（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 より複雑ですが、非常に大きな整数に対してより高い圧縮率を得られます。
どこで使われていますか？
レーベンシュタイン符号は主に情報理論とコルモゴロフ複雑性における理論的な対象です。実務で使われることは少ないですが、最適なユニバーサル符号化の原理を示す良い例です。