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 a ...
.
[
]
Encoding
The code of
zero
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usual ...
is "0"; to code a
positive number
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
:
#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 digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
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
#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 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
Elias ω coding or 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 positive integer with a representation of its order of ma ...
*
Iterated logarithm
In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition i ...
References
{{DEFAULTSORT:Levenshtein Coding
Numeral systems
Lossless compression algorithms