WikiDer > Кодирование Левенштейна
Кодирование Левенштейна, или же Кодирование Левенштейна, это универсальный код кодирование неотрицательных целых чисел, разработанное Владимир Левенштейн.[1][2]
Кодирование
Кодекс нуль равно «0»; кодировать положительное число:
- Инициализировать переменную количества шагов C к 1.
- Написать двоичный представление числа без "1" в начале кода.
- Позволять M быть количеством бит, записанных на шаге 2.
- Если M не 0, приращение C, повторите, начиная с шага 2, используя M в качестве нового числа.
- Написать 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», пока не встретится «0».
- Если счетчик равен нулю, значение равно нулю, в противном случае
- Начните с переменной N, установите значение 1 и повторите считать минус 1 раз:
- Читать N бит, добавьте "1", присвойте полученное значение N
Код Левенштейна положительного целого числа всегда на один бит длиннее, чем Омега-код Элиаса этого целого числа. Однако существует код Левенштейна для нуля, тогда как кодирование с помощью омега Элиаса потребовало бы сдвига чисел так, чтобы вместо этого ноль был представлен кодом для единицы.
Пример кода
Кодирование
пустота levenshteinEncode(char* источник, char* dest){ IntReader читатель(источник); BitWriter битрайтер(dest); пока (читатель.оставил()) { int число = читатель.getInt(); если (число == 0) битрайтер.outputBit(0); еще { int c = 0; BitStack биты; делать { int м = 0; за (int темп = число; темп > 1; темп>>=1) // вычисляем этаж (log2 (num)) ++м; за (int я=0; я < м; ++я) биты.pushBit((число >> я) & 1); число = м; ++c; } пока (число > 0); за (int я=0; я < c; ++я) битрайтер.outputBit(1); битрайтер.outputBit(0); пока (биты.длина() > 0) битрайтер.outputBit(биты.popBit()); } }}
Расшифровка
пустота levenshteinDecode(char* источник, char* dest){ BitReader битрейдер(источник); IntWriter интрайтер(dest); пока (битридер.оставил()) { int п = 0; пока (битрейдер.inputBit()) // потенциально опасно с искаженными файлами. ++п; int число; если (п == 0) число = 0; еще { число = 1; за (int я = 0; я < п-1; ++я) { int вал = 1; за (int j = 0; j < число; ++j) вал = (вал << 1) | битрейдер.inputBit(); число = вал; } } интрайтер.положить(число); // записываем значение } битрейдер.Закрыть(); интрайтер.Закрыть();}
Смотрите также
Рекомендации
- ^ "Доклад В. И. Левенштейна 1968 г." (PDF).
- ^ Дэвид Саломон (2007). Коды переменной длины для сжатия данных. Springer. п. 80. ISBN 978-1-84628-958-3.