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 个位元接在上述之后。

要对 $x$ 进行编码，以利亚戴尔达码必须使用 $\lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1$ 个位元。

以下为一编码对照表：

数｜N｜N+1｜编码｜代表之几率

1 = 20｜0｜1｜`1`｜1/2

2 = 21 + 0｜1｜2｜`0&thinsp;1&thinsp;0 ''0''`｜1/16

3 = 21 + 1｜1｜2｜`0&thinsp;1&thinsp;0 ''1''`｜1/16

4 = 22 + 0｜2｜3｜`0&thinsp;1&thinsp;1 ''00''`｜1/32

5 = 22 + 1｜2｜3｜`0&thinsp;1&thinsp;1 ''01''`｜1/32

6 = 22 + 2｜2｜3｜`0&thinsp;1&thinsp;1 ''10''`｜1/32

7 = 22 + 3｜2｜3｜`0&thinsp;1&thinsp;1 ''11''`｜1/32

8 = 23 + 0｜3｜4｜`00&thinsp;1&thinsp;00 ''000''`｜1/256

9 = 23 + 1｜3｜4｜`00&thinsp;1&thinsp;00 ''001''`｜1/256

10 = 23 + 2｜3｜4｜`00&thinsp;1&thinsp;00 ''010''`｜1/256

11 = 23 + 3｜3｜4｜`00&thinsp;1&thinsp;00 ''011''`｜1/256

12 = 23 + 4｜3｜4｜`00&thinsp;1&thinsp;00 ''100''`｜1/256

13 = 23 + 5｜3｜4｜`00&thinsp;1&thinsp;00 ''101''`｜1/256

14 = 23 + 6｜3｜4｜`00&thinsp;1&thinsp;00 ''110''`｜1/256

15 = 23 + 7｜3｜4｜`00&thinsp;1&thinsp;00 ''111''`｜1/256

16 = 24 + 0｜4｜5｜`00&thinsp;1&thinsp;01 ''0000''`｜1/512

17 = 24 + 1｜4｜5｜`00&thinsp;1&thinsp;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. 解碼為 = 2<sup>4</sup> + 3 = 19
```

## 范例程式码

### 编码

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

### 解码

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

## 一般化

以利亚戴尔达码并不适用于零或负整数。一个一般化的方式是在最左侧先加一个一位元，解码时再行扣掉。另一个方法是在编码前将所有整数映射至正整数，例如：(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