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

    Пример 2.7. Пусть B = {b₁, b₂, b₃, b₄, b₅, b₆, b₇}, P=(0,20;0,20;0,19;0,12;0,11;0,09;0,09).

    Процесс построения оптимального кода можно  представить следующим образом: 

 

    Фигурными скобками отмечены объединяемые вероятности. Для каждой скобки верхнему члену  приписываем символ 0, нижнему –  символ 1. Затем осуществляем движение в обратном направлении к p₁, p₂,…, p₇ и, проходя скобки, выписываем соответствующие элементарные коды.

    Например, путь 0,60 – 0,23 – 0,11 дает элементарный код 011 для буквы b₅. Таким образом, мы получаем следующую схему f для оптимального кода:

    _{Стоимость кодирования C * ( P) = 2,78.} 

2.4.2. Алгоритм Фано (1961 г.) 

    Упорядоченный в порядке не возрастания вероятностей список букв делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписываем символ 0, а буквам из второй части – символ 1. Далее точно так же поступаем с каждой из полученных частей, если она содержит хотя бы две буквы. Построенный код является префиксным, и ему соответствует насыщенное кодовое дерево.

    В алгоритме Фано кодовое дерево строится от корня, а в алгоритме Хаффмана –  начиная с листьев. Это отличие позволяет в алгоритме Хаффмана полнее использовать специфику данного распределения вероятностей и строить оптимальный код. Алгоритм Фано строит код, близкий к оптимальному.

    Пример  2.8. Применим алгоритм Фано к тому же распределению вероятностей.

    Пусть B = {b₁, b₂, b₃, b₄, b₅, b₆, b₇}, P = (0,20;0,20;0,19;0,12;0,11;0,09;0,09). 

 

Получаем следующую  схему алфавитного кодирования:

    Стоимость кодирования C_Ф (P) = 2,80.  

    2.4.3. Алгоритм Шеннона (1948 г.)

Алгоритм Шеннона  применим в случае, когда все вероятности  p_i > 0. Букве b_i ставится в соответствие последовательность из двоичных символов (здесь - ближайшее целое сверху числа x и log здесь и везде далее берется по основанию 2). Алгоритм Шеннона основан на том, что выбранные длины l_i (i=1,2, …, m) удовлетворяют неравенству Мак-Миллана. После выбора длин применяется алгоритм Шеннона построения схемы кодирования по заданному набору длин элементарных кодов, описанный ранее.

    Пример 2.9.

    Пусть B = {b₁, b₂, b₃, b₄, b₅, b₆, b₇}, P = (0,20;0,20;0,19;0,12;0,11;0,09;0,09).

    Вычислим  набор длин для P.

      

    Построим  префиксный код по алгоритму Шеннона  с вычисленными длинами

элементарных  кодов.

    Стоимость кодирования C_Ш (P) = 3,41. 

    2.4.4. Энтропия и ее связь со стоимостью оптимального алфавитного

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

    Важную  роль для оценки эффективности кодирования  играет энтропия вероятностного распределения:

      

    Пусть C *(P) - стоимость оптимального алфавитного кодирования.

    Теорема 2.6. C *(P) ≥ H(P).

    Доказательство. Будем использовать неравенство log x ≤ (x -1) ⋅ loge. Так как для длин элементарных кодов выполняется неравенство Мак-Миллана, .

    Рассмотрим  разность H(P)-C*(P):

        

    Отсюда  C *(P) ≥ H(P).

    Теорема доказана.

    При некоторых распределениях стоимость C *(P) может достигать нижней границы.

    Пример  2.10. Рассмотрим распределение вероятностей .

Вычислим C(m) = C(P_m).

Положим . Получим

l₁ = 1, l₂ = 2,…, l_i = i,…,l_m-2 = m -2, l_m-1 = l_m = m -1.

    Величины  l_i удовлетворяют неравенству Мак-Миллана, следовательно, существует

префиксный код  с таким набором длин элементарных кодов. Так как p_i являются степенью двойки, l_i = - log p_i , поэтому

      

    В общем же случае C *(P) = H(P) + ε , где 0 ≤ ε <1, как показывает следующая теорема. 

    Теорема 2.7. C *(P) < H(P) +1.

    Доказательство. Возьмем l_i = - log p_i , (i =1,…,m) . Тогда откуда

.Т.е. набор длин (l₁,…,l_m) реализуем.

    Но l_i  < - log p_i +1, откуда p_il_i < - p_i log p_i + p_i и суммируя по i, получаем:

      

    Теорема доказана.

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

    Дополнительные  возможности для сжатия могут возникнуть при конечно-автоматном кодировании. Вместо того, чтобы кодировать каждую букву, разобьем сообщение на блоки длины N, которые и будем кодировать как буквы нового алфавита B_N .

    Пусть P_N - распределение вероятностей на B_N , которое индуцируется распределением P на B:

    

    Теорема 2.8. H(P_N ) = N⋅ H(P).

    Доказательство  проведем индукцией по N. При N = 1 утверждение теоремы тривиально.

    Пусть теорема верна при N = 2,…,k -1. Тогда 

        

    Теорема доказана.

    Покажем, что, выбирая длину блока N достаточно большой, можно сделать стоимость кодирования на одну букву сообщения C_N (P) сколь угодно близкой к H(P).

    Теорема 2.9. .

Доказательство. Имеем:

N ⋅ H(P) = H(P_N ) ≤ C(P_N ) = N ⋅C_N (P) < H(P_N )+1 = N ⋅ H(P) +1.

    Отсюда получаем:

    

При N → ∞ C_N (P) →H(P). Теорема доказана.

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

    Пример 2.11. Пусть B = {^b₁ ^{, b}₂ ^{, b}₃ }, P = {0,5;0,4;0,1}.

    Применяя  алгоритм Хаффмана к распределению  P, получаем следующую схему кодирования:

     

    Вычислим  стоимость оптимального кодирования: C₁ = 1,5.

    Положим N = 2 и рассмотрим всевозможные блоки длины 2. Определим произведение вероятностей каждого блока как произведение вероятностей входящих в него букв:

              

    Применяя  алгоритм Хаффмана к построенному вероятностному распределению, получим следующую схему кодирования для блоков длины N=2:

      

    Построенная схема имеет стоимость кодирования  одного блока C₂ = 2,78, и стоимость кодирования одной буквы . Найдем энтропию H(P):

    H(P) = -(0,5 ⋅ log0,5 + 0,4 ⋅ log0,4 + 0,1⋅ log0,1) ≈1,36.

Получаем H(P) ≈ 1,36 <

    2.4.5. Возможности сжатия при алфавитном кодировании, учитывающем

синтаксис языка сообщений. 

    Дополнительные  возможности для сжатия появляются при L ⊂ B* , когда в качестве

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

них.

    Пример  2.12 алфавитного кодирования, учитывающего синтаксис языка сообщений:

    В качестве языка L рассмотрим множество слов в алфавите B = {^b₁ ^{, b}₂ ^{, b}₃ }, не содержащих диаграмму b₁ b₂ . Синтаксис этого языка описывается источником с двумя состояниями, изображенным на рис.2.4. 

 

Рис. 2.4. Источник, генерирующий сообщения, не содержащие диграмму b₁b₂. 

    Приведем  для этого языка две схемы  кодирования. Первая схема построена без учета синтаксиса языка, вторая учитывает запрещенную диграмму b₁b₂.

    Так как диграмма b₁b₂ не может встречаться в словах языка L, буква b₃ может быть закодирована последовательностью 10.

    Насколько эффективно можно использовать те или  иные свойства языка для сжатия информации при алфавитном кодировании?

    В языке сообщений может присутствовать алфавитная избыточность: некоторые буквы алфавита могут быть фиктивными или контекстно-различимыми. Поясним эти понятия.

    Определение 2.4. Пусть B = {^b₁ ^{,... , b}_m} и L ⊆ B*. Буква b_i называется фиктивной в L, если отображение α → a', состоящее в замене b_i пустым словом λ во всех вхождениях b_i в α, таково, что из α,β ∈ L и a ≠ b следует a'≠ b '. В противном случае буква b_i называется существенной в L.

    Буквы b_i и b_j (i ≠ j) называются контекстно-различимыми в L, если отображение

  α → a', состоящее в замене b_i буквой b_j во всех вхождениях b_i в α, таково, что из α,β ∈ L и a ≠ b следует a'≠ b' .

    Определение 2.5. Язык L называется неприводимым, если все его буквы

существенные  и попарно контекстно-неразличимы. В противном случае говорят, что L

допускает алфавитную редукцию.

    За  счет алфавитной избыточности можно  сжимать сообщения языка в  любое число