Levenshtein coding

<h2 id="encoding">Encoding</h2>
<p>The code of <a href="/facts/0_(number)/4NBRtKHc">zero</a> is "0"; to code a <a href="/facts/Positive_number/z0xollg1">positive number</a>:
</p>
<ol><li>Initialize the step count variable <i>C</i> to 1.</li>
<li>Write the <a href="/facts/Binary_numeral_system/a6JDSRPs">binary</a> representation of the number without the leading "1" to the beginning of the code.</li>
<li>Let <i>M</i> be the number of bits written in step 2.</li>
<li>If <i>M</i> is not 0, increment <i>C</i>, repeat from step 2 with M as the new number.</li>
<li>Write <i>C</i> "1" bits and a "0" to the beginning of the code.</li></ol>
<p>The code begins:
</p>
<table><tbody><tr><th>Number</th><th>Encoding</th><th>Implied probability</th></tr><tr><td>0</td><td>0</td><td>1/2</td></tr><tr><td colspan="4"></td></tr><tr><td>1</td><td>10</td><td>1/4</td></tr><tr><td colspan="4"></td></tr><tr><td>2</td><td>110 0</td><td>1/16</td></tr><tr><td>3</td><td>110 1</td><td>1/16</td></tr><tr><td colspan="4"></td></tr><tr><td>4</td><td>1110 0 00</td><td>1/128</td></tr><tr><td>5</td><td>1110 0 01</td><td>1/128</td></tr><tr><td>6</td><td>1110 0 10</td><td>1/128</td></tr><tr><td>7</td><td>1110 0 11</td><td>1/128</td></tr><tr><td colspan="4"></td></tr><tr><td>8</td><td>1110 1 000</td><td>1/256</td></tr><tr><td>9</td><td>1110 1 001</td><td>1/256</td></tr><tr><td>10</td><td>1110 1 010</td><td>1/256</td></tr><tr><td>11</td><td>1110 1 011</td><td>1/256</td></tr><tr><td>12</td><td>1110 1 100</td><td>1/256</td></tr><tr><td>13</td><td>1110 1 101</td><td>1/256</td></tr><tr><td>14</td><td>1110 1 110</td><td>1/256</td></tr><tr><td>15</td><td>1110 1 111</td><td>1/256</td></tr><tr><td colspan="4"></td></tr><tr><td>16</td><td>11110 0 00 0000</td><td>1/4096</td></tr><tr><td>17</td><td>11110 0 00 0001</td><td>1/4096</td></tr></tbody></table>
<p>To decode a Levenshtein-coded integer:
</p>
<ol><li>Count the number of "1" bits until a "0" is encountered.</li>
<li>If the count is zero, the value is zero, otherwise</li>
<li>Discard the "1" bits just counted and the first "0" encountered</li>
<li>Start with a variable <i>N</i>, set it to a value of 1 and repeat <i>count minus 1</i> times:</li>
<li>Read <i>N</i> bits (and remove them from the encoded integer), prepend "1", assign the resulting value to <i>N</i></li></ol>
<p>The Levenshtein code of a positive integer is always one bit longer than the <a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega code</a> 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.
</p>
<h2 id="example-code">Example code</h2>
<h3>Encoding</h3>
void levenshteinEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        if (num == 0)
            bitwriter.outputBit(0);
        else
        {
            int c = 0;
            BitStack bits;
            do {
                int m = 0;
                for (int temp = num; temp > 1; temp>>=1)  // calculate floor(log2(num))
                    ++m;
                for (int i=0; i < m; ++i)
                    bits.pushBit((num >> i) & 1);
                num = m;
                ++c;
            } while (num > 0);
            for (int i=0; i < c; ++i)
                bitwriter.outputBit(1);
            bitwriter.outputBit(0);
            while (bits.length() > 0)
                bitwriter.outputBit(bits.popBit());
        }
    }
}

<h3>Decoding</h3>
void levenshteinDecode(char* source, char* dest)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int n = 0;
        while (bitreader.inputBit())     // potentially dangerous with malformed files.
            ++n;
        int num;
        if (n == 0)
            num = 0;
        else
        {
            num = 1;
            for (int i = 0; i < n-1; ++i)
            {
                int val = 1;
                for (int j = 0; j < num; ++j)
                    val = (val << 1) | bitreader.inputBit();
                num = val;
            }
        }
        intwriter.putInt(num);           // write out the value
    }
    bitreader.close();
    intwriter.close();
}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega coding</a></li>
<li><a href="/facts/Iterated_logarithm/bEY9cfh8">Iterated logarithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"1968 paper by V. I. Levenshtein (in Russian)" (PDF). <a href="http://www.compression.ru/download/articles/int/levenstein_1968_on_the_redundancy_and_delay.pdf" target="_blank">http://www.compression.ru/download/articles/int/levenstein_1968_on_the_redundancy_and_delay.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>David Salomon (2007). Variable-length codes for data compression. Springer. p. 80. ISBN 978-1-84628-958-3. <a href="978-1-84628-958-3" target="_blank">978-1-84628-958-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Levenshtein coding open-in-new

Levenshtein coding