Elias Delta編碼、Elias delta code是一種用於正整數之通用編碼。該碼由發明。
編碼
對於待編碼正整數 X≥1：
令 N=⌊log2 X⌋ ，故 2N ≤ X N+1
令 L=⌊log2 N+1⌋ ，故 2L ≤ N+1 L+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 個位元。
以下為一編碼對照表：
解碼
以利亞戴爾達碼之解碼遵循下列步驟：
讀取並計數零位元直到第一個一位元出現，假設共有 L 出現
從第一個一位元之後，再讀取 L 個位元，並將已讀取之 2L+1 個位元還原成十進位正整數。假設該正整數為 N+1
再讀取 N 個位元並將之還原成十進位正整數，令之為 M
最終解碼為 2N+M
舉例：
001010011
- 最左方有兩個零位元 001
- 再讀取兩個位元 00101
- 還原 00101 = 5
- 再讀取 N = 5 − 1 = 4 個位元 0011 = 3
- 解碼為 = 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
一般化
以利亞戴爾達碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一位元，解碼時再行扣掉。另一個方法是在編碼前將所有整數映射至正整數，例如：(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 ...]
*[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 ...]
*[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]
评论 (0)