以利亚戴尔达码
2020-12-22 05:51:00
以利亚戴尔达码（Elias delta code）是一种用于正整数之通用编码。该码由 Peter Elias 发明。
对于待编码正整数 ≥1：
另一个等价的编码方式为：
要对 进行编码，以利亚戴尔达码必须使用 个比特。
进行编码，以利亚戴尔达码必须使用 
个比特。以下为一编码对照表：
以利亚戴尔达码之解码遵循下列步骤：
举例：
0010100111. 最左方有兩個零位元 0012. 再讀取兩個位元 001013. 還原 00101 = 54. 再讀取 N = 5 − 1 = 4 個位元 0011 = 35. 解碼為 = 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, ...)。