| dbo:abstract
|
- ترميز ليفينشتاين (بالإنجليزية: Levenshtein coding) هو أحد أنواع الترميز العامة للأعداد غير السالبة. طُوِّر على يد . (ar)
- Levenstein coding, or Levenshtein coding, is a universal code encoding the non-negative integers developed by Vladimir Levenshtein. (en)
- Le codage de Levenshtein est un codage entropique inventé par Vladimir Levenshtein en 1968 et utilisé essentiellement en compression de données. Le code de Levenshtein produit est un code préfixe et universel. (fr)
- Код Левенштейна — это универсальный код, позволяющий кодировать неотрицательные целые числа. Он был придуман Владимиром Левенштейном. Код нуля — это «0»; для кодирования положительного числа используется алгоритм: 1.
* Инициализировать счетчик шагов С = 1, K — код числа(изначально пустой). 2.
* Записать двоичный код кодируемого числа без «старшей» 1 (например, число 1100 записать как 100; число 100 — как 00). 3.
* Дописать полученное в начало K. 4.
* Пусть M — количество бит, записанных на втором шаге. Перевести M в двоичный вид. 5.
* Если М не пусто, то С = С + 1, и повторить алгоритм с шага 2 для полученного М. Иначе перейти на шаг 6. 6.
* Записать С штук единиц и 0 в начало кода К (например, если счетчик С = 2, К = 0 011, получить: 110 0 011) — код Левенштейна. Код Левенштейна для первых 24 чисел будет выглядеть так: 0 0 1 10 2 110 0 3 110 1 4 1110 0 00 5 1110 0 01 6 1110 0 10 7 1110 0 11 8 1110 1 000 9 1110 1 00110 1110 1 01011 1110 1 01112 1110 1 10013 1110 1 10114 1110 1 11015 1110 1 11116 11110 0 00 000017 11110 0 00 000118 11110 0 00 001019 11110 0 00 001120 11110 0 00 010021 11110 0 00 010122 11110 0 00 011023 11110 0 00 011124 11110 0 00 1000 Пусть К — код Левенштейна. Для расшифровки кода Левенштейна необходимо: 1.
* Посчитать количество С единичных бит до первого нулевого бита. 2.
* Если С = 0, то закодированное значение — 0. Если нет, перейти на шаг 3. 3.
* Отбросить из К эти С единиц и следующий за ними 0. Записать новое значение К. 4.
* Установить переменную N = 1. Ввести счетчик шагов P = С — 1. 5.
* Если P = 0, то N — искомое число. Если нет, перейти на шаг 6. 6.
* Считать первые N бит из К. Записать новое значение К без считанных N бит. 7.
* К считанной записи добавить 1 в начало (например, считано 00, получено: 100). 8.
* Преобразовать полученное значение в десятичную систему (или исходную, если известно) — новое значение переменной N. 9.
* P = P — 1. Повторить с шага 5. При кодировании Левенштейна положительное число всегда на 1 бит больше, чем при . Однако, кодом Левенштейна можно закодировать ноль, в то время как при омега-кодировании Элиаса необходимо переобозначать все цифры таким образом, чтобы ноль представлялся единицей. (ru)
|
