Elias delta coding
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Elias δ code or Elias delta code is a universal code encoding the positive integers developed by Peter Elias.
How it works
Elias δ code or Elias delta code is a universal code encoding the positive integers developed by Peter Elias. Let N = ⌊log 2 X⌋; be the highest power of 2 in X, so 2 N ≤ X N+1 . Let L = ⌊log 2 N + 1⌋ be the highest power of 2 in N + 1, so 2 L ≤ N + 1 L+1 . Write L zeros, followed by the (L + 1)-bit binary representation of N + 1, followed by all but the leading bit (i.e. the last N bits) of X. An equivalent way to express the same process: Separate X into the highest power of 2 it contains (2 N ) and the remaining N binary digits.
Encode N + 1 with Elias gamma coding. Append the remaining N binary digits to this representation of N + 1. To represent a number x , Elias delta (δ) uses \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor + 1) \rfloor + 1 bits. This is useful for very large integers, where the overall encoded representation's bits end up being fewer than what one might obtain using Elias gamma coding] due to the \log_2 (\lfloor \log_2(x) \rfloor + 1) portion of the previous expression.
The code begins, using \gamma' instead of \gamma : To decode an Elias delta-coded integer: Read and count zeros from the stream until you reach the first one. Call this count of zeros L. Considering the one that was reached to be the first digit of an integer, with a value of 2 L , read the remaining L digits of the integer. Call this integer N + 1 and subtract one to get N. Put a one in the first place of the final output, representing the value 2 N . Read and append the following N digits.
Example: 001010011 2 leading zeros in 001 read 2 more bits, i.e. 00101 decode N + 1 = 00101 = 5 get N = 5 − 1 = 4 remaining bits for the complete code, i.e.
Evidence and sources
0011 encoded number = 2 4 + 3 = 19 This code can be generalized to zero or negative integers in the same ways described in Elias gamma coding. void eliasDeltaEncode(const ByteBuffer& source, ByteBuffer& dest) { IntReader intreader(source); BitWriter bitwriter(dest); while (intreader.hasLeft()) { int num = intreader.getInt(); int len = 1 + std::floor(std::log2(num)); int lengthOfLen = std::floor(std::log2(len)); 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(const ByteBuffer& source, ByteBuffer& dest) { BitReader bitreader(source); IntWriter intwriter(dest); while (bitreader.hasLeft()) { int num = 1; int len = 1; int lengthOfLen = 0; // potentially dangerous with malformed files. while (!bitreader.inputBit()) { ++lengthOfLen; } for (int i = 0; i
Text derived from https://en.wikipedia.org/w/index.php?oldid=1356932371 under CC BY-SA 4.0; modifications have been made.