Кодирование Левенштейна

Кодирование Левенштейна — универсальный код кодирования целых неотрицательных чисел, разработанный Владимиром Левенштейном .

Кодировка

Код нуля — «0»; для кодирования положительного числа :

1. Инициализируйте переменную количества шагов C значением 1.
2. Запишите двоичное представление числа без лидирующей «1» в начале кода.
3. Пусть M — количество битов, записанных на шаге 2.
4. Если M не 0, увеличьте C и повторите действия, начиная с шага 2, используя M в качестве нового числа.
5. Запишите бит C «1» и «0» в начало кода.

Код начинается:

Число	Кодирование	Подразумеваемая вероятность
0	0	1/2
1	10	1/4
2	110 0	1/16
3	110 1	1/16
4	1110 0 00	1/128
5	1110 0 01	1/128
6	1110 0 10	1/128
7	1110 0 11	1/128
8	1110 1 000	1/256
9	1110 1 001	1/256
10	1110 1 010	1/256
11	1110 1 011	1/256
12	1110 1 100	1/256
13	1110 1 101	1/256
14	1110 1 110	1/256
15	1110 1 111	1/256
16	11110 0 00 0000	1/4096
17	11110 0 00 0001	1/4096

Чтобы декодировать целое число, закодированное Левенштейном:

1. Подсчитайте количество битов «1», пока не встретите «0».
2. Если счетчик равен нулю, значение равно нулю, в противном случае
3. Отбросьте только что подсчитанные биты «1» и первый встретившийся «0».
4. Начните с переменной N , установите для нее значение 1 и повторите счетчик минус 1 раз:
5. Прочитайте N бит (и удалите их из закодированного целого числа), добавьте к началу «1», присвойте полученное значение N.

Код Левенштейна положительного целого числа всегда на один бит длиннее, чем омега-код Элиаса этого целого числа. Однако существует код Левенштейна для нуля, тогда как кодирование омеги Элиаса потребует сдвига чисел так, чтобы вместо этого ноль представлялся кодом единицы.

Пример кода

Кодировка

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());
        }
    }
}

Расшифровка

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();
}

См. также

• Элиас омега-кодирование
• Повторный логарифм