Алфавитное кодирование

Сопоставим коду V ориентированный граф G, вершинами которого являются элементы множества S. Вершины α и β соединяем ориентированным ребром (α, β), если существует элементарный код v_j и последовательность элементарных кодов P = (v₁,v₂,…v_m), такие, что v_j=α v_i1 v_i2…v_ik β. При этом P может быть пустой, если α и β оба непустые.

    Ребру (α,  β) припишем последовательность v_i1 v_i2…v_ik. Ребро (λ, λ) присутствует в графе тогда и только тогда, когда существует v_j и последовательность P = v_i1 v_i2…v_ik (k≥2), такие, что v_j = v_i1 v_i2…v_ik.

    Теорема 2.4. Алфавитный код V является взаимно-однозначным тогда и только тогда, когда в графе G отсутствуют ориентированные циклы, проходящие через вершину λ.

    Пример  2.3. Пусть B = (b₁, b₂, b₃), V = {1,010,101}. Построим множества S₁ и S:

S₁ ={0,1,01,10}, S={0,1,01,10, λ}. Для этого выпишем все нетривиальные разложения элементарных кодов v_i.

    Для v₁ нет нетривиальных разложений.

    v₂ = 010 = 0 v₁ 0 = 01 λ 0 = 0 λ 10

    v₃ = 101 = λ v₁ 01 = 10 v₁ λ = 1 λ 01 = 10 λ 1.

    Соответствующий коду граф изображен на рис.2.2.

     

 

     Рис.2.2. Граф для примера 2.3 

    Граф  содержит ориентированный цикл, проходящий через вершину λ, следовательно, код V не является взаимно-однозначным.

    По  графу нетрудно построить двоичную последовательность, допускающую две расшифровки. Для этого достаточно, начиная с вершины λ, приписать друг к другу двоичные последовательности, соответствующие вершинам и ребрам графа, вдоль найденного цикла.

Слово γ = 1010101, соответствующее циклу, допускает две расшифровки: b₁ b₂ b₃ и b₃ b₂ b₁.

    Пример  2.4. Пусть B = (b₁ b₂ b₃ b₄ b₅), V = {1,01,100,0100,0000}. Построим множества S₁ и S: S₁ ={0,00,000,1}, S={0,00,000,1, λ}.

    Выпишем все нетривиальные разложения для  элементарных кодов.

v₂ = 01 = 0 v₁ λ = 0 λ 1

v₃ = 100 = λ v₁ 00 = 1 λ 00

v₄ = 0100 = 0 v₁ 00 = λ v₂ 00 = 0 v₃ λ

v5 = 0000 = 0 λ 000 = 00 λ 00 = 000 λ 0.

    Соответствующий коду граф изображен на рис.2.3.

    Граф  не содержит ориентированный цикл, проходящий через вершину λ, следовательно, код V является взаимно-однозначным. 

     

     Рис.2.3. Граф для примера 2.4 

    2.3. Алгоритм построения префиксного кода по набору длин элементарных кодов 

    Пусть задан набор чисел l₁,l₂,…l_m, удовлетворяющих неравенству Мак-Миллана:

. В силу теоремы 2.3 существует префиксный код с набором длин (l₁,l₂,…l_m)

элементарных  кодов. Приведем алгоритм К. Шеннона построения префиксного кода по набору длин.

    Будем полагать l₁ ≤ l₂  ≤...≤ l_m. Построим последовательность чисел q₁, q₂,..., q_m по следующим правилам:

    q₁ = 0,

    q_i+1 = q_i + 2^-li (i = 1, 2, …, m-1)

    Очевидно, 0 ≤ q_i < 1 и q_i имеет единственное представление в виде двоичной дроби с l_i знаками после запятой:

     где или .

    Рассмотрим  код V = (v₁,v₂,...,v_m), где

    Так как наборы длин упорядочены по неубыванию, при h > i выполняются неравенства

l_h ≥ l_i и q_h ≥ q_i + 2^-li. Поэтому элементарный код v_h отличается от элементарного кода v_i в l_i первых разрядах. Следовательно, построенный код является префиксным.

    Пример  2.5. Рассмотрим набор чисел L = (2,3,3,3,4,4,4). Так как

2^-2 + 2^-3 + 2^-3 + 2^-3 + 2^-4 + 2^-4 + 2^-4 = <1, неравенство Мак-Миллана выполняется.

    Построим  последовательность чисел q₁, q₂, q₃, q₄, q₅, q₆, q₇, записывая их в двоичной системе счисления.

     q₁ = 0,00

     q₂ = 0 + 2^-2 = 0,010

     q₃ = 0,01 + 2^-3 = 0,01 + 0,001 = 0,011

     q₄ = 0,011 + 2^-3 = 0,011 + 0,001 = 0,100

     q₅ = 0,1 + 2^-3 = 0,1 + 0,001 = 0,1010

     q₆ = 0,101 + 2^-4 = 0,101 + 0,0001 = 0,1011

     q₇ = 0,1011 + 2^-4 = 0,1011 + 0,0001 = 0,1100

    Построим схему f алфавитного кодирования, выбирая в качестве элементарного кода

^v_i  ^{последовательность из 0 и 1 длины l}_i ^{, образующую дробную часть числа q}_i ^:

      

    Нетрудно  убедиться в том, что построенный  код является префиксным. 

    2.4. Алгоритмы экономного алфавитного кодирования. 

    При построении экономных кодов используется дополнительная информация о вероятностях появления букв в сообщениях.

Пусть на буквах алфавита B = { ^b₁ ^{, b}₂ ^{,…, b}_m} задано распределение вероятностей

{ p₁, p₂ ,…, p_m}, p_{i  ≥ 0,} .

    Под стоимостью кодирования f понимается величина

      

(Здесь | v_i | - длина элементарного кода буквы b_i ). 

    Стоимость кодирования определяет число двоичных разрядов, которые  тратятся в среднем на кодирование одной буквы.

    C_f (P) - это средняя длина элементарного кода, которая показывает, во сколько раз

увеличивается средняя длина слова при кодировании  f.

    Пример 2.6. Пусть B = {^b₁ ^{, b}₂ ^{, b}₃ ^{, b}₄}, P = {0,40;0,25;0,20;0,15}.

    Рассмотрим  две схемы алфавитного кодирования и определим для них стоимости

кодирования.

             

    Для  f₁ стоимость кодирования C_f1(P) = 2, для f₂ стоимость кодирования С_f2(P) = 1,95. Таким образом, стоимость кодирования может изменяться при переходе от одной схемы кодирования к другой.

    Положим C *(P) = inf_f C_f (P). Код V * со схемой f* такой, что C_{f *}( P) = C * (P), называется оптимальным для набора вероятностей P. Можно показать, что величина

C *(P) достигается при некоторой схеме f * и может быть определена как min_f C_f (P). Оптимальные коды дают в среднем минимальное увеличение длин слов при соответствующем кодировании. В силу теоремы 2.3 при построении оптимальных кодов

можно ограничиться рассмотрением префиксных кодов.

    Рассмотрим алгоритмы построения оптимальных и близких к оптимальным кодов. 

    2.4.1. Алгоритм Хаффмана (1952 г.) 

    Алгоритм  Хаффмана строит оптимальный префиксный код. При рассмотрении алгоритмов кодирования наряду с элементарными кодами вершинам кодового дерева будем приписывать вероятности соответствующих букв. Алгоритм Хаффмана основан на следующих свойствах оптимальных кодов.

    Лемма 2.1. Если код V = (v₁, v₂,…,v_m) - оптимальный для P = (p₁, p₂,…,p_m), то |v_i | ≤ | v_j| при p_i > p_j.

    Из  леммы следует, что в оптимальном дереве вероятности букв, приписанные вершинам k-го яруса, не меньше вероятностей, приписанных вершинам (k+1)-го яруса.

    Лемма 2.2. Оптимальному префиксному коду соответствует насыщенное кодовое

дерево.

    Лемма 2.3. Две самые маленькие вероятности в оптимальном кодовом дереве находятся на нижнем ярусе. Перестановкой элементарных кодов нижнего яруса их можно поставить в вершины, для которых инцидентные им ребра выходят из одной вершины.

    Теорема 2.5 (теорема редукции). Если код с длинами (l₁, l₂,…, l_m-1, l_m ) является оптимальным для распределения вероятностей P = (p₁, p₂,…,p_m-1, p_m), то код с длинами

(l₁, l₂,…, l_m-1, l_m-1) также будет оптимальным для распределения вероятностей

P = (p₁, p₂,…,p_m-1 + p_m).

    Теорема редукции позволяет свести задачу построения оптимального кода мощности m к задаче построения оптимального кода мощности m-1. На ней основан алгоритм Хаффмана, который заключается в следующем. Пусть вероятности в распределении P = (p₁, p₂,…,p_m) расположены в порядке не возрастания. На каждом шаге объединяются две буквы, имеющие наименьшие вероятности. Вместо этих двух букв вводится новая буква с вероятностью

p = p_m-1 + p_m. Вероятность p вставляется в оставшийся набор вероятностей так, чтобы в получившемся новом наборе вероятности остались расположенными в порядке не возрастания. Продолжаем процесс объединения вероятностей до тех пор, пока не останутся две буквы алфавита. Одной из них приписывается символ 0, другой – символ 1 (оптимальный код для двух букв при произвольном распределении вероятностей). Затем из оптимального кода для двух букв строится оптимальный код для трех букв, и т.д. Продолжая этот процесс, придем к искомому оптимальному коду для m букв.