Кодирование Левенштейна
-
Основы кода Левенштейна
- Код Левенштейна — универсальный код для неотрицательных целых чисел.
- Код нуля начинается с «0», для положительных чисел используется описанный алгоритм.
-
Процесс кодирования
- Для кодирования положительного числа инициализируется C равным 1.
- Двоичное представление числа без «1» в начале записывается в код.
- Если количество битов M не равно 0, C увеличивается и процесс повторяется.
- В конце кода записывается C битов «1» и «0».
-
Процесс расшифровки
- Для расшифровки числа подсчитываются биты «1» до первого «0».
- Если счетчик равен нулю, значение равно нулю, иначе отбрасываются биты «1» и первый «0».
- N устанавливается в 1 и повторяется подсчет с вычитанием 1.
- Удаленные биты добавляются обратно с «1» перед ними.
-
Сравнение с кодом Элиаса Омеги
- Код Левенштейна на один бит длиннее кода Элиаса Омеги для того же числа.
- Для нуля код Левенштейна уникален, в то время как код Элиаса Омеги требует сдвига чисел.
-
Пример кода
- Приведен пример кодирования и расшифровки числа.
-
Дополнительные сведения
- Упоминается кодирование Элиаса омеги и повторяющийся логарифм.
- Предоставлены рекомендации по использованию кода.
Полный текст статьи: