Levenshtein coding
Encyclopedia
Levenstein coding, or 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:
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:
The Levenstein code of a positive integer is always one bit longer than the Elias omega code
of that integer. However, there is a Levenstein 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.
Universal code (data compression)
In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...
encoding the non-negative integers developed by Vladimir Levenshtein
Vladimir Levenshtein
Vladimir Iosifovich Levenshtein is a Russian scientist who did research in information theory and error-correcting codes. Among other contributions, he is known for the Levenshtein distance algorithm, which he developed in 1965....
.
The code of zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
is "0"; to code a positive number:
- Initialize the step count variable C to 1.
- Write the binaryBinary numeral systemThe binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
representation of the number without the leading "1" to the beginning of the code. - Let M be the number of bits written in step 2.
- If M is not 0, increment C, repeat from step 2 with M as the new number.
- 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:
- Count the number of "1" bits until a "0" is encountered.
- If the count is zero, the value is zero, otherwise
- Start with a variable N, set it to a value of 1 and repeat count minus 1 times:
- 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
Elias omega coding
Elias omega coding is a universal code encoding the positive integers developed by Peter Elias. Like Elias gamma coding and Elias delta coding, it works by prefixing the integer with a representation of its order of magnitude in a universal code...
of that integer. However, there is a Levenstein 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.