> elias | delta | optimal <

// Elias Delta —— 對大型整數比 Gamma 更高效的通用編碼

顯示步驟與 Gamma 比較

輸入

0 字元

輸出

0 字元

>> 功能特色

[高效]

優於 Gamma

對於 n > 3 的整數，比 Elias Gamma 使用更少位元。

[通用]

通用編碼

不需額外參數，適用於任何正整數。

[漸近優化]

良好的漸近行為

使用 log₂(n) + 2log₂(log₂(n)) + 1 個位元。

>> 技術細節

Elias Delta 的運作方式

Elias Delta 以三個步驟編碼正整數 n：1）計算 L = ⌊log₂(n)⌋ + 1（位元長度）；2）使用 Elias Gamma 對 L 進行編碼；3）附加 n 的最低 L−1 個位元。由於採用雙對數成長形式，在維持通用性的同時，對大型整數比 Gamma 更為節省位元。

Delta 編碼範例

n=1: L=1, Gamma(1)='1', bits='', Delta='1'
n=2: L=2, Gamma(2)='010', bits='0', Delta='0100'
n=3: L=2, Gamma(2)='010', bits='1', Delta='0101'
n=4: L=3, Gamma(3)='011', bits='00', Delta='01100'
n=16: L=5, Gamma(5)='00101', bits='0000', Delta='001010000'

長度比較：
n     | Gamma | Delta | 節省
1     | 1     | 1     | 0
16    | 9     | 9     | 0
100   | 13    | 12    | 1
1000  | 19    | 16    | 3

為何選擇 Elias Delta

▸ 在 n > 3 時比 Gamma 更有效率
▸ 無需調整參數，直接使用
▸ 前綴碼、可唯一解碼
▸ 適合中等大小整數的壓縮需求
▸ 是邁向 Elias Omega 的重要階段

>> 常見問題

什麼是 Elias Delta 編碼？

Elias Delta 是對 Elias Gamma 的改良：先以 Gamma 編碼整數的二進位長度，再接上剩餘的位元。大約使用 log₂(n) + 2log₂(log₂(n)) + 1 個位元，因此在大型整數上更為省空間。

Delta 與 Gamma 有何差異？

Gamma 採用 2⌊log₂(n)⌋ + 1 位元，而 Delta 採用 log₂(n) + 2log₂(log₂(n)) + 1 位元。對於 n > 3，Delta 更具優勢，且 n 越大節省越明顯；對 1–3 這類很小的整數，兩者差異不大。

什麼時候該用 Delta 而不是 Gamma？

當資料多半是 n > 3 的整數時，建議使用 Delta。若資料幾乎全是 1–2 這種極小整數，Gamma 可能略勝一籌。對非常大的整數，可考慮進一步的 Elias Omega 編碼。

Delta 是最佳的 Elias 編碼嗎？

Delta 屬於折衷方案：Gamma 最簡單但效率最低；Delta 提高了壓縮率；Omega 在超大整數上最省位元，但實作也最複雜。應依資料分佈及實作成本來選擇。

[Base64.sh]