Levenshtein coding

The code of zero is "0"; to code a positive number:

1. Initialize the step count variable C to 1.
2. Write the binary representation of the number without the leading "1" to the beginning of the code.
3. Let M be the number of bits written in step 2.
4. If M is not 0, increment C, repeat from step 2 with M as the new number.
5. Write C "1" bits and a "0" to the beginning of the code.

The code begins:

To decode a Levenshtein-coded integer:

1. Count the number of "1" bits until a "0" is encountered.
2. If the count is zero, the value is zero, otherwise
3. Discard the "1" bits just counted and the first "0" encountered
4. Start with a variable N, set it to a value of 1 and repeat count minus 1 times:
5. Read N bits (and remove them from the encoded integer), prepend "1", assign the resulting value to N

The Levenshtein code of a positive integer is always one bit longer than the Elias omega code of that integer. However, there is a Levenshtein code for zero, whereas Elias omega coding would require the numbers to be shifted so that a zero is represented by the code for one instead.

void levenshteinEncode(char* source, char* dest)

{

IntReader intreader(source);

BitWriter bitwriter(dest);

while (intreader.hasLeft())

{

int num = intreader.getInt();

if (num == 0)

bitwriter.outputBit(0);

else

{

int c = 0;

BitStack bits;

do {

int m = 0;

for (int temp = num; temp > 1; temp>>=1) // calculate floor(log2(num))

++m;

for (int i=0; i < m; ++i)

bits.pushBit((num >> i) & 1);

num = m;

++c;

} while (num > 0);

for (int i=0; i < c; ++i)

bitwriter.outputBit(1);

bitwriter.outputBit(0);

while (bits.length() > 0)

bitwriter.outputBit(bits.popBit());

}

}

}

void levenshteinDecode(char* source, char* dest)

{

BitReader bitreader(source);

IntWriter intwriter(dest);

while (bitreader.hasLeft())

{

int n = 0;

while (bitreader.inputBit()) // potentially dangerous with malformed files.

++n;

int num;

if (n == 0)

num = 0;

else

{

num = 1;

for (int i = 0; i < n-1; ++i)

{

int val = 1;

for (int j = 0; j < num; ++j)

val = (val << 1) | bitreader.inputBit();

num = val;

}

}

intwriter.putInt(num); // write out the value

}

bitreader.close();

intwriter.close();

}

• Elias omega coding
• Iterated logarithm

{{reflist}}

{{Compression Methods}}

{{DEFAULTSORT:Levenshtein Coding}}

Category:Entropy coding

Category:Numeral systems

Category:Data compression