Levenshtein coding is auniversal code encoding the non-negative integers developed byVladimir Levenshtein.^[1][2]

The code ofzero is "0"; to code apositive number:

1. Initialize the step count variableC to 1.
2. Write thebinary representation of the number without the leading "1" to the beginning of the code.
3. LetM be the number of bits written in step 2.
4. IfM is not 0, incrementC, repeat from step 2 with M as the new number.
5. WriteC "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 variableN, set it to a value of 1 and repeatcount minus 1 times:
5. ReadN bits (and remove them from the encoded integer), prepend "1", assign the resulting value toN

The Levenshtein code of a positive integer is always one bit longer than theElias 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.

voidlevenshteinEncode(char*source,char*dest){IntReaderintreader(source);BitWriterbitwriter(dest);while(intreader.hasLeft()){intnum=intreader.getInt();if(num==0)bitwriter.outputBit(0);else{intc=0;BitStackbits;do{intm=0;for(inttemp=num;temp>1;temp>>=1)// calculate floor(log2(num))++m;for(inti=0;i<m;++i)bits.pushBit((num>>i)&1);num=m;++c;}while(num>0);for(inti=0;i<c;++i)bitwriter.outputBit(1);bitwriter.outputBit(0);while(bits.length()>0)bitwriter.outputBit(bits.popBit());}}}

voidlevenshteinDecode(char*source,char*dest){BitReaderbitreader(source);IntWriterintwriter(dest);while(bitreader.hasLeft()){intn=0;while(bitreader.inputBit())// potentially dangerous with malformed files.++n;intnum;if(n==0)num=0;else{num=1;for(inti=0;i<n-1;++i){intval=1;for(intj=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

• Entropy coding
• Numeral systems
• Data compression

• Articles with short description
• Short description matches Wikidata