Levenshtein coding is a
universal code encoding the non-negative integers developed by
Vladimir Levenshtein
Vladimir Iosifovich Levenshtein ( rus, Влади́мир Ио́сифович Левенште́йн, p=vlɐˈdʲimʲɪr ɨˈosʲɪfəvʲɪtɕ lʲɪvʲɪnˈʂtʲejn, a=Ru-Vladimir Iosifovich Levenstein.oga; 20 May 1935 – 6 September 2017) was ...
.
[
]
Encoding
The code of
zero
0 (zero) is a number representing an empty quantity. Adding (or subtracting) 0 to any number leaves that number unchanged; in mathematical terminology, 0 is the additive identity of the integers, rational numbers, real numbers, and compl ...
is "0"; to code a
positive number
In mathematics, the sign of a real number is its property of being either positive, negative, or 0. Depending on local conventions, zero may be considered as having its own unique sign, having no sign, or having both positive and negative sign. ...
:
#Initialize the step count variable ''C'' to 1.
#Write the
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two values (0 and 1) for each digit
* Binary function, a function that takes two arguments
* Binary operation, a mathematical op ...
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:
To decode a Levenshtein-coded integer:
#Count the number of "1" bits until a "0" is encountered.
#If the count is zero, the value is zero, otherwise
#Discard the "1" bits just counted and the first "0" encountered
#Start with a variable ''N'', set it to a value of 1 and repeat ''count minus 1'' times:
#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.
Example code
Encoding
void levenshteinEncode(char* source, char* dest)
Decoding
void levenshteinDecode(char* source, char* dest)
See also
*
Elias omega coding
*
Iterated logarithm
References
{{DEFAULTSORT:Levenshtein Coding
Entropy coding
Numeral systems
Data compression