Методы кодирования данных (Необходимые понятия и определения)

ВВЕДЕНИЕ

Теория кодирования и теория информации возникли в начале XX века. Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. статей К. Шеннона, которые заложили фундамент для дальнейших исследований в этой области.

Детальное рассмотрение вопроса, что такое кодирование и декодирование информации является фундаментальной необходимостью. Для передачи информации люди используют естественные языки. В повседневной жизни мы общаемся с помощью неформальной речи, а в деловой сфере используем формальный язык. Сегодня для передачи и отображения информации мы используем вычислительную технику, которая «не понимает» наш язык без специальных операций – кодирования и декодирования.

Код — это набор условных обозначений (или сигналов) для записи (или передачи) некоторых заранее определенных понятий.

Кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

Обычно каждый образ при кодировании (иногда говорят — шифровке) представлении отдельным знаком.

Знак - это элемент конечного множества отличных друг от друга элементов.

В более узком смысле под термином "кодирование" часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

Компьютер может обрабатывать только информацию, представленную в числовой форме. Вся другая информация (например, звуки, изображения, показания приборов и т. д.) для обработки на компьютере должна быть преобразована в числовую форму. Например, чтобы перевести в числовую форму музыкальный звук, можно через небольшие промежутки времени измерять интенсивность звука на определенных частотах, представляя результаты каждого измерения в числовой форме. С помощью программ для компьютера можно выполнить преобразования полученной информации, например "наложить" друг на друга звуки от разных источников.

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

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

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

НЕОБХОДИМЫЕ ТЕРМИНЫ И ПОНЯТИЯ

В связи с развитием информационных технологий кодирование является центральным вопросом при решении самых разных задач программирования, таких как:

• 1. представление данных произвольной структуры (числа, текст, графика) в памяти компьютера;
  2. обеспечение помехоустойчивости при передаче данных по каналам связи;
  3. сжатие информации в базах данных.

Основной моделью, которую изучает теория информации, является модель системы передачи сигналов:

Шум

Источник

Кодер

источника

Канал

Приемник

Кодер

канала

Декодер

канала

Декодер

источника

Рисунок 1 Модель системы передачи сигналов

Начальным звеном в приведенной выше модели является источник информации. Здесь рассматриваются дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита. Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, а количество символов в этом множестве – размером алфавита источника. Например, можно считать, что текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. Причем обычно символу исходного алфавита А ставится в соответствие не один, а группа символов алфавита В, которая называется кодовым словом. Кодовый алфавит – множество различных символов, используемых для записи кодовых слов. Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов.

Пример. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

Далее будем рассматривать двоичное кодирование, т.е. размер кодового алфавита равен 2. Конечную последовательность битов (0 или 1) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Пример. Код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.

Дадим строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех возможных сообщений в алфавите А обозначим S. Тогда отображение , которое преобразует множество сообщений в кодовые слова в алфавите В, называется кодированием. Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.

Задача кодирования сообщения ставится следующим образом. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными. Приведем некоторые из них:

1. существование декодирования;
2. помехоустойчивость или исправление ошибок при кодировании: декодирование обладает свойством , β~β (эквивалентно β с ошибкой);
3. обладает заданной трудоемкостью (время, объем памяти).

Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше символов, где m – размер исходного алфавита, n – размер кодового алфавита.

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

При неравномерном кодировании источника используются кодовые слова разной длины. Причем кодовые слова обычно строятся так, что часто встречающиеся символы кодируются более короткими кодовыми словами, а редкие символы – более длинными (за счет этого и достигается «сжатие» данных).

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

Методы сжатия данных можно разделить на две группы: статические методы и адаптивные методы. Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Эти методы базируются на знании статистической структуры исходных данных. К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известные сведения о вероятностях порождения источником различных символов или их сочетаний.

Если статистика источника информации неизвестна или изменяется с течением времени, то для кодирования сообщений такого источника применяются адаптивные методы сжатия. В адаптивных методах при кодировании очередного символа текста используются сведения о ранее закодированной части сообщения для оценки вероятности появления очередного символа. В процессе кодирования адаптивные методы «настраиваются» на статистическую структуру кодируемых сообщений, т.е. коды символов меняются в зависимости от накопленной статистики данных. Это позволяет адаптивным методам эффективно и быстро кодировать сообщение за один просмотр.

Существует множество различных адаптивных методов сжатия данных. Наиболее известные из них – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды, а также методы из класса Лемпела-Зива.

1. Кодирование целых чисел

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

Основная идея кодирования состоит в том, чтобы отдельно кодировать порядок значения числа («экспоненту» ) и отдельно – значащие цифры числа («мантиссу» ). Значащие цифры мантиссы начинаются со старшей ненулевой цифры, а порядок числа определяется позицией старшей ненулевой цифры в двоичной записи числа. Как и при десятичной записи, порядок равен числу цифр в записи числа без предшествующих незначащих нулей.

Пример. Порядок двоичного числа 000001101 равен 4, а мантисса – 1101.

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

• Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы)
• Variable + Variable (переменная длина экспоненты + переменная длина мантиссы)
  1. Коды класса Fixed + Variable

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.

Пример. Пусть R = 15 – количество бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤2⁴. При записи мантиссы можно сэкономить 1 бит: не писать первую единицу, т.к. это всегда будет только единица. Таким образом, количество бит мантиссы меньше на один бит, чем количество бит для порядка.

Таблица 1 Код класса Fixed + Variable

число	двоичное представление	кодовое слово	длина кодового слова
0 1	000000000000000 000000000000001	0000 0001	4 4
2 3	000000000000010 000000000000011	0010 0 0010 1	5 5
4 5 6 7	000000000000100 000000000000101 000000000000110 000000000000111	0011 00 0011 01 0011 10 0011 11	6 6 6 6
8 9 10 … 15	000000000001000 000000000001001 000000000001010 … 000000000001111	0100 000 0100 001 0100 010 … 0100 111	7 7 7 .. 7
16 17 …	000000000010000 000000000010001 …	0101 0000 0101 0001 …	8 8 ..

• 1. Коды класса Variable + Variable

В качестве кода числа берется двоичная последовательность, построенная следующим образом: несколько нулей (количество нулей равно значению порядка числа), затем единица как признак окончания экспоненты переменной длины, затем мантисса переменной длины (как в кодах Fixed + Variable). Рассмотрим пример построения кода этого класса.

Таблица 2 Код класса Variable + Variable

число	двоичное представление	кодовое слово	длина кодового слова
0 1	00000000000 00000000001	1 0 1	1 2
2 3	00000000010 00000000011	00 1 0 00 1 1	4 4
4 5 6 7	00000000100 00000000101 00000000110 00000000111	000 1 00 000 1 01 000 1 10 000 1 11	6 6 6 6
8 9 10 …	00000001000 00000001001 00000001010 …	0000 1 000 0000 1 001 0000 1 010 …	8 8 8

Если в рассмотренном выше коде исключить кодовое слово для нуля, то можно уменьшить длины кодовых слов на 1 бит, убрав первый нуль. Таким образом строится гамма-код Элиаса (γ-код Элиаса).

Таблица 3 Гамма-код Элиаса

число	кодовое слово	длина кодового слова
1	1	1
2 3	01 0 01 1	3 3
4 5 6 7	00 1 00 00 1 01 00 1 10 00 1 11	5 5 5 5
8 9 10 …	000 1 000 000 1 001 000 1 010 …	7 7 7

Другим примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной , начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые групп служат лишь для указания длины последней группы.

Таблица 4 Омега-код Элиаса

число	кодовое слово	длина кодового слова
1 2 3	0 10 0 11 0	1 3 3
4 5 6 7	10 100 0 10 101 0 10 110 0 10 111 0	6 6 6 6
8 9 .. 15	11 1000 0 11 1001 0 … 11 1111 0	7 7 .. 7
16 17 .. 31	10 100 10000 0 10 100 10001 0 … 10 100 11111 0	11 11 .. 11
32	10 101 100000 0	12

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

Рассмотренные типы кодов могут быть эффективны в следующих случаях

1. Вероятности чисел убывают с ростом значений элементов и их распределение близко к такому: , при любом x, т.е. маленькие числа встречаются чаще, чем большие.
2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.
3. При использовании в составе других схем кодирования, например, кодировании длин серий.
   1. Кодирование длин серий

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

Пример. Входную последовательность (общая длина 31бит) можно разбить на серии, а затем закодировать их длины.

000000 1 00000 1 0000000 1 1 00000000 1

Используем, например, γ-код Элиаса. Поскольку в коде нет кодового слова для нуля, то будем кодировать длину серии +1, т.е. последовательность 7 6 8 1 9:

7 6 8 1 9  00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности равна 25 бит.

Метод длин серий актуален для кодирования данных, в которых есть длинные последовательности одинаковых бит. В нашем примере, если .

1. Некоторые теоремы ПОБУКВЕННОГО кодирования

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

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

Пример 1 А={a₁,a₂,a₃}, B={0,1} Побуквенное кодирование символов источника a₁ 1001 a₂ 0 a₃010

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

a₂a₁a₂a₃  010010010

Пример 2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:

А  01, В  1000, С  1010, D  100, E  0, …

Побуквенное кодирование задается таблицей кодовых слов: , , . Множество кодовых слов V={β_i} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом , т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.

Количество букв в слове α=α₁…α_k называется длиной слова. (Обозначение |α|=k) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается Λ. Если α=α₁α₂, то α₁ – начало (префикс) слова α, α₂ – окончание (постфикс) слова α.

Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если β_i1 …β_ik=β_j1…β_jt , то k=t и при любых s=1,…,k i_s=j_s . При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

Пример. 3 Код из примера 1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами: a₃a₃ или a₂a₁a₂.

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

Пример 4. Код из примера 1 не является префиксным, поскольку элементарный код буквы a₂ является префиксом элементарного кода буквы a₃.

Утверждение. Префиксный код является разделимым.

Доказательство (от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность β, что она представлена различными способами из элементарных кодов: (побитовое представление одинаковое) и существует L такое, что при любом следует (β_is=β_js) и (β_it≠β_jt), т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда , т.е. последовательности элементарных кодов разные и существует β^/, что β_iL=β_jLβ^/ или β_jL=β_iLβ^/ , т.е. β_iL – начало β_jL, или наоборот. Получили противоречие с префиксностью кода.

Заметим, что разделимый код может быть не префиксным.

Пример 5. Разделимый, но не префиксный код: A={a,b}, B={0,1},

Приведем основные теоремы побуквенного кодирования.

Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов L₁,…,L_n необходимо и достаточно, чтобы

.

Доказательство. Докажем необходимость. Пусть существует префиксный код с длинами L₁,…,L_n. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).

011



0

1

00

01

10

11

000

001

010

100

101

110

111

Рисунок 2 Полное двоичное дерево с помеченными вершинами

В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – 2^r-Li вершин. Всего вершин в поддереве 2^r. Тогда, , .

Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию L₁≤ L₂≤ … ≤ L_n. Выберем в двоичном дереве вершину V₁ на уровне L₁. Уберем поддерево с корнем в вершине V₁. В оставшемся дереве возьмем вершину V₂ на уровне L₂ и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам V₁, V₂,…, V_n образуют префиксный код. Теорема доказана.

Пример 6. Построить префиксный код с длинами L₁=1, L₂=2, L₃=2 для алфавита A={a₁,a₂,a₃}. Проверим неравенство Крафта для набора длин

.

Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с 2³ помеченными вершинами и выберем вершины дерева, как описано выше. Тогда элементарные коды могут быть такими: a₁ 0, a₂10, a₃ 11.



0

1

00

01

10

11

000

001

010

011

100

101

110

111

a₁

a₂

a₃

Рисунок 3 Построение префиксного кода с заданными длинами

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

Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов L₁,…,L_n , необходимо и достаточно, чтобы .

Доказательство. Покажем достаточность. По теореме Крафта существует префиксный код с длинами L₁,…,L_n, и он является разделимым.

Докажем необходимость утверждения. Рассмотрим тождество

Положим . Тогда тождество можно переписать следующим образом

,

где , – число всевозможных представлений числа j в виде суммы . Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу

,

где b_s – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом, и . Используя предельный переход получим при . Теорема доказана.

Пример 7. Азбука Морзе – это схема алфавитного кодирования

A01, B1000, C1010, D100, E0, F0010, G110, H0000, I00, J0111, K101, L0100, M11, N10, O111, P0110, Q1101, R010, S000, T1, U001, V0001, W011, X1001, Y1011, Z1100.

Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку

Следовательно, этот код не является разделимым. На самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщение. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений (особенно с высокой скоростью) является некоторым искусством, а не простой технической процедурой.

1. оптимальное ПОБУКВЕННОЕ кодирование
   1. Основные понятия

При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник называется дискретным вероятностным источником.

Если вероятностный источник с алфавитом А={a₁, a₂, ..., a_n} порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любой последовательности x₁x₂...x_L, L≥1, порождаемой источником, выполняется равенство:

P(x₁x₂...x_L ) = P(x₁)·P(x₂)·...·P(x_L),

где P(x) – вероятность появления символа х, Р(x₁x₂x₃...x_L) – вероятность появления последовательности x₁x₂x₃...x_L.

Для другого класса источников (марковских) существует статистическая взаимосвязь между порождаемыми символами. В дальнейшем мы будем рассматривать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти.

Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита А={a₁,…,a_n} с вероятностями , . Основной характеристикой источника является энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)

.

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

Пример. Если А={a₁,a₂}, p₁=0, p₂ =1, т.е. источник может породить только символ a₂, то неопределенности нет, энтропия H(p₁,p₂)=0.

Источник с равновероятными символами А={a₁,a₂}, p₁ =1/2, p₂ =1/2, будет иметь максимальную энтропию H(p₁,p₂)=1.

Величина называется энтропией на символ последовательности длины L, где A^L  множество всех последовательностей длины L в алфавите A, x=(x₁,x₂,...,x_L)  последовательность L букв дискретного cтационарного источника. Обозначим через предел энтропии H_L при L  . Эту величину называют предельной энтропией источника. Показано, что для стационарного бернуллиевского источника

.

Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения. Пусть имеется разделимый побуквенный код для источника, порождающего символы алфавита А={a₁,…,a_n} с вероятностями p_i =P(a_i), состоящий из n кодовых слов с длинами L₁,…,L_n в алфавите {0,1}. Средней длиной кодового слова называется величина , которая показывает среднее число кодовых букв на одну букву источника.

Пример. Пусть имеются два источника с одним и тем же алфавитом А={a₁,a₂,a₃} и разными вероятностными распределениями P₁={1/3, 1/3, 1/3}, P₂={1/4, 1/4, 1/2}, которые кодируются одним и тем же кодом

.

Средняя длина кодового слова для разных источников будет различной

L_ср(P₁)=1/3^.2 + 1/3^.3 + 1/3^.2= 7/3 ≈2.33

L_ср(P₂)=1/4^.2 + 1/4^.3 + 1/2^.2= 9/4 =2.25

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

Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений

.

Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.

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

Теорема 1 (Шеннон). Для источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i), и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии

L_cp ≥ H(p₁,…,p_n)

и можно построить разделимый побуквенный код, у которого средняя длина кодового слова превосходит энтропию не больше, чем на единицу:

L_cp < H(p₁,…,p_n)+1

Можно получить более сильные результаты, если кодовые слова приписывать не отдельными буквами, а блоками из L букв источника. Так, для неравномерных блоковых кодов справедлива следующая теорема.

Теорема 2. Пусть H_L  энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова L_cp будет удовлетворять неравенствам:

.

Кроме того, в случае бернуллиевского стационарного источника для любого >0 можно выбрать достаточно большое L, чтобы величина L_cp удовлетворяла неравенствам:

,

и левое неравенство для L_cp никогда не нарушается для разделимого кода.

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

Лемма 1. Для оптимального кода с длинами кодовых слов L₁,…,L_n: верно соотношение L₁≤L₂≤…≤L_{n ,} если p₁≥p₂≥…≥p_n.

Доказательство (от противного): Пусть есть i и j, что L_i>L_j при p_i>p_j. Тогда

L_ip_i+L_jp_j=

=L_ip_i+L_jp_j+L_ip_j+L_jp_i-L_ip_j-L_jp_i=

=p_i(L_i-L_j)-p_j(L_i-L_j)+L_jp_i+L_ip_j=

=(p_i-p_j)(L_i-L_j) +L_ip_j+L_jp_i>L_ip_j+L_jp_i,

т.е. если поменяем местами L_i и L_j, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.

Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей Р, . Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.

Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид , . Тогда длина любого элементарного кода не больше длины b, т.е. , . Поскольку схема кодирования префиксная, то кодовые слова не являются префиксом b. С другой стороны, b не является префиксом кодовых слов . Таким образом, новая схема кодирования также является префиксной, причем с меньшей средней длиной кодового слова , что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова и максимальной длины отличаются не в последнем разряде, т.е. , , , . Причем , не являются префиксами для других кодовых слов и наоборот. Тогда новая схема также является префиксной, причем , что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.

• 1. Оптимальный код Хаффмана

Метод оптимального побуквенного кодирования был разработан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i).

Рассмотрим алгоритм построения оптимального кода Хаффмана, который основывается на утверждениях лемм предыдущего параграфа.

1. Упорядочим символы исходного алфавита А={a₁,…,a_n} по убыванию их вероятностей p₁≥p₂≥…≥p_n.
2. Если А={a₁,a₂}, то a₁0, a₂1.
3. Если А={a₁,…,a_j,…,a_n} и известны коды <a_j  b_j >, j = 1,…,n, то для алфавита {a₁,…a_j^/, a_j^//…,a_n} с новыми символами a_j^/ и a_j^// вместо a_j, и вероятностями p(a_j)=p(a_j^/)+ p(a_j^//), код символа a_j заменяется на коды a_j^/  b_j0, a_j^// b_j1.

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями

p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07.

Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.

a₁ 0.36 0.36 0.36 0.36 0.64 0

a₂ 0.18 0.18 0.28 0.36 0.36 1

a₃ 0.18 0.18 0.18 0.28 00

a₄ 0.12 0.16 0.18 000 01

a₅ 0.09 0.12 010 001

a₆ 0.07 0100 011

0101

Рисунок 4 Процесс построения кода Хаффмана

Таблица 5 Код Хаффмана

ai	pi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	0.36 0.18 0.18 0.12 0.09 0.07	2 3 3 4 4 4	1 000 001 011 0100 0101

Посчитаем среднюю длину, построенного кода Хаффмана

L_ср(P)=1^.0.36 + 3^.0.18 + 3^.0.18 + 3^.0.12 + 4^.0.09 + 4^.0.07 =2.44,

при этом энтропия данного источника

H(p₁,…,p₆) = − 0.36^.log0.36 − 2^.0.18^.log0.18 −

− 0.12^.log0.12 − 0.09^.log0.09 − 0.07log0.07=2.37



0

1

а₁

00

01

000

001

010

011

0100

0101

а₂

а₃

а₄

а₆

а₅

Рисунок 5 Кодовое дерево для кода Хаффмана

Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 собираются в одну уникальную последовательность (рис. 5).

Алгоритм на псевдокоде

Построение оптимального кода Хаффмана (n,P)

Обозначим

n – количество символов исходного алфавита

P – массив вероятностей, упорядоченных по убыванию

C – матрица элементарных кодов

L – массив длин кодовых слов

Huffman (n,P)

IF (n=2) C [1,1]:= 0, L [1]:= 1

C [2,1]:=1, L [2]:=1

ELSE q:= P [n-1]+P [n]

j:= Up (n,q) (поиск и вставка суммы)

Huffman (n-1,P)

Down (n,j) (достраивание кодов)

FI

Функция Up (n,q) находит в массиве P место, куда вставить число q, и вставляет его, сдвигая вниз остальные элементы.

DO (i=n-1, n-2,…,2)

IF (P [i-1]≤q) P [i]:=P [i-1]

ELSE j:=i

OD

FI

OD

P [j]:= q

Процедура Down (n,j) формирует кодовые слова.

S:= C [j,*] (запоминание j-той строки матрицы элем. кодов в массив S)

L:= L[j]

DO (i=j,…,n-2)

C [i,*]:= C[i+1,*] (сдвиг вверх строк матрицы С)

L [i]:=L [i+1]

OD

C [n-1,*]:= S, C [n,*]:= S (восстановление префикса кодовых слов из м-ва S)

C [n-1,L+1]:=0

C [n,L+1]:=1

L [n-1]:=L+1

L [n]:=L+1

1. почти оптимальное кодирование

Рассмотрим несколько классических побуквенных кодов, у которых средняя длина кодового слова близка к оптимальной. Пусть имеется дискретный вероятностный источник, порождающий символы алфавита А={a₁,…,a_n} с вероятностями p_i = P(a_i).

• 1. Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона из п. 5.1

.

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита А={a₁,a₂,…,a_n} по убыванию их вероятностей: p₁≥p₂≥p₃≥…≥p_n.
2. Вычислим величины Q_i:, которые называются кумулятивные вероятности

Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1.

1. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые знаков после запятой .

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения

, .

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 6.

Таблица 6 Код Шеннона

ai	Pi	Qi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	1/22≤0.36<1/2 1/23≤0.18<1/22 1/23≤0.18<1/22 1/24≤0.12<1/23 1/24≤0.09<1/23 1/24≤0.07<1/23	0 0.36 0.54 0.72 0.84 0.93	2 3 3 4 4 4	00 010 100 1011 1101 1110

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана в п. 5.2 (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона

L_ср= 0.36^.2+(0.18+0.18)^.3+(0.12+0.09+0.07)^.4=2.92< 2.37+1,

что полностью соответствует утверждению теоремы Шеннона.

Алгоритм на псевдокоде

Построение кода Шеннона

Обозначим

n – количество символов исходного алфавита

P – массив вероятностей, упорядоченных по убыванию

Q– массив для величин Q_i

L – массив длин кодовых слов

C – матрица элементарных кодов

P [0]:=0, Q [0]:=0

DO (i=1,…,n)

Q [i] := Q [i-1]+P [i]

L [i]:= - log₂P[i]  (длину кодового слова определять

OD из соотношения, указанного выше)

DO (i=1,…,n)

DO (j=1,…,L[i])

Q [i-1]:=Q [i-1] _*2 (формирование кодового слова

C [i,j]:= Q [i-1] в двоичном виде)

IF (Q [i-1]>1) Q [i-1]:=Q [i-1] - 1 FI

OD

OD

• 1. Код Фано

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

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 7 и на рисунке 6.

Таблица 7 Код Фано

ai	Pi	кодовое слово				Li
a1	0.36	0	0			2
a2	0.18	0	1			2
a3	0.18	1	0			2
a4	0.12	1	1	0		3
a5	0.09	1	1	1	0	3
a6	0.07	1	1	1	1	4

Λ

0

1

00

01

10

11

110

111

1110

1111

а₁

а₂

а₃

а₄

а₅

а₆

Рисунок 6 Кодовое дерево для кода Фано

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

L_ср=0.36^.2+0.18^.2+0.18^.2+0.12^.3+0.09^.4+0.07^.4=2.44

Алгоритм на псевдокоде

Построение кода Фано

Обозначим

P–массив вероятностей символов алфавита

L – левая граница обрабатываемой части массива P

R– правая граница обрабатываемой части массива P

k – длина уже построенной части элементарных кодов

С – матрица элементарных кодов

Length – массив длин элементарных кодов

S_L – сумма элементов первой части массива

S_R – сумма элементов второй части массива.

Fano (L,R,k)

IF (L<R)

k:=k+1

m:=Med (L,R)

DO (i=L,…,R)

IF (i≤m) C [i,k]:=0, Length [i]:= Length [i]+1

ELSE C [i,k]:=1, Length [i]:= Length [i]+1

FI

OD

Fano (L,m,k)

Fano (m+1,R,k)

FI

Функция Med находит медиану части массива P, т.е. такой индекс L≤m≤R, что величина минимальна.

Med (L,R)

S_L:= 0

DO (i=L,…,R-1)

S_L:=S_L+ P [i]

OD

S_R:=P [R]

m:= R

DO (S_L ≥ S_R)

m:=m-1

S_L:=S_L - P [m]

S_R:=S_R+ P [m]

OD

Med:= m

• 1. Алфавитный код Гилберта – Мура

Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого .

Пусть символы алфавита некоторым образом упорядочены, например, a₁≤a₂≤…≤a_n. Код называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. .

Процесс построения кода происходит следующим образом.

1. Вычислим величины Q_i, i=1,n:

Q₁=p₁/2,

Q₂=p₁+p₂/2,

Q₃=p₁+p₂+p₃/2,

…

Q_n=p₁+p₂+…+p_n-1+p_n/2.

1. Представим суммы Q_i в двоичном виде.
2. В качестве кодовых слов возьмем младших бит в двоичном представлении Q_i, .

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 8.

Таблица 8 Код Гилберта-Мура

ai	Pi	Qi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	1/23≤0.18 1/23≤0.18<1/22 1/22≤0.36<1/21 1/24≤0.07 1/24≤0.09 1/24≤0.12	0.09 0.27 0.54 0.755 0.835 0.94	4 4 3 5 5 5	0001 0100 100 11000 11010 11110

Средняя длина кодового слова не превышает значения энтропии плюс 2. Действительно,

L_ср=4^.0.18+4^.0.18+3^.0.36+5^.0.07+5^.0.09+5^.0.12=3.92<2.37+2

Алгоритм на псевдокоде

Построение кода Гилберта-Мура

Обозначим

n – количество символов исходного алфавита

P – массив вероятностей символов

Q – массив для величин Q_i

L – массив длин кодовых слов

C – матрица элементарных кодов

pr:=0

DO (i=1,…,n)

Q [i]:= pr+ P[i] /2

pr:=pr+ P[i]

L [i]:= - log₂P[i]  +1 (использовать соотношение из п. 6.1)

OD

DO (i=1,…,n)

DO (j=1,…,L[i])

Q [i]:=Q [i] _*2 (формирование кодового слова

C [i,j]:= Q [i] в двоичном виде)

IF (Q [i] >1) Q [i]:=Q [i] - 1 FI

OD

OD

1. арифметический код

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

Рассмотрим общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита А={a₁,a₂,…,a_n} с вероятностями p_i=P(a_i), . Необходимо закодировать последовательность символов данного источника Х=х₁х₂х₃х_4.

1. Вычислим кумулятивные вероятности Q₀ ,Q₁,…,Q_n:

Q₀=0

Q₁=p₁

Q₂=p₁+p₂

Q₃=p₁+p₂+p₃

...

Q_n=p₁+p₂+…+p_n=1

1. Разобьем интервал [Q₀,Q_n) (т.е. интервал [0,1)) так, чтобы каждой букве исходного алфавита соответствовал свой интервал, равный ее вероятности (см. рис. 7):

a₁ [Q₀,Q₁)

a₂ [Q₁,Q₂)

a₃ [Q₂,Q₃)

a₄ [Q₃,Q₄)

...

a_n [Q_n-1,Q_n)

• 1. В процессе кодирования будем выбирать интервал, соответствующий текущей букве исходного сообщения, и снова разбивать его пропорционально вероятностям исходных букв алфавита. Постепенно происходит сужение интервала до тех пор, пока не будет закодирован последний символ кодируемого сообщения. Двоичное представление любой точки, расположенной внутри интервала, и будет кодом исходного сообщения.

На рисунке 7 показан этот процесс для кодирования последовательности а₃а₂а₃…

x₁=a₃

a₁

a₂

a₃

…

a_n

Q₁

Q₂=p₁+p₂

Q₃=p₁+p₂+p₃

Q_n

x₂=a₂

a₁

a₂

a₃

…

a_n

x₃=a₃

Рисунок 7 Схема арифметического кодирования

Для удобства вычислений введем следующие обозначения:

l_i  нижняя граница отрезка, соответствующего i-той букве исходного сообщения;

h_i  верхняя граница этого отрезка;

r_i  длина отрезка [l_i, h_i), т.е. r_i = h_i  l_i.

Возьмем начальные значения этих величин

l₀ = Q₀=0, h₀ = Q_k=1, r₀ = h₀  l₀=1

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

, ,

где m  порядковый номер кодируемой буквы в алфавите источника, m=1,...,n.

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

Для однозначного декодирования исходной последовательности достаточно взять разрядов двоичной записи любой точки из интервала [l_i,h_i), где r_k  длина интервала после кодирования k символов источника.

Пример. Рассмотрим кодирование бесконечной последовательности X=a₃a₂a₃a₁a₄... в алфавите A={a₁, a₂, a₃, a₄} с помощью арифметического кода. Пусть вероятности букв исходного алфавита равны соответственно

p₁ = 0.1, p₂ = 0.4, p₃ = 0.2, p₄ = 0.3.

Вычислим кумулятивные вероятности Q_i :

Q₀ = 0,

Q₁ =p₁ = 0.1,

Q₂ =p₁+p₂ = 0.5,

Q₃ =p₁+p₂+p₃ = 0.7,

Q₄ =p₁ +p₂ +p₃ + p₄ = 1.

Получим границы интервала, соответствующего первому символу кодируемого сообщения a₃:

l₁ = l₀ + r₀·Q₂ = 0 + 1·0.5 = 0.5,

h₁ = l₀ + r₀·Q₃ = 0 + 1·0.7 = 0.7,

r₁ = h₁  l₁ = 0.7  0.5 = 0.2.

Для второго символа кодируемого сообщения a₂ границы интервала будут следующие:

l₂ = l₁ + r₁·Q₁ = 0.5 + 0.2·0.1 = 0.52,

h₂ = l₁ + r₁·Q₂ = 0.5 + 0.2·0.5 = 0.6,

r₂ = h₂  l₂ = 0.6  0.52 = 0.08 и т.д.

В результате всех вычислений получаем следующую последовательность интервалов для сообщения a₃a₂a₃a₁a₄

В начале [0.0, 1.0)

После пpосмотpа a₃ [0.5, 0.7)

После пpосмотpа a₂ [0.52, 0.6)

После пpосмотpа a₃ [0.56, 0.576)

После пpосмотpа a₁ [0.56, 0.5616)

После пpосмотpа a₄ [0.56112, 0.5616)

Кодом последовательности a₃a₂a₃a₁a₄ будет двоичная запись любой точки из интервала [0.56112, 0.5616), например, 0.56112. Для однозначного декодирования возьмем log₂(r₅) = log₂(0.00048) = 12 разрядов, получим 100011111010.

Таким образом, при арифметическом кодировании сообщение представляется вещественными числами в интервале [0,1). По мере кодирования сообщения отображающий его интервал уменьшается, а количество битов для представления интервала возрастает. Очередные символы сообщения сокращают величину интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и следовательно, добавляют меньше битов к результату.

Алгоритм на псевдокоде

Арифметическое кодирование

Обозначим

l  массив нижних границ интервалов при кодировании

h  массив верхних границ интервалов при кодировании

r  массив длин интервалов

m  порядковый номер кодируемой буквы в алфавите источника

Q – массив для величин Q_i.

l[0]:=0; h[0]:=1; r[0]:=1; i:=0

DO (not EOF)

C:=Read ( ) (читаем следующий символ из файла)

i:=i+1

DO (j=1,…,n)

IF (C= a_j) m:=j FI

OD

l [i] = l [i-1] + r [i-1]·Q [m-1]

h [i] = l [i-1] + r [i-1]·Q [m]

r [i] = h [i]  l [i]

OD

В начале декодирования известен конечный интервал, например, [0.56112; 0.5616) или любое число из этого интервала, например, 0.56112. Сразу можно определить, что первым закодированным символом был а₃, т. к. число 0.56112 лежит в интервале [0.5; 0.7), выделенном символу а₃. Затем в качестве интервала берется [0.5; 0.7) и в нем определяется диапазон, соответствующий числу 0.56112. Это интервал [0.52, 0.6), выделенный символу а₂ и т.д. Для декодирования необходимо знать количество закодированных символов и исходные вероятности символов.

Алгоритм на псевдокоде

Арифметическое декодирование

Обозначим

l  массив нижних границ интервалов при кодировании

h  массив верхних границ интервалов при кодировании

r  массив длин интервалов

Q – массив для величин Q_i

length – количество закодированных символов,

value – значение из входного файла.

l [0] :=0; h [0] :=1; r [0] :=1;

value:=ReadCode(); (читаем код из файла)

DO (i=1,…,length)

DO (j=1,…,n)

l [i] = l [i-1] + r [i-1]·Q [j-1]

h [i] = l [i-1] + r [i-1]·Q [j]

r [i] = h [i]  l [i]

IF (( l [i] <= value ) и ( value< h [i] ) OD FI

OD

Write(a[i]) (пишем символ в выходной файл)

OD

Заметим, что при кодировании и декодировании для экономии памяти достаточно использовать не массивы, а переменные l, r и h.

При реализации арифметического кодирования возникают две проблемы:

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

Для решения этих проблем реальные алгоритмы работают с целыми числами и оперируют с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен 10000h=65536, l₀=0, h₀=65535). При этом с потерей точности можно бороться, отслеживая сближение l_i и h_i и умножая числитель и знаменатель представляющей их дроби на одно и то же число, например на 2. С переполнением сверху можно бороться, записывая старшие биты l_i и h_i в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда l_i и h_i одновременно находятся в верхней или нижней половине интервала.

1. адаптивные методы кодирования

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

Большинство адаптивных методов для учета изменений статистики исходных данных используют так называемое окно. Окном называют последовательность символов, предшествующих кодируемой букве, а длиной окна  количество символов в окне.

Обычно окно имеет фиксированную длину и после кодирования каждой буквы текста окно передвигается на один символ вправо. Таким образом, код для очередной буквы строится с учетом информации, хранящейся в данный момент в окне (см. рис. 8).

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

Рисунок 8 Схема перемещения окна при кодировании

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

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

Однако для всех методов адаптивного кодирования, которые приводятся в этой главе, справедлива следующая теорема:

Теорема. Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству

,

где Н – энтропия источника информации, C – константа, зависящая от размера алфавита источника и длины окна.

• 1. Адаптивный код Хаффмана

В 1978 году Р. Галлагер предложил метод кодирования источников с неизвестной или меняющейся статистикой, основанный на коде Хаффмана, и поэтому названный адаптивным кодом Хаффмана.

Адаптивный код Хаффмана используется как составная часть во многих методах сжатия данных. В нем кодирование осуществляется на основе информации, содержащейся в окне длины W. Алгоритм такого кодирования заключается в выполнении следующих действий:

1. Перед кодированием очередной буквы подсчитываются частоты появления в окне всех символов исходного алфавита А={a₁, a₂, ..., a_n}. Обозначим эти частоты как q(a₁), q(a₂), ..., q(a_n). Вероятности символов исходного алфавита оцениваются на основе значений частот символов в окне

P(a₁)= q(a₁)/W, P(a₂) =q(a₂)/W, ..., P(a_n)= q(a_n)/W.

1. По полученному распределению вероятностей строится код Хаффмана для алфавита А.
2. Очередная буква кодируется при помощи построенного кода.
3. Окно передвигается на один символ вправо, вновь подсчитываются частоты встреч в окне букв алфавита, строится новый код для очередного символа, и так далее, пока не будет получен код всего сообщения.

Пример. Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита А={a₁, a₂, a₃, a₄} и длины окна W=6 (см. рис. 9).

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

Рисунок 9 Кодирование адаптивным кодом Хаффмана

Рассмотрим подробно этапы кодирования сообщения.

При кодировании буквы a₃ получаем следующие частоты встреч символов в окне: q(a₁)=3, q(a₂)=1, q(a₃)=1, q(a₄)=1. Тогда вероятности символов алфавита A оцениваются так

Строим код Хаффмана для полученного распределения вероятностей (см. рис. 10 (а)) и кодируем символ а₃ кодовым символом 001.

a)

Символы	Вероятности	Построение кода	Кодовые cлова
а1	1/2	1	1
а2	1/6	1/2 0	01
а3	1/6	1/3	001
а4	1/6		000

б)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1	1
а2	1/6	1/3 2/3 0	011
а3	1/3		00
а4	1/6		010

в)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1/2 1	11
а2	0	1/6 0	101
а3	1/2		0
а4	1/6		100

Рисунок 10 Построение адаптивного кода Хаффмана

Далее передвигаем окно на один символ вправо и снова подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=1, q(a₃)=2, q(a₄)=1 и оцениваем вероятности:

Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (б)) и кодируем очередной символ а₃ другим кодовым словом  00. В этом случае частота встречи в окне символа а₃ увеличилась, соответственно уменьшилась длина его кодового слова.

Снова передвигаем окно на один символ вправо, подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=0, q(a₃)=3, q(a₄)=1 и оцениваем вероятности:

Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (в)) и кодируем очередной символ а₂ кодовым словом  101. Таким образом, после кодирования символов a₃a₃a₂ получаем кодовую последовательность 00100101.

Алгоритм на псевдокоде

Адаптивный код Хаффмана

Обозначим

w – окно

mas – массив вероятностей символов и кодовых слов

DO (i=1,…n) w[i]:=a[i] OD (заполняем окно символами алфавита)

DO (not EOF) (пока не конец входного файла)

DO (i=1,…,n) mas[i].p:=0 OD

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p +1 OD (частоты встречи

символов в окне)

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p/n OD (вероятности символов

в окне)

Сортировка(mas)

DO (i=1,…,n) (определяем количество

IF (mas[i].p=0) OD ненулевых вероятностей)

OD

Huffman(i,P) (строим код Хаффмана)

C:=Read( ) (читаем следующий символ из файла)

Write(mas[C].code) (код символа – в выходной файл)

DO (i=1,…,n-1) w[i]:= w[i+1] OD

w[n]:=C (включаем в окно текущий символ)

OD

• 1. Код «Стопка книг»

Этот метод был предложен Б. Я. Рябко в 1980 году. Название метод получил по аналогии со стопкой книг, лежащей на столе. Обычно сверху стопки находятся книги, которые недавно использовались, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.

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

Пример. Приведем описание кода на примере алфавита A={a₁,a₂,a₃,a₄}. Пусть кодируется сообщение а₃а₃а₄а₄а₃…

• Символ а₃ находится в третьей позиции стопки, кодируется кодовым словом 110 и перемещается на первую позицию в стопке, при этом символы а₁ и а₂ смещаются на одну позицию вниз.
• Следующий символ а₃ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
• Символ а₄ находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на первую позицию в стопке, при этом символы а₁, а₂, а₃ смещаются на одну позицию вниз.
• Следующий символ а₄ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
• Символ а₃ находится во второй позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в стопке, при этом символ а₄ смещается на одну позицию вниз.

№	Кодовое слово	Начальная «стопка»	Преобразования «стопки»
1	0	а1	а3	а3	а4	А4	а3
2	10	а2	а1	а1	а3	А3	а4
3	110	а3	а2	а2	а1	А1	а1
4	111	а4	а4	а4	а2	А2	а2

Рисунок 11 Кодирование методом «стопка книг»

Таким образом, закодированное сообщение имеет следующий вид:

110 0   111 0 10 …

а₃ а₃ а₄ а₄ a₃

Рассмотренный метод сжимает сообщение за счет того, что часто встречающиеся символы будут находиться в верхних позициях «стопки книг» и кодироваться более короткими кодовыми словами. Эффективность метода особенно заметна при кодировании серий одинаковых символов. В этом случае все символы серии, начиная со второго, будут кодироваться самым коротким кодовым словом, соответствующим первой позиции «стопки книг».

При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.

Приведение описание данного алгоритма на псевдокоде.

Алгоритм на псевдокоде

Кодирование кодом «Стопка книг»

Обозначим

code – массив кодовых слов для позиции «стопки»

s_in – строка для кодирования

s_out – результат кодирования

S – строка, содержащая исходный алфавит

l:=<длина s_in>

DO (i=1,…l)

T:=<номер символа s_in[i] в строке S>

s_out:=s_out+code[t]

stmp:=S[t]

delete(S,t,1) (преобразование

insert(stmp,S,1) строки S)

OD

• 1. Интервальный код

Интервальный код был предложен П. Элиасом в 1987 году. В нем используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

При кодировании символа x_i определяется расстояние (интервал) до его предыдущей встречи в окне длины W. Обозначим это расстояние (x_i). Если символ есть x_i в окне, то значение (x_i) равно номеру позиции символа в окне. Позиции в окне нумеруются справа налево. Если символа x_i нет в окне, то (x_i) присваивается значение W+1, а x_i кодируется словом, состоящим из (x_i) и самого символа x_i. После кодирования очередного символа окно сдвигается вправо на один символ.

Пример. Рассмотрим описание кода для исходного алфавита A={a₁,a₂,a₃,a₄}, пусть длина окна W=3. Возьмем некоторый префиксный код для записи числа (X_i):

 (хi)	1	2	3	4
σi	0	10	110	111

Пусть кодируется последовательность а₁а₁а₂а₃а₂а₂… (см. рис. 12)

1. Сначала символа а₁ нет в окне, поэтому на выход кодера передается 111 и восьмибитовый ASCII-код символа а₁ Затем окно сдвигается на одну позицию вправо.
2. При кодировании следующего символа а₁ на выход кодера передается 0, так как теперь символ а₁ находится в первой позиции окна. Далее окно снова сдвигается на одну позицию вправо.
3. Следующий символ а₂ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₂, так как символа а₂ нет в окне. Окно снова сдвигается на одну позицию вправо.
4. Следующий символ а₃ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₃ , так как символа а₃ нет в окне. Окно снова сдвигается на одну позицию вправо.
5. Следующий кодируемый символ а₂ находим во второй позиции окна и поэтому кодируем комбинацией 10. Окно снова сдвигается на одну позицию вправо.
6. И последний символ а₂ находим во первой позиции окна и поэтому кодируем комбинацией 0. Таким образом, закодированное сообщение имеет следующий вид:

111 а₁ 0 111 а₂ 111 а₃ 10 0

а₁ а₁ а₂ а₃ а₂ а_{2 …}

1

111 а₁

а₁ а₁ а₂ а₃ а₂ а_{2 …}

2

0

а₁ а₁ а₂ а₃ а₂ а_{2 …}

3

111 а₂

а₁ а₁ а₂ а₃ а₂ а_{2 …}

41

111 а₃

а₁ а₁ а₂ а₃ а₂ а_{2 …}

5

10

а₁ а₁ а₂ а₃ а₂ а_{2 …}

6

0

Рисунок 12 Кодирование интервальным кодом

При декодировании используется такое же окно, как и при кодировании. По принятому кодовому слову можно определить, в какой позиции окна находится данный символ. Если поступает код 111, то декодер считывает следующий за ним символ. Каждая декодированная буква полностью включается в окно.

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

Алгоритм на псевдокоде

Кодирование интервальным кодом

Обозначим

code – массив кодовых слов для записи числа (X_i)

s_in – строка для кодирования

s_out – результат кодирования

l:=<длина s_in>

DO (i=1,…l)

t:=0

found:=нет

DO (j=i-1,…,i-W)

t:=t+1

IF (j>0) и (s_in[i]=s_in[j])

s_out:=s_out+code[t]

found:=да

OD

FI

OD

IF (not found) s_out:=s_out+code[n]+s_in[i] FI

OD

• 1. Частотный код

В 1990 году Б. Я. Рябко предложил алгоритм кодирования, использующий алфавитный код Гилберта-Мура, и названный частотным. Частотный код относится к адаптивным методам сжатия с постоянной избыточностью. Средняя длина кодового слова для этого метода определяется только длиной окна, по которому оценивается статистика кодируемых данных, к тому же частотный код имеет достаточно высокую скорость кодирования и декодирования.

Рассмотрим алгоритм построения частотного кода для источника с алфавитом А={a₁, a₂, ..., a_n}. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

Возьмем размер окна такой, что W=(2^r  1)·n, где n=2^k  размер исходного алфавита, r, k  целые числа.

Порядок построения кодовой последовательности следующий:

1. Сначала оценивается число встреч в окне x_i-W...x_i-1 всех букв исходного алфавита. Обозначим эти величины через P(a_j), j=1,…,n
2. P(a_j) увеличивается на единицу и обозначается как
3. Вычисляются суммы Q_i , i=1,…,n

…

1. Для кодового слова символа а_j берется k знаков от двоичного разложения Q_j, где .
2. Далее окно сдвигается на один символ вправо и для кодирования следующего символа алгоритм вновь повторяется.

Пример. Пусть А={a₁, a₂, a₃, a₄}, длина окна W=4. Необходимо закодировать последовательность символов

Построим кодовое слово для символа а₃ .

1. Оценим частоты встреч в текущем "окне" всех символов алфавита:

2. Вычислим суммы Q_j :

Q₁ = 1

Q₂ = 1 + 0.5 = 1.5

Q₃ = 1 + 1 + 2 = 4

Q₄ = 1 + 1 + 4 + 1 = 7

3. Определим длину кодового слова для а₃ :

k = 1 + log (4+4)  log 4 = 1 + 3  2 = 2

4. Двоичное разложение Q₃ =100₂ , берем первые 2 знака. Таким образом, для текущего символа а₃ кодовое слово 10.

Алгоритм на псевдокоде

Частотный код

Обозначим

w – окно

W – размер окна

P – массив частот символов

Q – массив для величин Q_i.

DO (i=1,…n) w[i]:=a[i] OD (заполняем окно символами алфавита)

DO (not EOF) (пока не конец входного файла)

DO (i=1,…,n) P [i]:=1 OD

DO (i=1,…,n) P [w[i]]:= P [w[i]] +1 OD (частоты встречи

символов в окне)

pr:=0

DO (i=1,…,n)

Q [i] := pr+ P [i] /2 (вычисляем суммы)

pr:=pr+ P [i]

OD

C:=Read( ) (читаем следующий символ из файла)

DO (j=1,…,n)

IF (C= a[i]) m:=j FI (определяем номер символа в алфавите)

OD

k = 1 + log₂ (n+W)  log₂ P[m]  (длина кодового слова)

DO (j=1,…,k) (формирование кодового слова

Q [m]:=Q [m] _*2 в двоичном виде)

code:= Q [m]

IF (Q [m] >1) Q [m]:= Q [m] - 1 FI

OD

Write(code) (код символа – в выходной файл)

DO (i=0,…,n-1) w[i]:= w[i+1] OD

w[n]:=C (включаем в окно текущий символ)

OD

1. словарные коды класса Lz

Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.

Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, LZ-методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.

Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А. Лемпелом и Я. Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.

Общая схема кодирования, используемая в LZ-методах, заключается в следующем. При кодировании сообщение разбивается на слова переменной длины. При обработке очередного слова ведется поиск ему подобного в ранее закодированной части сообщения. Если слово найдено, то передается соответствующий ему код. Если слово не найдено, то передается специальный символ, обозначающий его отсутствие, и новое обозначение этого слова. Каждое новое слово, не встречавшееся ранее, запоминается, и ему присваивается индивидуальный код.

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

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

• алгоритмы, осуществляющие поиск слов в какой-либо части ранее закодированного текста, называемой окном;
• алгоритмы, использующие адаптивный словарь, который включает ранее встретившиеся слова. Если словарь заполняется до окончания процесса кодирования, то в некоторых методах он обновляется (на место ранее встретившихся слов записываются новые), а в некоторых кодирование продолжается без обновления словаря.

Алгоритмы класса LZ отличаются размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все указанные факторы влияют и на характеристики этих методов: скорость кодирования, объем требуемой памяти и степень сжатия данных, различные для разных алгоритмов. Однако в целом методы из класса LZ представляют значительный практический интерес и позволяют достаточно эффективно сжимать данные с неизвестной статистикой.

• 1. Кодирование с использованием скользящего окна

Рассмотрим основные этапы кодирования сообщения Х=х₁х₂х₃х₄…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

Сначала осуществляется поиск в окне символа х₁. Если символ не найден, то в качестве кода передается 0 как признак того, что этого символа нет в окне и двоичное представление х₁.

Если символ х₁ найден, то осуществляется поиск в окне слова х₁х₂, начинающегося с этого символа. Если слово х₁х₂ есть в окне, то производится поиск слова х₁х₂х₃ , затем х₁х₂х₃х₄ и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина этого слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.

Для кодирования чисел (i, j) могут быть использованы рассмотренные ранее коды целых чисел.

Пример. Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. (см. рис. 13)

После кодирования первых шести букв окно будет иметь вид bababa.

• Далее проверяем наличие в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Этого слова нет в окне, тогда кодируем aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3– номер позиции в окне, с которой начинается это слово, 3– длина этого слова.
• Далее окно сдвигаем на 3 символа вправо и ищем в окне букву с. Ее нет в окне, поэтому кодируем комбинацией (0, «с»), где 0– признак того, что буквы нет в окне, «с»– двоичное представление буквы. Окно сдвигаем на 1 символ вправо.
• Ищем в окне букву а, она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Это слово есть в окне, тогда кодируем abaс кодовой комбинацией (1,4,4), где 1 – признак того, что слово есть в окне, 4 –номер позиции в окне, с которой начинается это слово, 4 – длина этого слова.

... b a b a b a a b a c a b a c ...

код (0, «с»)

... b a b a b a a b a c a b a c ...

код (1,3,3)

... b a b a b a a b a c a b a c ...

код (1,4,4)

Рисунок 13 Кодирование последовательности bababaabacabac

• 1. Кодирование с использованием адаптивного словаря

В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения Х=х₁х₂х₃х₄… сначала читаются два символа х₁х₂, поскольку это слово отсутствует в словаре, то передается код символа х₁ (обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово х₁х₂, далее читается символ х₃ и осуществляется поиск в словаре слова х₂х₃. Если это слово есть в словаре, то проверяется наличие слова х₂х₃х₄ и так далее. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки, его содержащей.

Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac.

1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log₂V = log₂8 =3.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	–
4	–
5	–
6	–
7	–

1. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	–
5	–
6	–
7	–

1. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	–
6	–
7	–

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	011
6	–
7	–

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	011
6	abaа	101
7	–

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 7-ю строку словаря, и закодируем abа кодом 101. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа	110
7	abaс	111

1. Читаем букву а, ищем в словаре слово са. Этого слова нет в словаре, поэтому запишем слово са в 7-ю строку словаря, удалив слово abас, и закодируем букву с кодом 010.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа	110
7	abaс са	111

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа abaс	110
7	са	111

1. Закодируем букву с кодом 010. Конец входной последовательности.

Таким образом, входное сообщение будет закодировано так

Вход кодера: a b ab aba aba c aba c

Выход кодера: 000 001 011 101 101 010 101 010

Алгоритм на псевдокоде

Кодирование с адаптивным словарем

Обозначим

CurCode – текущий код

PrevCode – предыдущий код

M – массив, содержащий текущую последовательность

L – длина текущей последовательности

C – словарь (массив строк)

S – текущая длина кода

DicPos – количество последовательностей в словаре

<Инициализация словаря символами исходного алфавита>

S:=9; L:=0; DicPos:=257 (256+конец сжатия)

DO (not EOF)

CurCode:=Read( ) (читаем следующий байт из файла)

M[L]:=CurCode; L:=L+1

IF (текущая последовательность найдена в словаре)

CurCode:=номер найденной последовательности

ELSE

C[DicPos]:=M; DicPos:=DicPos+1

IF (log(DicPos)+1)>S S:=S+1 FI (использовать соотношение п.6.1)

Write(PrevCode,S) (пишем в выходной файл S бит PrevCode)

M[0]:=CurCode; L:=1

FI

PrevCode:=CurCode

OD

Write(PrevCode,S) (сохраняем оставшийся код)

Write(256,S) (конец сжатия)

Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид

000001011101101010101010

1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log₂V = log₂8 = 3. (Процесс заполнения словаря будет таким же, как и при кодировании.)
2. Читаем первые три бита кодовой последовательности (код 000), по коду найдем в словаре букву а.
3. Читаем следующий код 001, по коду найдем в словаре букву b. Получим новое слово ab, которого нет в словаре, поместим слово ab в свободную 3-ю строку словаря. На выход декодера передаем букву а, букву b запоминаем.
4. Читаем код 011, по коду находим в словаре слово ab. Добавляем первую букву а к предыдущему декодированному слову b, получим слово ba, его нет в словаре. Поместим слово ba в свободную 4-ю строку словаря. На выход декодера передаем букву b, слово ab запоминаем.
5. Читаем код 101, такого кода нет в словаре. Тогда добавляем к слову ab

первую букву этой же последовательности – а, получим слово aba, его нет в словаре. Поместим слово aba в свободную 5-ю строку словаря. На выход декодера передаем слово ab, слово aba запоминаем.

1. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву a к предыдущему декодированному слову aba, получим abaa. Добавим слово abaa в словарь в свободную 6-ю строку. На выход декодера передаем слово aba , и слово aba запоминаем.
2. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abaс в словарь в свободную 7-ю строку. На выход декодера передаем слово aba , букву с запоминаем.
3. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву а к предыдущей декодированной букве с, получим слово са.

Так как словарь заполнился до окончания декодирования, то будем записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. Добавим слово са в 7-ю строку словаря вместо слова abac. На выход декодера передаем букву с, слово aba запоминаем.

1. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abac в 6-ю строку словаря вместо слова abaа. На выход декодера передаем слово aba, букву с запоминаем.
2. На выход декодера передаем букву с.

В результате декодирования получим исходное сообщение

Вход декодера: 000 001 011 101 101 010 101 010

Выход декодера: a b ab aba aba c aba c

Алгоритм на псевдокоде

Декодирование с адаптивным словарем

Обозначим

CurCode – текущий код

PrevCode – предыдущий код

M – массив, содержащий текущую последовательность

L – длина текущей последовательности

C – словарь (массив строк)

S – текущая длина кода

DicPos – количество последовательностей в словаре

<Инициализация словаря символами исходного алфавита>

S:=9; L:=0; DicPos:=257

DO

CurCode:=Read(S) (читаем из файла S бит)

IF (CurCode=256) break FI

IF (C[CurCode]<>0) (в словаре найдена послед-ть с номером CurCode)

M[L]:=C[CurCode][0] (в конец текущей последовательности

приписываем первый символ найденной последовательности)

L:=L+1

ELSE M[L]:=M[0]; L:=L+1

FI

IF (текущая последовательность М не найдена в словаре С)

Write(C[PrevCode])

C[DicPos]:=M (добавляем текущую послед-ть в словарь)

DicPos:=DicPos+1

IF (log DicPos+1)>S S:=S+1 FI (использовать соотношение п.6.1)

M:=C[CurCode] (в текущую послед-ть заносим слово

L=длина слова с номером CurCode)

FI

PrevCode:=CurCode

OD

Write(C[PrevCode])

СПИСОК ЛИТЕРАТУРЫ

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом "Вильямс", 2000. - 384 с.
2. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. – М.: «Диалог-МИФИ», 2002.
3. Кричевский Р.Е. Сжатие и поиск информации. - М.: Радио и связь, 1989. - 168 с.
4. Марченко А.И., Марченко Л.А. Программирование в среде Turbo PASCAL 7.0. Базовый курс. Киев: «ВЕК+», 2003.
5. Панин В.В., Основы теории информации. Учебное пособие для ВУЗов. Бином, 2009.
6. Босова Л.Л Информатика и ИКТ: Изд-во "БИНОМ. Лаборатория знаний", 2012. - 208 с.;
7. Босова Л.Л Информатика и ИКТ: Изд-во "БИНОМ. Лаборатория знаний", 2010. - 229 с.; .
8. Семакин И.Г. Информатика и ИКТ: Изд-во "БИНОМ. Лаборатория знаний", 2009. - 320 с.; .
9. Угринович Н.Д «Информатика и ИКТ» Базовый курс.: Изд-во "БИНОМ. Лаборатория знаний", 2011. 295 с.;
10. Могилев А.В. Информатика: Академия, 2004. - 848 с.
11. Подласый И. П. Педагогика. Новый курс: изд. центр ВЛАДОС, 1999.
12. Бочкин, А.И. Методика преподавания информатики : Высшая школа, 1998. - 431