Кодирование натурального ряда.

Здесь мы будем рассматривать алфавиты А = (0,1,…,9) иB= (0,1).

Задача кодирования натуральных чисел битовыми последовательностями актуальна, так как часто необходимо хранить и передавать информацию в бинарном виде.Особенно остро она встала в 50-е годы прошлого века в связи с распространением компьютеров.

В данной модели предполагается, что нужно работать (хранить, передавать) с битовой информацией, изначально представимой, например, в десятичных числах. При этом набор чисел представляется битовой последовательностью без разделителей.

Простой переход к двоичной записи не обеспечивает префиксности, а, следовательно, и декодируемости этой битовой последовательности.

Приведем примеры кодов, которые это обеспечивают.

Пусть n > 1, двоичную запись числа n обозначимBIN(n) = α ₁… α_n, α _i {0, 1}. (Например, BIN(30) = 11110, BIN(75) = 1001011). Заметим, что k = |BIN(n)| = [log n ] + 1. Пусть B(n) – двоичная запись n без первого символа. (Например, B(30) = 1110, B(75) = 001011). Тогда |B(n)| = [log n ].

Так как любая двоичная запись натурального числа начинается с единицы, то префиксность можно обеспечить с помощью тривиального кода

TK(n)= 0…0BIN(n),

Где число нулей префиксе равно [log n ] + 1. Длина такого кода 2[log n ] + 2. Следующие два примера дают более экономное кодирование.

Код Элайеса.

Код Элайеса неотрицательного целого числа n обозначим через El (n). Положим El (0) = 10, El (1) = 11.

Пусть n > 1. В этом случае длина слова BIN(n) больше единицы. Код Элайеса состоит из трех фрагментов. Вначале идет некоторое количество нулей, подсчитав которые, мы найдем число символов в двоичной записи |BIN(n)|. Для экономии, учитывая предыдущее замечание можно взять количество нулей на единицу меньшее числа символов в двоичной записи |BIN(n)|. (Так как любая двочная запись начинается с единицы, то мы всегда знаем, где заканчивается наша цепочка нулей). Теперь мы это количество символов записи |BIN(n)| отсчитываем после последнего нуля, а затем полученный врагмент из нулей и единиц переводим в десятичную запись и получаем длину закодированного слова. Зная эту длину, мы отсчитываем нужное нам число символов, а полученный фрагмент и будет двоичной записью закодированного натурального числа. Опять же для экономии первую единицу данного фрагмента можно в коде опустить.

Тогда El (n)= 00…0 BIN([log n ]+1) B (n), где 00…0 – маркер, необходимый для того, чтобы знать, сколько последующих за 0 символов может задавать длину записи числа. Поэтому в данном коде количество нулей передBIN([log n ]+1) равно |BIN([log n ]+1)|-1.

Примеры (пробелы стоят только для иллюстрации):

El (5) = 0 11 01.

El (75) = 00 111 001011.

Утверждение. Длина | El (n)| непревосходитlog n + 2 log (log n) + 3.

Утверждение. Код Элайеса – префиксный.

Доказательство: Рассмотрим El (n) и El (m). Если хотя бы одно из этих слов начинается с 1, то это либо 0, либо 1. Утверждение доказано. Пусть n, m больше 1, вспомним теорему о дешифруемости кода: El (n) = α ₁… α_k, El (m) = β ₁… β_S (для определенности k ≥ s). Пусть количество 0, с которых начинается α, совпадает с количеством 0, с которых начинается β. (В противном случае сразу следует свойство префиксности кода.)Далее рассмотрим вторые подслова слов El (n) и El (m). Если они не совпадают, то префиксность кода доказана. Если совпадают, то переходим к окончаниям слов. Если они совпадают, тоm=n. В противном случае n не равно m. Таким образом, при m≠nвыполняется соотношение B (n) ≠ B (m).

Утверждение доказано.

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

В коде Элайеса мы сэкономили по сравнению с тривиальным кодом за счет уменьшения префикса. В коде Левенштейна эта идея доведена до определенного истощения: от двоичной записи числа мы сначала переходим к двоичной записи длины BIN(n) (это было и в коде Элайеса), но затем мы переходим к длине длины, длине длины длины и т.д.

Введем для удобства формальной записи этой идеи некоторые обозначения. Пусть λ ₀(n) = [log n ]. А далее по аналогии до λ^k ₀(n) = λ ₀ (λ^{k -1}₀(n)) = [log…[log n ]].

Для любого n существует S такое, что: λ^S ₀(n) = 0, λ^{S -1}₀(n) = 1.

Положим Lev (0)=0, Lev (1) =10. Пусть n > 1. Тогда для такого сила вышеупомянутый параметр S>1. Если в префиксе кода мы ставим Sподряд идущих единиц, а затем ноль (чтобы показать, где эта цепочка единиц заканчивается), то это не может быть ни кодом 0, ни кодом 1. А так как λ^S ₀(n) = 0, λ^{S -1}₀(n) = 1, то эти соотношения никакой информации для кодирования не содержа, и в код надо включать информацию о длинах, начиная с B (λ^{S -2}₀(n). Отсюда и следует формула для кода Левенштейна.

Lev (n) = 11…10 B (λ^{S -2}₀(n))… B (λ ₀(n)) B (n),

где 11…10 – слово из S единициодного нуля.

Утверждение. Длина кода Левенштейна задается соотношением

| Lev (n)| = log n + loglog n + o(loglog n).

Утверждение. Код Левенштейна префиксный.

Пример (пробелы только для иллюстрации):

Lev (75) = 11110 0 11 001011

 

S = 4

Lev(5)=1110 0 01. Lev(62)=11110 0 01 11110.