Levenshtein coding

Levenshtein coding is a universal code encoding the non-negative integers developed by Vladimir Levenshtein.

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:

 0 0
 1 10
 2 110 0
 3 110 1
 4 1110 0 00
 5 1110 0 01
 6 1110 0 10
 7 1110 0 11
 8 1110 1 000
 9 1110 1 001
10 1110 1 010
11 1110 1 011
12 1110 1 100
13 1110 1 101
14 1110 1 110
15 1110 1 111
16 11110 0 00 0000
17 11110 0 00 0001

To decode a Levenstein-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. Start with a variable N, set it to a value of 1 and repeat count minus 1 times:
4. Read N bits, prepend "1", assign the resulting value to N

The Levenstein code of a positive integer is always one bit longer than the Elias omega code of that integer.

See also

• Elias omega coding
• Log*

Sources

• 1968 paper by V. I. Levenshtein (in Russian)