Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Практикум предназначен для студентов технических специальностей, изучающих дисциплину «Структуры и алгоритмы обработки данных». Пособие содержит необходимые теоретические сведения об основных методах кодирования информации и варианты заданий для самостоятельного выполнения.
Рисунков 13, таблиц 8. Список лит. –6 назв.
Кафедра прикладной математики и кибернетики.
Рецензент: доцент Мамойленко С.Н.
Утверждено редакционно-издательским советом СибГУТИ в качестве практикума.
Сибирский государственный университет
телекоммуникаций и информатики, 2010 г.
ОГЛАВЛЕНИЕ
Изучение дисциплины «Структуры и алгоритмы обработки данных» является одним из основных моментов в процессе подготовки специалистов по разработке программного обеспечения для компьютерных систем. Это связано с тем, что первичная задача программиста заключается в применении решения о форме представления данных и выборе алгоритмов для обработки этих данных. И лишь затем выбранные структуры программы и данных реализуется на конкретном языке программирования. В связи с этим знание классических методов и приемов обработки данных позволяет избежать ошибок, которые могут возникать при чисто интуитивной разработке программ.
Данные методические указания содержат необходимый теоретический материал по разделу курса «Структуры и алгоритмы обработки данных», посвященного различным методам кодирования информации. Все рассмотренные методы проиллюстрированы наглядными примерами. Для каждого метода приведен конкретный алгоритм, позволяющий легко его программировать. Также методические указания содержат задания для лабораторных работ по каждой теме, выполнив которые можно окончательно уяснить все особенности изучаемых методов.
Теория кодирования и теория информации возникли в начале XX века. Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. статей К. Шеннона, которые заложили фундамент для дальнейших исследований в этой области.
Кодирование – способ представления информации в удобном для хранения и передачи виде. В связи с развитием информационных технологий кодирование является центральным вопросом при решении самых разных задач программирования, таких как:
Основной моделью, которую изучает теория информации, является модель системы передачи сигналов:
Рисунок Модель системы передачи сигналов
Начальным звеном в приведенной выше модели является источник информации. Здесь рассматриваются дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита. Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, а количество символов в этом множестве – размером алфавита источника. Например, можно считать, что текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.
Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. Причем обычно символу исходного алфавита А ставится в соответствие не один, а группа символов алфавита В, которая называется кодовым словом. Кодовый алфавит – множество различных символов, используемых для записи кодовых слов. Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов.
Пример. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».
Далее будем рассматривать двоичное кодирование, т.е. размер кодового алфавита равен 2. Конечную последовательность битов (0 или 1) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.
Пример. Код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.
Дадим строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех возможных сообщений в алфавите А обозначим S. Тогда отображение , которое преобразует множество сообщений в кодовые слова в алфавите В, называется кодированием. Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.
Задача кодирования сообщения ставится следующим образом. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными. Приведем некоторые из них:
Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше символов, где m – размер исходного алфавита, n – размер кодового алфавита.
Пример. Для кодирования источника, порождающего 26 букв латинского алфавита, равномерным двоичным кодом требуется построить кодовые слова длиной не меньше =5 бит.
При неравномерном кодировании источника используются кодовые слова разной длины. Причем кодовые слова обычно строятся так, что часто встречающиеся символы кодируются более короткими кодовыми словами, а редкие символы – более длинными (за счет этого и достигается «сжатие» данных).
Под сжатием данных понимается компактное представление данных, достигаемое за счет избыточности информации, содержащейся в сообщениях. Большое значение для практического использования имеет неискажающее сжатие, позволяющее полностью восстановить исходное сообщение. При неискажающем сжатии происходит кодирование сообщения перед началом передачи или хранения, а после окончания процесса сообщение однозначно декодируется (это соответствует модели канала без шума (помех)).
Методы сжатия данных можно разделить на две группы: статические методы и адаптивные методы. Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Эти методы базируются на знании статистической структуры исходных данных. К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известные сведения о вероятностях порождения источником различных символов или их сочетаний.
Если статистика источника информации неизвестна или изменяется с течением времени, то для кодирования сообщений такого источника применяются адаптивные методы сжатия. В адаптивных методах при кодировании очередного символа текста используются сведения о ранее закодированной части сообщения для оценки вероятности появления очередного символа. В процессе кодирования адаптивные методы «настраиваются» на статистическую структуру кодируемых сообщений, т.е. коды символов меняются в зависимости от накопленной статистики данных. Это позволяет адаптивным методам эффективно и быстро кодировать сообщение за один просмотр.
Существует множество различных адаптивных методов сжатия данных. Наиболее известные из них – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды, а также методы из класса Лемпела-Зива.
Рассмотрим семейство методов кодирования, не учитывающих вероятности появления символов источника. Поскольку все символы алфавита источника можно пронумеровать, то в будем считать, что алфавит источника состоит из целых чисел. Каждому целому числу из определенного диапазона ставится в соответствие свое кодовое слово, поэтому эту группу методов также называют представлением целых чисел (representation of integers).
Основная идея кодирования состоит в том, чтобы отдельно кодировать порядок значения числа («экспоненту» ) и отдельно – значащие цифры числа («мантиссу» ). Значащие цифры мантиссы начинаются со старшей ненулевой цифры, а порядок числа определяется позицией старшей ненулевой цифры в двоичной записи числа. Как и при десятичной записи, порядок равен числу цифр в записи числа без предшествующих незначащих нулей.
Пример. Порядок двоичного числа 000001101 равен 4, а мантисса – 1101.
В этой главе будут рассмотрены две группы методов кодирования целых чисел. Условно их можно обозначить так:
Коды класса Fixed + Variable
В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.
Пример. Пусть R = 15 – количество бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤24. При записи мантиссы можно сэкономить 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 .. |
Коды класса 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.
Рассмотренные типы кодов могут быть эффективны в следующих случаях
Кодирование длин серий
Метод кодирования информации, известный как метод кодирования длин серий и предложенный П. Элиасом, при построении использует коды целых чисел. Входной поток для кодирования рассматривается как последовательность из нулей и единиц. Идея кодирования заключается в том, чтобы кодировать последовательности одинаковых элементов (например, нулей) как целые числа, указывающие количество элементов в этой последовательности. Последовательность одинаковых элементов называется серией, количество элементов в ней – длиной серии.
Пример. Входную последовательность (общая длина 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 бит.
Метод длин серий актуален для кодирования данных, в которых есть длинные последовательности одинаковых бит. В нашем примере, если .
В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования.
Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех сообщений в алфавите А обозначим S. Кодирование может сопоставлять код всему сообщению из множества S как единому целому или строить код сообщения из кодов его частей (побуквенное кодирование).
Пример 1 А={a1,a2,a3}, B={0,1} Побуквенное кодирование символов источника a1 1001 a2 0 a3010
позволяет следующим образом закодировать сообщение
a2a1a2a3 010010010
Пример 2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:
А 01, В 1000, С 1010, D 100, E 0, …
Побуквенное кодирование задается таблицей кодовых слов: , , . Множество кодовых слов V={βi} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом , т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.
Количество букв в слове α=α1…αk называется длиной слова. (Обозначение |α|=k) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается Λ. Если α=α1α2, то α1 – начало (префикс) слова α, α2 – окончание (постфикс) слова α.
Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если βi1 …βik=βj1…βjt , то k=t и при любых s=1,…,k is=js . При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.
Пример. 3 Код из примера 1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами: a3a3 или a2a1a2.
Побуквенный код называется префиксным, если в его множестве кодовых слов ни одно слово не является началом другого, т.е. элементарный код одной буквы не является префиксом элементарного кода другой буквы.
Пример 4. Код из примера 1 не является префиксным, поскольку элементарный код буквы a2 является префиксом элементарного кода буквы a3.
Утверждение. Префиксный код является разделимым.
Доказательство (от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность β, что она представлена различными способами из элементарных кодов: (побитовое представление одинаковое) и существует L такое, что при любом следует (βis=βjs) и (βit≠βjt), т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда , т.е. последовательности элементарных кодов разные и существует β/, что βiL=βjLβ/ или βjL=βiLβ/ , т.е. βiL – начало βjL, или наоборот. Получили противоречие с префиксностью кода.
Заметим, что разделимый код может быть не префиксным.
Пример 5. Разделимый, но не префиксный код: A={a,b}, B={0,1},
Приведем основные теоремы побуквенного кодирования.
Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов L1,…,Ln необходимо и достаточно, чтобы
.
Доказательство. Докажем необходимость. Пусть существует префиксный код с длинами L1,…,Ln. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).
Рисунок Полное двоичное дерево с помеченными вершинами
В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – 2r-Li вершин. Всего вершин в поддереве 2r. Тогда, , .
Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию L1≤ L2≤ … ≤ Ln. Выберем в двоичном дереве вершину V1 на уровне L1. Уберем поддерево с корнем в вершине V1. В оставшемся дереве возьмем вершину V2 на уровне L2 и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам V1, V2,…, Vn образуют префиксный код. Теорема доказана.
Пример 6. Построить префиксный код с длинами L1=1, L2=2, L3=2 для алфавита A={a1,a2,a3}. Проверим неравенство Крафта для набора длин
.
Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с 23 помеченными вершинами и выберем вершины дерева, как описано выше. Тогда элементарные коды могут быть такими: a1 0, a210, a3 11.
Рисунок Построение префиксного кода с заданными длинами
Процесс декодирования выглядит следующим образом. Просматриваем полученное сообщение, двигаясь по дереву. Если попадем в кодовую вершину, то выдаем соответствующую букву и возвращаемся в корень дерева и т.д.
Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов L1,…,Ln , необходимо и достаточно, чтобы .
Доказательство. Покажем достаточность. По теореме Крафта существует префиксный код с длинами L1,…,Ln, и он является разделимым.
Докажем необходимость утверждения. Рассмотрим тождество
Положим . Тогда тождество можно переписать следующим образом
,
где , – число всевозможных представлений числа j в виде суммы . Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу
,
где bs – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом, и . Используя предельный переход получим при . Теорема доказана.
Пример 7. Азбука Морзе – это схема алфавитного кодирования
A01, B1000, C1010, D100, E0, F0010, G110, H0000, I00, J0111, K101, L0100, M11, N10, O111, P0110, Q1101, R010, S000, T1, U001, V0001, W011, X1001, Y1011, Z1100.
Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку
Следовательно, этот код не является разделимым. На самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщение. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений (особенно с высокой скоростью) является некоторым искусством, а не простой технической процедурой.
Основные понятия
При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов Р(x1x2x3...xL), L≥1. Такой источник называется дискретным вероятностным источником.
Если вероятностный источник с алфавитом А={a1, a2, ..., an} порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любой последовательности x1x2...xL, L≥1, порождаемой источником, выполняется равенство:
P(x1x2...xL ) = P(x1)·P(x2)·...·P(xL),
где P(x) – вероятность появления символа х, Р(x1x2x3...xL) – вероятность появления последовательности x1x2x3...xL.
Для другого класса источников (марковских) существует статистическая взаимосвязь между порождаемыми символами. В дальнейшем мы будем рассматривать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти.
Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита А={a1,…,an} с вероятностями , . Основной характеристикой источника является энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)
.
Энтропия характеризует меру неопределенности выбора для данного источника.
Пример. Если А={a1,a2}, p1=0, p2 =1, т.е. источник может породить только символ a2, то неопределенности нет, энтропия H(p1,p2)=0.
Источник с равновероятными символами А={a1,a2}, p1 =1/2, p2 =1/2, будет иметь максимальную энтропию H(p1,p2)=1.
Величина называется энтропией на символ последовательности длины L, где AL множество всех последовательностей длины L в алфавите A, x=(x1,x2,...,xL) последовательность L букв дискретного cтационарного источника. Обозначим через предел энтропии HL при L . Эту величину называют предельной энтропией источника. Показано, что для стационарного бернуллиевского источника
.
Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения. Пусть имеется разделимый побуквенный код для источника, порождающего символы алфавита А={a1,…,an} с вероятностями pi =P(ai), состоящий из n кодовых слов с длинами L1,…,Ln в алфавите {0,1}. Средней длиной кодового слова называется величина , которая показывает среднее число кодовых букв на одну букву источника.
Пример. Пусть имеются два источника с одним и тем же алфавитом А={a1,a2,a3} и разными вероятностными распределениями P1={1/3, 1/3, 1/3}, P2={1/4, 1/4, 1/2}, которые кодируются одним и тем же кодом
.
Средняя длина кодового слова для разных источников будет различной
Lср(P1)=1/3.2 + 1/3.3 + 1/3.2= 7/3 ≈2.33
Lср(P2)=1/4.2 + 1/4.3 + 1/2.2= 9/4 =2.25
Побуквенный разделимый код называется оптимальным, если средняя длина кодового слова минимальна среди всех побуквенных разделимых кодов для данного распределения вероятностей символов.
Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений
.
Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.
Взаимосвязь между средней длиной кодового слова и энтропией дискретного вероятностного источника при побуквенном кодировании выражает следующая теорема.
Теорема 1 (Шеннон). Для источника с алфавитом А={a1,…,an} и вероятностями pi =P(ai), и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии
Lcp ≥ H(p1,…,pn)
и можно построить разделимый побуквенный код, у которого средняя длина кодового слова превосходит энтропию не больше, чем на единицу:
Lcp < H(p1,…,pn)+1
Можно получить более сильные результаты, если кодовые слова приписывать не отдельными буквами, а блоками из L букв источника. Так, для неравномерных блоковых кодов справедлива следующая теорема.
Теорема 2. Пусть HL энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова Lcp будет удовлетворять неравенствам:
.
Кроме того, в случае бернуллиевского стационарного источника для любого >0 можно выбрать достаточно большое L, чтобы величина Lcp удовлетворяла неравенствам:
,
и левое неравенство для Lcp никогда не нарушается для разделимого кода.
Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.
Лемма 1. Для оптимального кода с длинами кодовых слов L1,…,Ln: верно соотношение L1≤L2≤…≤Ln , если p1≥p2≥…≥pn.
Доказательство (от противного): Пусть есть i и j, что Li>Lj при pi>pj. Тогда
Lipi+Ljpj=
=Lipi+Ljpj+Lipj+Ljpi-Lipj-Ljpi=
=pi(Li-Lj)-pj(Li-Lj)+Ljpi+Lipj=
=(pi-pj)(Li-Lj) +Lipj+Ljpi>Lipj+Ljpi,
т.е. если поменяем местами Li и Lj, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.
Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей Р, . Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.
Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид , . Тогда длина любого элементарного кода не больше длины b, т.е. , . Поскольку схема кодирования префиксная, то кодовые слова не являются префиксом b. С другой стороны, b не является префиксом кодовых слов . Таким образом, новая схема кодирования также является префиксной, причем с меньшей средней длиной кодового слова , что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова и максимальной длины отличаются не в последнем разряде, т.е. , , , . Причем , не являются префиксами для других кодовых слов и наоборот. Тогда новая схема также является префиксной, причем , что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.
Оптимальный код Хаффмана
Метод оптимального побуквенного кодирования был разработан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом А={a1,…,an} и вероятностями pi =P(ai).
Рассмотрим алгоритм построения оптимального кода Хаффмана, который основывается на утверждениях лемм предыдущего параграфа.
Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями
p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=0.07.
Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.
a1 0.36 0.36 0.36 0.36 0.64 0
a2 0.18 0.18 0.28 0.36 0.36 1
a3 0.18 0.18 0.18 0.28 00
a4 0.12 0.16 0.18 000 01
a5 0.09 0.12 010 001
a6 0.07 0100 011
0101
Рисунок Процесс построения кода Хаффмана
Таблица 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(p1,…,p6) = − 0.36.log0.36 − 2.0.18.log0.18 −
− 0.12.log0.12 − 0.09.log0.09 − 0.07log0.07=2.37
Рисунок Кодовое дерево для кода Хаффмана
Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 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
Рассмотрим несколько классических побуквенных кодов, у которых средняя длина кодового слова близка к оптимальной. Пусть имеется дискретный вероятностный источник, порождающий символы алфавита А={a1,…,an} с вероятностями pi = P(ai).
Код Шеннона
Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона из п. 5.1
.
Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:
Q0=0, Q1=p1, Q2=p1+p2, Q3=p1+p2+p3, … , Qn=1.
Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова Li из соотношения
, .
Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=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– массив для величин Qi
L – массив длин кодовых слов
C – матрица элементарных кодов
P [0]:=0, Q [0]:=0
DO (i=1,…,n)
Q [i] := Q [i-1]+P [i]
L [i]:= - log2P[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
Код Фано
Метод Фано построения префиксного почти оптимального кода, для которого , заключается в следующем. Упорядоченный по убыванию вероятностей список букв алфавита источника делится на две части так, чтобы суммы вероятностей букв, входящих в эти части, как можно меньше отличались друг от друга. Буквам первой части приписывается 0, а буквам из второй части – 1. Далее также поступают с каждой из полученных частей. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве.
Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=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 |
Рисунок Кодовое дерево для кода Фано
Полученный код является префиксным и почти оптимальным со средней длиной кодового слова
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 – массив длин элементарных кодов
SL – сумма элементов первой части массива
SR – сумма элементов второй части массива.
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)
SL:= 0
DO (i=L,…,R-1)
SL:=SL+ P [i]
OD
SR:=P [R]
m:= R
DO (SL ≥ SR)
m:=m-1
SL:=SL - P [m]
SR:=SR+ P [m]
OD
Med:= m
Алфавитный код Гилберта – Мура
Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого .
Пусть символы алфавита некоторым образом упорядочены, например, a1≤a2≤…≤an. Код называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. .
Процесс построения кода происходит следующим образом.
Q1=p1/2,
Q2=p1+p2/2,
Q3=p1+p2+p3/2,
…
Qn=p1+p2+…+pn-1+pn/2.
Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=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 – массив для величин Qi
L – массив длин кодовых слов
C – матрица элементарных кодов
pr:=0
DO (i=1,…,n)
Q [i]:= pr+ P[i] /2
pr:=pr+ P[i]
L [i]:= - log2P[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
Идея арифметического кодирования была впервые предложена П. Элиасом. В арифметическом коде кодируемое сообщение разбивается на блоки постоянной длины, которые затем кодируются отдельно. При этом при увеличении длины блока средняя длина кодового слова стремится к энтропии, однако возрастает сложность реализации алгоритма и уменьшается скорость кодирования и декодирования. Таким образом, арифметическое кодирование позволяет получить произвольно малую избыточность при кодировании достаточно больших блоков входного сообщения.
Рассмотрим общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита А={a1,a2,…,an} с вероятностями pi=P(ai), . Необходимо закодировать последовательность символов данного источника Х=х1х2х3х4.
Q0=0
Q1=p1
Q2=p1+p2
Q3=p1+p2+p3
...
Qn=p1+p2+…+pn=1
a1 [Q0,Q1)
a2 [Q1,Q2)
a3 [Q2,Q3)
a4 [Q3,Q4)
...
an [Qn-1,Qn)
На рисунке 7 показан этот процесс для кодирования последовательности а3а2а3…
Рисунок 7 Схема арифметического кодирования
Для удобства вычислений введем следующие обозначения:
li нижняя граница отрезка, соответствующего i-той букве исходного сообщения;
hi верхняя граница этого отрезка;
ri длина отрезка [li, hi), т.е. ri = hi li.
Возьмем начальные значения этих величин
l0 = Q0=0, h0 = Qk=1, r0 = h0 l0=1
и далее будем вычислять границы интервала, соответствующего кодируемой букве по формулам:
, ,
где m порядковый номер кодируемой буквы в алфавите источника, m=1,...,n.
Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а начало интервала зависит от порядка расположения символов в кодируемой последовательности.
Для однозначного декодирования исходной последовательности достаточно взять разрядов двоичной записи любой точки из интервала [li,hi), где rk длина интервала после кодирования k символов источника.
Пример. Рассмотрим кодирование бесконечной последовательности X=a3a2a3a1a4... в алфавите A={a1, a2, a3, a4} с помощью арифметического кода. Пусть вероятности букв исходного алфавита равны соответственно
p1 = 0.1, p2 = 0.4, p3 = 0.2, p4 = 0.3.
Вычислим кумулятивные вероятности Qi :
Q0 = 0,
Q1 =p1 = 0.1,
Q2 =p1+p2 = 0.5,
Q3 =p1+p2+p3 = 0.7,
Q4 =p1 +p2 +p3 + p4 = 1.
Получим границы интервала, соответствующего первому символу кодируемого сообщения a3:
l1 = l0 + r0·Q2 = 0 + 1·0.5 = 0.5,
h1 = l0 + r0·Q3 = 0 + 1·0.7 = 0.7,
r1 = h1 l1 = 0.7 0.5 = 0.2.
Для второго символа кодируемого сообщения a2 границы интервала будут следующие:
l2 = l1 + r1·Q1 = 0.5 + 0.2·0.1 = 0.52,
h2 = l1 + r1·Q2 = 0.5 + 0.2·0.5 = 0.6,
r2 = h2 l2 = 0.6 0.52 = 0.08 и т.д.
В результате всех вычислений получаем следующую последовательность интервалов для сообщения a3a2a3a1a4
В начале [0.0, 1.0)
После пpосмотpа a3 [0.5, 0.7)
После пpосмотpа a2 [0.52, 0.6)
После пpосмотpа a3 [0.56, 0.576)
После пpосмотpа a1 [0.56, 0.5616)
После пpосмотpа a4 [0.56112, 0.5616)
Кодом последовательности a3a2a3a1a4 будет двоичная запись любой точки из интервала [0.56112, 0.5616), например, 0.56112. Для однозначного декодирования возьмем log2(r5) = log2(0.00048) = 12 разрядов, получим 100011111010.
Таким образом, при арифметическом кодировании сообщение представляется вещественными числами в интервале [0,1). По мере кодирования сообщения отображающий его интервал уменьшается, а количество битов для представления интервала возрастает. Очередные символы сообщения сокращают величину интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и следовательно, добавляют меньше битов к результату.
Алгоритм на псевдокоде
Арифметическое кодирование
Обозначим
l массив нижних границ интервалов при кодировании
h массив верхних границ интервалов при кодировании
r массив длин интервалов
m порядковый номер кодируемой буквы в алфавите источника
Q – массив для величин Qi.
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= aj) 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. Сразу можно определить, что первым закодированным символом был а3, т. к. число 0.56112 лежит в интервале [0.5; 0.7), выделенном символу а3. Затем в качестве интервала берется [0.5; 0.7) и в нем определяется диапазон, соответствующий числу 0.56112. Это интервал [0.52, 0.6), выделенный символу а2 и т.д. Для декодирования необходимо знать количество закодированных символов и исходные вероятности символов.
Алгоритм на псевдокоде
Арифметическое декодирование
Обозначим
l массив нижних границ интервалов при кодировании
h массив верхних границ интервалов при кодировании
r массив длин интервалов
Q – массив для величин Qi
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, l0=0, h0=65535). При этом с потерей точности можно бороться, отслеживая сближение li и hi и умножая числитель и знаменатель представляющей их дроби на одно и то же число, например на 2. С переполнением сверху можно бороться, записывая старшие биты li и hi в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда li и hi одновременно находятся в верхней или нижней половине интервала.
При решении реальных задач истинные значения вероятностей источника, как правило, неизвестны или могут изменяться с течением времени, поэтому для кодирования сообщений применяют адаптивные модификации методов кодирования.
Большинство адаптивных методов для учета изменений статистики исходных данных используют так называемое окно. Окном называют последовательность символов, предшествующих кодируемой букве, а длиной окна количество символов в окне.
Обычно окно имеет фиксированную длину и после кодирования каждой буквы текста окно передвигается на один символ вправо. Таким образом, код для очередной буквы строится с учетом информации, хранящейся в данный момент в окне (см. рис. 8).
Рисунок 8 Схема перемещения окна при кодировании
При декодировании окно передвигается по тексту аналогичным образом. Информация, содержащаяся в окне, позволяет однозначно декодировать очередной символ.
Оценка избыточности при адаптивном кодировании является достаточно сложной математической задачей, поскольку общая избыточность складывается из двух составляющих: избыточность кодирования и избыточность, возникающая при оценке вероятностей появления символов. Поэтому эффективность методов адаптивного кодирования зачастую оценивают экспериментальным путем.
Однако для всех методов адаптивного кодирования, которые приводятся в этой главе, справедлива следующая теорема:
Теорема. Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству
,
где Н – энтропия источника информации, C – константа, зависящая от размера алфавита источника и длины окна.
Адаптивный код Хаффмана
В 1978 году Р. Галлагер предложил метод кодирования источников с неизвестной или меняющейся статистикой, основанный на коде Хаффмана, и поэтому названный адаптивным кодом Хаффмана.
Адаптивный код Хаффмана используется как составная часть во многих методах сжатия данных. В нем кодирование осуществляется на основе информации, содержащейся в окне длины W. Алгоритм такого кодирования заключается в выполнении следующих действий:
P(a1)= q(a1)/W, P(a2) =q(a2)/W, ..., P(an)= q(an)/W.
Пример. Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита А={a1, a2, a3, a4} и длины окна W=6 (см. рис. 9).
Рисунок 9 Кодирование адаптивным кодом Хаффмана
Рассмотрим подробно этапы кодирования сообщения.
При кодировании буквы a3 получаем следующие частоты встреч символов в окне: q(a1)=3, q(a2)=1, q(a3)=1, q(a4)=1. Тогда вероятности символов алфавита A оцениваются так
Строим код Хаффмана для полученного распределения вероятностей (см. рис. 10 (а)) и кодируем символ а3 кодовым символом 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(a1)=2, q(a2)=1, q(a3)=2, q(a4)=1 и оцениваем вероятности:
Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (б)) и кодируем очередной символ а3 другим кодовым словом 00. В этом случае частота встречи в окне символа а3 увеличилась, соответственно уменьшилась длина его кодового слова.
Снова передвигаем окно на один символ вправо, подсчитываем частоты встреч символов в окне q(a1)=2, q(a2)=0, q(a3)=3, q(a4)=1 и оцениваем вероятности:
Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (в)) и кодируем очередной символ а2 кодовым словом 101. Таким образом, после кодирования символов a3a3a2 получаем кодовую последовательность 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
Код «Стопка книг»
Этот метод был предложен Б. Я. Рябко в 1980 году. Название метод получил по аналогии со стопкой книг, лежащей на столе. Обычно сверху стопки находятся книги, которые недавно использовались, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.
До начала кодирования буквы исходного алфавита упорядочены произвольным образом и каждой позиции в стопке присвоено свое кодовое слово, причем первой позиции стопки соответствует самое короткое кодовое слово, а последней позиции самое длинное кодовое слово. Очередной символ кодируется кодовым словом, соответствующим номеру его позиции в стопке, и переставляется на первую позицию в стопке.
Пример. Приведем описание кода на примере алфавита A={a1,a2,a3,a4}. Пусть кодируется сообщение а3а3а4а4а3…
|
№ |
Кодовое слово |
Начальная «стопка» |
Преобразования «стопки» |
||||
|
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 Кодирование методом «стопка книг»
Таким образом, закодированное сообщение имеет следующий вид:
Рассмотренный метод сжимает сообщение за счет того, что часто встречающиеся символы будут находиться в верхних позициях «стопки книг» и кодироваться более короткими кодовыми словами. Эффективность метода особенно заметна при кодировании серий одинаковых символов. В этом случае все символы серии, начиная со второго, будут кодироваться самым коротким кодовым словом, соответствующим первой позиции «стопки книг».
При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.
Приведение описание данного алгоритма на псевдокоде.
Алгоритм на псевдокоде
Кодирование кодом «Стопка книг»
Обозначим
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
Интервальный код
Интервальный код был предложен П. Элиасом в 1987 году. В нем используется окно длины W, т.е. при кодировании символа xi исходной последовательности учитываются W предыдущих символов:
При кодировании символа xi определяется расстояние (интервал) до его предыдущей встречи в окне длины W. Обозначим это расстояние (xi). Если символ есть xi в окне, то значение (xi) равно номеру позиции символа в окне. Позиции в окне нумеруются справа налево. Если символа xi нет в окне, то (xi) присваивается значение W+1, а xi кодируется словом, состоящим из (xi) и самого символа xi. После кодирования очередного символа окно сдвигается вправо на один символ.
Пример. Рассмотрим описание кода для исходного алфавита A={a1,a2,a3,a4}, пусть длина окна W=3. Возьмем некоторый префиксный код для записи числа (Xi):
|
(хi) |
1 |
2 |
3 |
4 |
|
σi |
0 |
10 |
110 |
111 |
Пусть кодируется последовательность а1а1а2а3а2а2… (см. рис. 12)
Рисунок 12 Кодирование интервальным кодом
При декодировании используется такое же окно, как и при кодировании. По принятому кодовому слову можно определить, в какой позиции окна находится данный символ. Если поступает код 111, то декодер считывает следующий за ним символ. Каждая декодированная буква полностью включается в окно.
Сжатие данных интервальным кодом достигается за счет малых расстояний между встречами более вероятных букв, что позволяет получить более короткие кодовые слова.
Алгоритм на псевдокоде
Кодирование интервальным кодом
Обозначим
code – массив кодовых слов для записи числа (Xi)
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
Частотный код
В 1990 году Б. Я. Рябко предложил алгоритм кодирования, использующий алфавитный код Гилберта-Мура, и названный частотным. Частотный код относится к адаптивным методам сжатия с постоянной избыточностью. Средняя длина кодового слова для этого метода определяется только длиной окна, по которому оценивается статистика кодируемых данных, к тому же частотный код имеет достаточно высокую скорость кодирования и декодирования.
Рассмотрим алгоритм построения частотного кода для источника с алфавитом А={a1, a2, ..., an}. Пусть используется окно длины W, т.е. при кодировании символа xi исходной последовательности учитываются W предыдущих символов:
Возьмем размер окна такой, что W=(2r 1)·n, где n=2k размер исходного алфавита, r, k целые числа.
Порядок построения кодовой последовательности следующий:
…
Пример. Пусть А={a1, a2, a3, a4}, длина окна W=4. Необходимо закодировать последовательность символов
Построим кодовое слово для символа а3 .
1. Оценим частоты встреч в текущем "окне" всех символов алфавита:
2. Вычислим суммы Qj :
Q1 = 1
Q2 = 1 + 0.5 = 1.5
Q3 = 1 + 1 + 2 = 4
Q4 = 1 + 1 + 4 + 1 = 7
3. Определим длину кодового слова для а3 :
k = 1 + log (4+4) log 4 = 1 + 3 2 = 2
4. Двоичное разложение Q3 =1002 , берем первые 2 знака. Таким образом, для текущего символа а3 кодовое слово 10.
Алгоритм на псевдокоде
Частотный код
Обозначим
w – окно
W – размер окна
P – массив частот символов
Q – массив для величин Qi.
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 + log2 (n+W) log2 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
Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.
Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, LZ-методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.
Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А. Лемпелом и Я. Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.
Общая схема кодирования, используемая в LZ-методах, заключается в следующем. При кодировании сообщение разбивается на слова переменной длины. При обработке очередного слова ведется поиск ему подобного в ранее закодированной части сообщения. Если слово найдено, то передается соответствующий ему код. Если слово не найдено, то передается специальный символ, обозначающий его отсутствие, и новое обозначение этого слова. Каждое новое слово, не встречавшееся ранее, запоминается, и ему присваивается индивидуальный код.
При декодировании по принятому коду определяется закодированное слово. В случае получения специального символа, сигнализирующего о передаче нового слова, принятое слово запоминается, и ему присваивается такой же, как и при кодировании, код. Таким образом, декодирование является однозначным, т.к. каждому слову соответствует свой собственный код.
По способу организации хранения и поиска слов словарные методы можно разделить на две большие группы:
Алгоритмы класса LZ отличаются размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все указанные факторы влияют и на характеристики этих методов: скорость кодирования, объем требуемой памяти и степень сжатия данных, различные для разных алгоритмов. Однако в целом методы из класса LZ представляют значительный практический интерес и позволяют достаточно эффективно сжимать данные с неизвестной статистикой.
Кодирование с использованием скользящего окна
Рассмотрим основные этапы кодирования сообщения Х=х1х2х3х4…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, т.е. при кодировании символа xi исходной последовательности учитываются W предыдущих символов:
Сначала осуществляется поиск в окне символа х1. Если символ не найден, то в качестве кода передается 0 как признак того, что этого символа нет в окне и двоичное представление х1.
Если символ х1 найден, то осуществляется поиск в окне слова х1х2, начинающегося с этого символа. Если слово х1х2 есть в окне, то производится поиск слова х1х2х3 , затем х1х2х3х4 и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина этого слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.
Для кодирования чисел (i, j) могут быть использованы рассмотренные ранее коды целых чисел.
Пример. Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. (см. рис. 13)
После кодирования первых шести букв окно будет иметь вид bababa.
Рисунок 13 Кодирование последовательности bababaabacabac
Кодирование с использованием адаптивного словаря
В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения Х=х1х2х3х4… сначала читаются два символа х1х2, поскольку это слово отсутствует в словаре, то передается код символа х1 (обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово х1х2, далее читается символ х3 и осуществляется поиск в словаре слова х2х3. Если это слово есть в словаре, то проверяется наличие слова х2х3х4 и так далее. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки, его содержащей.
Пример. Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac.
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
– |
|
|
4 |
– |
|
|
5 |
– |
|
|
6 |
– |
|
|
7 |
– |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
– |
|
|
5 |
– |
|
|
6 |
– |
|
|
7 |
– |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
– |
|
|
6 |
– |
|
|
7 |
– |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
aba |
011 |
|
6 |
– |
|
|
7 |
– |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
aba |
011 |
|
6 |
abaа |
101 |
|
7 |
– |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
aba |
101 |
|
6 |
abaа |
110 |
|
7 |
abaс |
111 |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
aba |
101 |
|
6 |
abaа |
110 |
|
7 |
abaс са |
111 |
|
Номер строки |
Слово |
Код |
|
0 |
a |
000 |
|
1 |
b |
001 |
|
2 |
c |
010 |
|
3 |
ab |
011 |
|
4 |
ba |
100 |
|
5 |
aba |
101 |
|
6 |
abaа abaс |
110 |
|
7 |
са |
111 |
Таким образом, входное сообщение будет закодировано так
Алгоритм на псевдокоде
Кодирование с адаптивным словарем
Обозначим
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
первую букву этой же последовательности – а, получим слово aba, его нет в словаре. Поместим слово aba в свободную 5-ю строку словаря. На выход декодера передаем слово ab, слово aba запоминаем.
Так как словарь заполнился до окончания декодирования, то будем записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. Добавим слово са в 7-ю строку словаря вместо слова abac. На выход декодера передаем букву с, слово aba запоминаем.
В результате декодирования получим исходное сообщение
Алгоритм на псевдокоде
Декодирование с адаптивным словарем
Обозначим
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
Кодирование целых чисел
Порядок выполнения работы
|
Число |
Кодовое слово |
||
|
Fixed+Variable |
γ-код Элиаса |
ω-код Элиаса |
|
|
0 |
|||
|
1 |
|||
|
2 |
|||
|
… |
|
Размер файла |
Коэффициент сжатия файла |
||
|
Fixed+Variable |
γ-код Элиаса |
ω-код Элиаса |
|
Контрольные вопросы
Лабораторная работа №2
Оптимальный код Хаффмана
Порядок выполнения работы
|
Символ |
Вероятность |
Кодовое слово |
Длина кодового слова |
Контрольные вопросы
Лабораторная работа №3
Почти оптимальное алфавитное кодирование
Порядок выполнения работы
|
Символ |
Вероятность |
Кодовое слово |
Длина кодового слова |
|
Энтропия исходного текста |
Средняя длина кодового слова |
|||
|
Код Хаффмена |
Код Шеннона |
Код Фано |
Код Гилберта-Мура |
|
Контрольные вопросы
Лабораторная работа №4
Арифметическое кодирование
Порядок выполнения работы
Контрольные вопросы
Лабораторная работа №5
Адаптивное кодирование
Порядок выполнения работы
|
Размер исходного файла |
Коэффициент сжатия данных |
|||
|
Адаптивный код Хаффмана |
Код «Стопка книг» |
Интервальный код |
Частотный код |
|
Контрольные вопросы
Лабораторная работа №6
Словарные коды
Порядок выполнения работы
|
Размер исходного файла |
Коэффициент сжатия данных |
||
|
Текст на английском языке |
Текст на русском языке |
Текст программы на языке С |
|
Контрольные вопросы
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
Приложение А
Псевдокод для записи алгоритмов
Для записи алгоритма будем использовать специальный язык – псевдокод. Алгоритм на псевдокоде записывается на естественном языке с использованием двух конструкций: ветвления и повтора. В круглых скобках будем писать комментарии. В треугольных скобках будем описывать действия, алгоритм выполнения которых не требует детализации, например, <обнулить массив>.
: = Операция присваивания значений.
Операция обмена значениями.
Конструкции ветвления
<действие> то выполнить действие
FI FI указывает на конец этих действий.
<действия 1>
ELSE <действия 2> Действия 2 выполняются,
FI если неверно условие.
<действия1>
ELSEIF (условие2) Действия 2 выполняются,
<действия2> если неверно условие1 и верно условие 2
…FI
Конструкции повтора
DO (условие) Действия повторяются
<действия> пока условие истинно.
OD OD указывает на конец цикла.
DO <действия>
OD (условие выполнения)
DO (i=1, 2, ... n) Действия выполняются для значений
<действия> параметра из списка
OD
DO
<действия>
OD
DO
...IF (условие) OD Если условие истинно, то выйти из цикла.
OD
Елена Викторовна Курапова
Елена Павловна Мачикина
ОСНОВНЫЕ МЕТОДЫ КОДИРОВАНИЯ ДАННЫХ
Методические указания
Редактор Фионов А. Н.
Корректор:.....................
Подписано в печать..........
Формат бумаги 62 x 84/16, отпечатано на ризографе, шрифт № 10,
изд. л......,заказ №.....,тираж – экз., СибГУТИ.
630102, г. Новосибирск, ул. Кирова, 86.
PAGE 62