> levenshtein | 遞迴 | 最佳 <
// Levenshtein 編碼 —— 具漸近最優性的遞迴通用整數編碼
0 字元
0 字元
[RECURSIVE]
遞迴結構
遞迴編碼「長度的長度」，直到回到 0。
[OPTIMAL]
漸近最優
對非常大的整數，其碼長逼近理論上的最小值。
[UNIVERSAL]
通用碼
不需假設分佈或參數，適用於所有非負整數。
>> 技術資訊
Levenshtein 編碼的運作方式:
Levenshtein 編碼（亦稱為 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'
為什麼要使用 Levenshtein 編碼？:
- ▸對大整數而言具有漸近最優的壓縮效率
- ▸無需對來源分佈做任何假設
- ▸在資訊理論與 Kolmogorov 複雜度中具有重要理論價值
- ▸適用於所有非負整數的通用編碼方案
- ▸能穩定處理非常龐大的整數資料
>> 常見問題
什麼是 Levenshtein 編碼？
Levenshtein 編碼（請勿與 Levenshtein 距離混淆）是一種對整數長度進行遞迴編碼的通用碼。由 Vladimir Levenshtein 提出，對於大型整數在漸近意義下是最優的。
這裡的遞迴是怎麼進行的？
此編碼會遞迴地編碼「位元長度減一」。對 N 位元長度的 n 進行編碼時，先編碼 (N-1)，再附加 '1'，最後附加 n 的後 (N-1) 位。遞迴在 0 結束，而 0 會被編碼為 '0'。
Levenshtein 與 Elias 編碼有何差異？
Levenshtein 編碼與 Elias Omega 一樣在漸近意義上是最優的，但採用不同的遞迴結構。相比 Elias Gamma／Delta，它更為複雜，但在極大整數上通常能得到更好的壓縮率。
這種編碼實際上用在哪裡？
Levenshtein 編碼主要應用於資訊理論與 Kolmogorov 複雜度等領域的理論研究。在實務系統中較少直接使用，但非常適合用來說明「最優通用編碼」的核心概念。