Elias Delta編碼
編碼
對於待編碼正整數 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 個位元。
另一個等價的編碼方式為:
要對 進行編碼,以利亞戴爾達碼必須使用 個位元。
以下為一編碼對照表:
數 | 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(頁面存檔備份,存於網際網路檔案館)