Бинарные деревья и бинарные префиксные коды

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

Справедливо утверждение. Префиксная схема является разделимой.

Неравенство Макмиллана:

_n

Sum (1/2^Si)<=1, где s_i – натуральные числа.

ⁱ⁼¹

Утверждение. Если схема разделима, то для длин ее элементарных кодов выполняется неравенство Макмиллана. Обратно, если для данного набора натуральных чисел выполняется неравенство Макмиллана, то существует разделимая схема, длины элементарных кодов которой равны данным числам.

Задание. Код Морзе - неразделимая схема. Доказать.

Пример префиксного кодирования чисел - код Левенштейна для натуральных чисел.

Двоичная запись натуральных чисел не является префиксной. Этот недостаток ликвидируется кодированием Левенштейна.

Введем вспомогательные понятия:

1. Определим рекурсивную последовательность натуральных чисел: n(0),n(1),n(2),n(3),…

По определению: n(0)=0; n(i)=2^n(i-1) для i>0.

Таким образом, имеем: n(0)=0, n(1)=1, n(2)=2¹=2, n(3)= 2²=4, n(4)= 2⁴=16, n(5)= 2ⁿ⁽⁴⁾=2¹⁶

2. На множестве натуральных чисел определим функцию log*:

log*x=i, где n(i)<=x< n(i+1)

Например, log*100=4, log*2¹⁰⁰=5, т.к. n(5)<=2¹⁰⁰<n(6)

Bin’x – бинарная запись числа x без первой 1.

Например, Bin`129=0000001, т.к. 129=10000001.

Утверждение. |Bin’x|=[log₂x], где |Bin’x| - длина слова Bin’x, [log₂x]-целая часть log₂x.

Примечание. log₂x – логарифм по основанию 2 от x.

Обозначим код Левенштейна натурального числа x как Lev(x).

Код Левенштейна формируется справа налево.

Алгоритм построения кода Левенштейна:

A. Выпиши Bin’x.

b. Припиши слева (log*x-1) итераций Bin’[log₂⁽ⁱ⁾x], i=1,2,…, log*x-1.

Пояснение. log₂⁽ⁱ⁾x= log₂(…(log₂(log₂x))…)

i раз

C. Припиши слева 0.

d. Припиши слева log*x единиц.

в итоге получаем следующую «схему» кода Левенштейна натурального числа x:

11…1 0 Bin’[log₂⁽ⁱ⁾x] … Bin’[log₂x] Bin’x

D c b a

Пример. x=37

log*37=4; [log₂37]=5 [log₂⁽²⁾37]=2 [log₂⁽³⁾37]=1 =>

Bin’1=пусто. Bin’2=0, Bin’5=01 Bin’37=00101 => Lev(37)=1111 0 0 01 00101

Утверждение. В коде Левенштейна каждое подслово является укороченной на одну цифру(единицу) бинарной записью длины следующего слова. Это не относится к начальному подслову 11…10, по которому можно узнать сколько раз приписывается слово Bin’[log⁽ⁱ⁾x].

Это утверждение определяет алгоритм декодирования кода Левенштейна.

Пример. Пусть начальный отрезок последовательности кодов Левенштейна имеет вид:

111100100010111101001…

Декодируем:

i. слева 4 единицы => log*x=4

ii. считываем первую цифру после первого нуля – 0, приписываем к ней 1 => 1Bin’[log₂⁽²⁾x]=10=2

iii. Берем 2 последующие цифры, приписываем слева 1 => 1Bin’[log₂⁽¹⁾x]=110=6

iv. Приписывая слева 1 к последующим 6 цифрам получаем 1Bin’x=1001011=75 => x=75.

Пример. Расшифровать 11110 0 10 000001 [ответ-Lev(65)], 11110 0 11 0000010 [ответ-Lev(130)], 11110 1 000 00000001 [ответ-Lev(257)]

$1.4. Задача создания оптимального префиксного кода.

Сжатие информации это процесс сокращения количества бит, необходимых для хранения некоторого объема информации.

1.4.1. Сжатие методом "стопки книг".

Укажем способ оптимизации данной схемы кодирования - " стопка книг". Он был открыт в 1980 г., а затем переоткрыт в 1986 г., получив название " двигай вверх", и в 1987 г. под названием "Кодирование по степени новизны". Метод состоит в следующем.

Пусть по линии связи должно быть передано cсообщение S в алфавите А={a₁, a₂,..., a_n}. Буквы А отождествлены с числами 1, 2,..., │А│=n.

На приемном и передающем концах имеются идентичные списки, которые в начальный момент содержат числа от 1 до n в порядке возрастания. При появлении в сообщении S очередной буквы a по линии связи передается префиксный код x_i номера позиции i, занимаемой в данный момент буквой a в списке. Это дает возможность на приемном конце идентифицировать букву a. Вслед за этим на приемном и передающем концах ставят букву a в начало списка, увеличивая этим на единицу номера букв, стоящих на позициях от 1 до i-1. Позиции букв, стоящих на позициях от i+1 и дальше, остаются неизменными. Так происходит со стопкой книг, если одну из них взять из стопки и переложить наверх.

Теперь вспомним главную идею префиксного сжатия по частоте встреч букв в тексте: для часто встречающейся буквы - очень короткий код, для редко встречающейся -длинный префиксный код. Если мы расположим наши коды с первой до позиции │А│ по возрастанию длины кода, то получим, что часто встречающиеся буквы будут постоянно вверху "стопки", а, следовательно, будут иметь самые короткие коды и наоборот, редко встречающиеся буквы будут находиться внизу "стопки", а значит будут иметь длинные коды.

Пример.

Пусть нужно передать сообщение S= «bbacabbcc» в алфавите А={a, b, c}. Возьмем, например, следующее префиксное множество {0,10,11} и сопоставим каждому номеру позиции в "стопке" элементарный код из данного множества, причем по возрастанию длины кода. Тогда первая позиция будет иметь код 0, вторая - код 10 и третья - код 11:

Тогда в процессе кодирования сообщения S последний столбец таблицы("стопка книг") будет меняться следующим образом: (a, b, c) - (b, a, c) - (b, a, c) - (a, b, c) - (c, a, b) - (a, c, b) - (b, a, c) и т. д. Тогда кодом сообщения S будет 100101110110110.

Поиск по сайту: