Elias Delta編碼

Elias Delta編碼、Elias delta code是一種用於正整數之通用編碼。該碼由發明。

 編碼 
對於待編碼正整數 X≥1：
 令 N=⌊log2 X⌋ ，故 2N ≤ X < 2N+1
 令 L=⌊log2 N+1⌋ ，故 2L ≤ N+1 < 2L+1
 輸出 L 個零位元，接著輸出
 N+1 之 L+1 位元二進位數，接著輸出
 X 的最後 N 個位元。

另一個等價的編碼方式為：
 將 X 分割成小於其之最大二的次方 (2N) 和餘下的 N 個位元之和
 將 N+1 進行以編碼
 將餘下的 N 個位元接在上述之後。

要對  進行編碼，以利亞戴爾達碼必須使用  個位元。

以下為一編碼對照表：

 數  N  N+1  編碼  代表之機率  1 = 20  0  1  1  1/2  2 = 21 + 0  1  2  0 1 0 0  1/16  3 = 21 + 1  1  2  0 1 0 1  1/16  4 = 22 + 0  2  3  0 1 1 00  1/32  5 = 22 + 1  2  3  0 1 1 01  1/32  6 = 22 + 2  2  3  0 1 1 10  1/32  7 = 22 + 3  2  3  0 1 1 11  1/32  8 = 23 + 0  3  4  00 1 00 000  1/256  9 = 23 + 1  3  4  00 1 00 001  1/256 10 = 23 + 2  3  4  00 1 00 010  1/256 11 = 23 + 3  3  4  00 1 00 011  1/256 12 = 23 + 4  3  4  00 1 00 100  1/256 13 = 23 + 5  3  4  00 1 00 101  1/256 14 = 23 + 6  3  4  00 1 00 110  1/256 15 = 23 + 7  3  4  00 1 00 111  1/256 16 = 24 + 0  4  5  00 1 01 0000  1/512 17 = 24 + 1  4  5  00 1 01 0001  1/512

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

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

 範例程式碼 

 編碼 
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();
}

 解碼 
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();
}

 一般化 
以利亞戴爾達碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一位元，解碼時再行扣掉。另一個方法是在編碼前將所有整數映射至正整數，例如：(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.
Classical and Quantum Information Theory: An Introduction for the Telecom ...
Database Systems for Advanced Applications: 15th International Conference ...
Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data

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