查看“︁Elias Delta編碼”︁的源代码

{{多個問題|
{{Disputed|time=2022-12-22T21:33:43+00:00}}
{{Rough translation|time=2022-12-22T21:33:43+00:00}}
{{No footnotes|time=2023-08-14T16:46:22+00:00}}
}}
{{TA
|G1=IT
|G2=通訊學
|G3=Math
}}

'''Elias Delta編碼'''、'''Elias delta code'''是一種用於[[正整數]]之通用[[編碼]]。該碼由{{tsl|en|Peter Elias|彼得·埃利亞斯}}發明。

== 編碼 ==
對於待編碼[[自然数|正整數]] ''X''≥1：
# 令 ''N''=&lfloor;log<sub>2</sub> ''X''&rfloor; ，故 2<sup>''N''</sup> ≤ ''X'' < 2<sup>''N''+1</sup>
# 令 ''L''=&lfloor;log<sub>2</sub> ''N''+1&rfloor; ，故 2<sup>''L''</sup> ≤ ''N''+1 < 2<sup>''L''+1</sup>
# 輸出 ''L'' 個零[[位元]]，接著輸出
# ''N''+1 之 ''L''+1 位元[[二进制|二進位]]數，接著輸出
# ''X'' 的最後 ''N'' 個[[位元]]。

另一個等價的編碼方式為：
# 將 ''X'' 分割成小於其之最大二的[[冪|次方]] (2<sup>''N''</sup>) 和餘下的 ''N'' 個[[位元]]之和
# 將 ''N''+1 進行以[[编码|編碼]]
# 將餘下的 ''N'' 個[[位元]]接在上述之後。

要對 <math>x</math> 進行編碼，以利亞戴爾達碼必須使用 <math>\lfloor \log_2(x) \rfloor  + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1</math> 個[[位元]]。

以下為一[[编码|編碼]]對照表：

{| class="wikitable"
! 數 !! N !! N+1 !! 編碼 !! 代表之機率
|-
|  1 = 2<sup>0</sup> || 0 || 1 || <code>1</code> || 1/2
|-
|colspan=4|
|-
|  2 = 2<sup>1</sup> + ''0'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''0''</code> || 1/16
|-
|  3 = 2<sup>1</sup> + ''1'' || 1 || 2 || <code>0&thinsp;1&thinsp;0 ''1''</code> || 1/16
|-
|colspan=4|
|-
|  4 = 2<sup>2</sup> + ''0'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''00''</code> || 1/32
|-
|  5 = 2<sup>2</sup> + ''1'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''01''</code> || 1/32
|-
|  6 = 2<sup>2</sup> + ''2'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''10''</code> || 1/32
|-
|  7 = 2<sup>2</sup> + ''3'' || 2 || 3 || <code>0&thinsp;1&thinsp;1 ''11''</code> || 1/32
|-
|colspan=4|
|-
|  8 = 2<sup>3</sup> + ''0'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''000''</code> || 1/256
|-
|  9 = 2<sup>3</sup> + ''1'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''001''</code> || 1/256
|-
| 10 = 2<sup>3</sup> + ''2'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''010''</code> || 1/256
|-
| 11 = 2<sup>3</sup> + ''3'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''011''</code> || 1/256
|-
| 12 = 2<sup>3</sup> + ''4'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''100''</code> || 1/256
|-
| 13 = 2<sup>3</sup> + ''5'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''101''</code> || 1/256
|-
| 14 = 2<sup>3</sup> + ''6'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''110''</code> || 1/256
|-
| 15 = 2<sup>3</sup> + ''7'' || 3 || 4 || <code>00&thinsp;1&thinsp;00 ''111''</code> || 1/256
|-
|colspan=4|
|-
| 16 = 2<sup>4</sup> + ''0'' || 4 || 5 || <code>00&thinsp;1&thinsp;01 ''0000''</code> || 1/512
|-
| 17 = 2<sup>4</sup> + ''1'' || 4 || 5 || <code>00&thinsp;1&thinsp;01 ''0001''</code> || 1/512
|}

== 解碼 ==
以利亞戴爾達碼之[[编码|解碼]]遵循下列步驟：
# 讀取並計數零[[位元]]直到第一個一[[位元]]出現，假設共有 <sup>''L''</sup> 出現
# 從第一個一位元之後，再讀取 <sup>''L''</sup> 個[[位元]]，並將已讀取之 2<sup>''L''</sup>+1 個位元還原成十進位[[自然数|正整數]]。假設該[[自然数|正整數]]為 ''N''+1
# 再讀取 ''N'' 個[[位元]]並將之還原成十進位[[自然数|正整數]]，令之為 ''M''
# 最終[[编码|解碼]]為 2<sup>''N''</sup>+''M''

舉例：
 001010011
 1. 最左方有兩個零位元 001
 2. 再讀取兩個位元 00101
 3. 還原 00101 = 5
 4. 再讀取 N = 5 − 1 = 4 個位元 0011 = 3
 5. 解碼為 = 2<sup>4</sup> + 3 = 19

== 範例程式碼 ==

=== 編碼 ===
<syntaxhighlight lang="cpp">
void eliasDeltaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        int len = 0;
        int lengthOfLen = 0;
        for (int temp = num; temp > 0; temp >>= 1)  // calculate 1+floor(log2(num))
            len++;
        for (int temp = len; temp > 1; temp >>= 1)  // calculate floor(log2(len))
            lengthOfLen++;
        for (int i = lengthOfLen; i > 0; --i)
            bitwriter.outputBit(0);
        for (int i = lengthOfLen; i >= 0; --i)
            bitwriter.outputBit((len >> i) & 1);
        for (int i = len-2; i >= 0; i--)
            bitwriter.outputBit((num >> i) & 1);
    }
    bitwriter.close();
    intreader.close();
}
</syntaxhighlight>

=== 解碼 ===
<syntaxhighlight lang="cpp">
void eliasDeltaDecode(char* source, char* dest)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int num = 1;
        int len = 1;
        int lengthOfLen = 0;
        while (!bitreader.inputBit())     // potentially dangerous with malformed files.
            lengthOfLen++;
        for (int i = 0; i < lengthOfLen; i++)
        {
            len <<= 1;
            if (bitreader.inputBit())
                len |= 1;
        }
        for (int i = 0; i < len-1; i++)
        {
            num <<= 1;
            if (bitreader.inputBit())
                num |= 1;
        }
        intwriter.putInt(num);            // write out the value
    }
    bitreader.close();
    intwriter.close();
}
</syntaxhighlight>

== 一般化 ==
以利亞戴爾達碼並不適用於[[0|零]]或[[負整數]]。一個一般化的方式是在最左側先加一個一[[位元]]，[[编码|解碼]]時再行扣掉。另一個方法是在[[编码|編碼]]前將所有[[整数|整數]]映射至[[自然数|正整數]]，例如：(0, 1, −1, 2, −2, 3, −3, ...) 對應至 (1, 2, 3, 4, 5, 6, 7, ...)。

== 參考項目 ==
*Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory 21 (2): 194–203.
*[https://books.google.com.tw/books?id=m1u2eo5WweYC&pg=PA181&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CB0Q6AEwAA#v=onepage&q=Elias%20delta%20code&f=false Classical and Quantum Information Theory: An Introduction for the Telecom ...]{{Wayback|url=https://books.google.com.tw/books?id=m1u2eo5WweYC&pg=PA181&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CB0Q6AEwAA#v=onepage&q=Elias%20delta%20code&f=false |date=20150706074042 }}
*[https://books.google.com.tw/books?id=9S9qCQAAQBAJ&pg=PA187&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CCUQ6AEwAQ#v=onepage&q=Elias%20delta%20code&f=false Database Systems for Advanced Applications: 15th International Conference ...]{{Wayback|url=https://books.google.com.tw/books?id=9S9qCQAAQBAJ&pg=PA187&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CCUQ6AEwAQ#v=onepage&q=Elias%20delta%20code&f=false |date=20150706082223 }}
*[https://books.google.com.tw/books?id=jnCi0Cq1YVkC&pg=PA239&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CCwQ6AEwAg#v=onepage&q=Elias%20delta%20code&f=false Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data]{{Wayback|url=https://books.google.com.tw/books?id=jnCi0Cq1YVkC&pg=PA239&dq=Elias+delta+code&hl=zh-TW&sa=X&ei=PiaZVdm9E4rf8AX8zLDQDA&ved=0CCwQ6AEwAg#v=onepage&q=Elias%20delta%20code&f=false |date=20150706093118 }}

[[Category:数字]]
[[Category:无损压缩算法]]