ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ
по дисциплине «Информационные технологии»
УНИВЕРСАЛЬНОЕ КОДИРОВАНИЕ.
СЛОВАРНОЕ МОДЕЛИРОВАНИЕ.
АНАЛИЗ ОПТИМАЛЬНОСТИ КОДОВ ХАФФМАНА
2012

Реферат

Отчет по лабораторной работе 12 с., 2 части, 4 рис., 4 таб., 4источника, 2  прил.
КОД ХАФФМАНА, ДИСКРЕТНЫЙ ИСТОЧНИК, СЛОВАРНОЕ МОДЕЛИРОВАНИЕ, КОДИРОВАНИЕ, ЭНТРОПИЯ, ДЛИНА КОДА.
Предметом исследования лабораторной работы являлся принцип универсального кодирования, методы словарного моделирования дискретных источников и кодирование методом Д.А. Хаффмана.
Цель работы – универсальное кодирование дискретного нестационарного источника на примере словарного моделирования и оценка оптимальности кодов Хаффмана.
В ходе работы был сгенерирован псевдотекст (около 150 символов) с использованием четырёх букв и знака подчёркивания в качестве разделителя слов, Был проведён анализ первой трети текста,на основании которого построен словарь подстрок, который использовался при кодировании оставшихся двух третей текста.
По итогам работы были сделаны выводы об однородности текста и эффективности применяемого метода кодирования.

Содержание

Введение    4
1 Словарное моделирование    5
1.1 Генерация псевдотекста    5
1.2 Построение словаря повторяющихся подстрок    5
1.3 Сравнительные характеристики энтропии    5
2 Кодирование на основе словарного моделирования    7
2.1 Построение двоичных кодов Хаффмана    7
Заключение    9
Список использованных источников    10
Приложение А Дерево подстрок псевдотекста    11
Приложение Б Таблицы для кодирования по методу Хаффмана    12

Введение

В 1981г. Й.Й. Риссанен и Г.Г. Лангдон предложили принцип универсального кодирования, разделяющий задачу кодирования источника на две составляющих: моделирование и кодирование. Задачей моделирования является получение распределения вероятностей текущего состояния источника. Результатом моделирования источника в момент времени k после получения сообщения sk является множество вероятностей Pk = {pk1, pk2, … pkN} того, какое значение из множества возможных сообщений X = {x1, x2, … xN} выберет ожидаемое sk+1.
После получения сообщения sk+1, которое, например, приняло значение xi, требуется построить для него как можно более короткий код из сообщений выходного алфавита Y = {y1, y2, … yM} (чаще всего двоичного), что является задачей кодирования. Оптимальной длиной кода для sk+1 будет величина
– logM p(xi),    (1)
где M – мощность выходного алфавита, p(xi) – объективная вероятность появления сообщения xi. Поскольку объективные вероятности априорно неизвестны, для построения кода используется значение pki, полученное на этапе моделирования. Таким образом, эффективность универсального кодирования зависит и от точности оценки вероятностей при моделировании, и от оптимальности построения кода при кодировании.
Суть словарного моделирования заключается в использовании расширенного алфавита источника – словаря D = {d1, d2, … dN+C}, состоящего из комбинаций элементарных сообщений алфавита X и называются подстроками. При кодировании источника элементарные сообщения принимаются до тех пор, пока не сформируют подстроку словаря D,  которая кодируется на основе распределения вероятностей подстрок P = {p1, p2, … pN+С}.
Для эффективного кодирования сообщений алфавита любой мощности может быть использован метод Д.А. Хаффмана, который позволяет построить для каждого сообщения уникальный префиксный код длины, округлённой до большего целого [2].
Целью работы являлось универсальное кодирование дискретного нестационарного источника на примере словарного моделирования и оценка оптимальности кодов Хаффмана.

1 Словарное моделирование

1.1 Генерация псевдотекста

Для генерации псевдотекста был взят алфавит, состоящий из четырех букв плюс знак подчеркивания в качестве разделителя слов: X = {“Т”, “О”, “М”, “А”, “_”}.
Из символов полученного алфавита был составлен собственный непрерывный псевдотекст (около 150 символов), интуитивно подражая фонетическим, орфографическим и грамматическим свойствам естественного человеческого языка:
АМ_ТОМ_ТОМА_АМОТАМ_МОТТАТТТАМ_ТОМА_АМОТ_ОТ_ТО_А_А_•ТО_МА_АТОМ_ТОМААМОТ_АМАМ_М_ТО_ТОАМ_АА_ТОТО_ТОМАМАТОАМА_МА_АМ_ОТАМ_ТОМА_ТОМАТОМА_ОТ_АМТО_ТОМАТО_ТОМАА
Примерно треть текста здесь отделен маркером так, чтобы разрыв находился перед началом очередного псевдослова (т.е. после знака подчёркивания). Часть текста (до маркера) решено было считать обработанной, именно она использовалась для статистического анализа и получения подстрок.

1.2 Построение словаря повторяющихся подстрок

Выписав все имеющиеся подстроки первой части и частоту их появления, мы построим словарь D. Удобно записывать подстроки иерархически: для каждой короткой подстроки выписывать все более длинные, начинающиеся с этой подстроки. Тогда можно проверить: частота появления подстроки должна быть равна сумме частот дочерних подстрок (более длинных, начинающихся с родительской). Все возможные подстроки изображены на рисунке А.1 приложения А.
Выбор подстрок, являясь в каком-то смысле произвольным процессом, имеет важное для последующего кодирование свойство: множество подстрок модели должно покрывать множество возможных подстрок сообщения, и в общем случае этого можно достичь, включив весь алфавит в множество подстрок.

1.3 Сравнительные характеристики энтропии

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

Dk    F(dk)    P(dk)     -plog(p)        Dk    F(dk)    P(dk)     -plog(p)
А    23    0,077441    0,285816        А    23    0,077441    0,285816
М    20    0,06734    0,262114        М    20    0,06734    0,262114
_    19    0,063973    0,253742        _    19    0,063973    0,253742
О    19    0,063973    0,253742        О    19    0,063973    0,253742
Т    19    0,063973    0,253742        Т    19    0,063973    0,253742
ТО    16    0,053872    0,227034                  H(X)=    1,309157
МА    12    0,040404    0,187045
_Т    9    0,030303    0,15286
_ТО    9    0,030303    0,15286
АМ    9    0,030303    0,15286
ОМ    8    0,026936    0,140453
ТОМ    8    0,026936    0,140453
ОМА    7    0,023569    0,127437
ТОМА    7    0,023569    0,127437
_ТОМ    6    0,020202    0,113724
_ТОМА    6    0,020202    0,113724
А_    6    0,020202    0,113724
М_    6    0,020202    0,113724
_А    5    0,016835    0,099199
МА_    5    0,016835    0,099199
О_    5    0,016835    0,099199
ТО_    5    0,016835    0,099199
АМ_    4    0,013468    0,083695
АТ    4    0,013468    0,083695
АТО    4    0,013468    0,083695
О_Т    4    0,013468    0,083695
О_ТО    4    0,013468    0,083695
ОТ    4    0,013468    0,083695
ТО_Т    4    0,013468    0,083695
ТО_ТО    4    0,013468    0,083695
_АМ    3    0,010101    0,066963
_М    3    0,010101    0,066963
АА    3    0,010101    0,066963
АМА    3    0,010101    0,066963
М_Т    3    0,010101    0,066963
М_ТО    3    0,010101    0,066963
МАТ    3    0,010101    0,066963
МАТО    3    0,010101    0,066963
О_ТОМ    3    0,010101    0,066963
О_ТОМА    3    0,010101    0,066963
ТО_ТОМ    3    0,010101    0,066963
ТО_ТОМА    3    0,010101    0,066963
Cумм=    297    1    5,042403
Средн=    7,071429
H(D)=    0,713067
Рисунок1 – Вычисление энтропии в Exel
Перед сравнением полученные оценки энтропии были нормализированы – поделены на среднее количество символов в подстроке ансамбля:

HD=5,042403/7,071429=0,713067 бит.    (2)

Что касается максимального значения энтропии первого символа оставшейся части текста Hmax, то очевидно из свойства энтропии о её максимуме, что значение Hmax будет высчитываться по формуле 3:

Hmax=-log2N= -log20,2=2,322 бит.    (3)

В таблице 1 приведены значения полученной энтропии в битах:
Таблица 1 – Значения полученной энтропии
HD    Hmax    HX
0,713067    2,322    1,309157

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

2 Кодирование на основе словарного моделирования

2.1 Построение двоичных кодов Хаффмана

В ходе выполнения работы было построено два набора двоичных кодов Хаффмана: Huff(X) для основного алфавита и Huff(D) для словаря подстрок (в приложении Б приведены таблица Б.1 и таблица Б.2). Для оставшейся части псевдотекста по формуле (4) была вычислена суммарная длина кода текста LX при использовании равномерных кодов для основного алфавита (1/N бит на символ, где N – мощность алфавита):

LX=k∙NUM=3∙71=213 бит    (4)

где k – количество знакомест в двоичном представлении кода (по Хаффману) символа алфавита псевдотекста; NUM – количество символов в тексте.
Далее по (5) вычислялась суммарная длина кода текста LHuff(X) при использовании кодов Хаффмана для основного алфавита:
LHuff(X) = (кол. биткол. символов) = 147 бит                                         (5)
где суммирование происходило по k (количество букв алфавита).
После чего была закодирована оставшаяся часть текста с помощью словаря подстрок D и кодов Хаффмана Huff(D):

ТО_.МА_.АТ.ОМ._ТОМ.ААМОТ._АМА.М_М_.ТО_.ТОАМ._АА_.ТО.ТО_ТО.МАМА.ТОАМ.А_МА_.АМ_.ОТА.М_ТО.МА_Т.ОМА.ТОМА_.ОТ_.АМТ.О_Т.ОМА.ТО_Т.ОМАА

001000001.1110001.10001.00011.00100100011.101011000001.001101110.1100111001.001000001.0010001011.0011010001.001000.001000001001000.11101110.0010001011.100011110001.1011001.00000110.11001001000.1110001001.0001110.0010001110001.000001001.1011001.000001001.0001110.001000001001.000111010

В таблице 2 приведены значения длин кода  в битах при различных вариантах кодирования:
Таблица 2 – Значения длин кода
LHuff(D)    LHuff(X)    LX
125    147    213

Суммарная длина кода текста LHuff(D)=125 бит. Сравнивая между собой средние длины двоичного кода, приходящихся на один символ при кодировании тремя указанными способами, можно сделать вывод, что в данном случае максимальное сжатие дало кодирование с помощью словаря подстрок D. Исходя из значений Hmax, HX и HD, можно сделать вывод о большой однородности текста.

Заключение

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

Список использованных источников

1.    Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов: Учеб. пособие для вузов по спец. «Автоматизация и механизация процессов обработки и выдачи информации». – М.: Высш. шк., 1987. – 248 с.
2.    Советов Б.Я. Информационная технология: Учеб. для студ. вузов по спец. Автоматизир. системы обраб. информ. и управления». – М.: Высш. шк., 1994. – 366 c.
3.    Сэломон Д. Сжатие данных, изображений и звука – Москва: Техносфера, 2004. – 368с.
4.    Алгоритмы архивации данных (http://www.structur.h1.ru/arch.htm)

Приложение А

Дерево подстрок псевдотекста
_(19)    _А(5)    _АМ(3)
_М(3)
_Т(9)    _ТО(9)    _ТОМ(6)     _ТОМА(6)
А(23)    А_(6)
АА(3)
АМ(9)    АМ_(4)
АМА(3)
АТ(4)    АТО(4)
М(20)    М_(6)    М_Т(3)     М_ТО(3)
МА: 12    МА_(5)
МАТ(3)    МАТО(3)
О(19)    О_(5)    О_Т(4)    О_ТО(4)     О_ТОМ(3)    О_ТОМА(3)
ОМ(8)    ОМА(7)
ОТ(4)
Т(19)    ТО(16)    ТО_(5)    ТО_Т(4)    ТО_ТО(4)    ТО_ТОМ(3)    ТО_ТОМА(3)
ТОМ(8)    ТОМА(7)

Рисунок А.1 – Иерархическое представление подстрок

Приложение Б

Таблицы для кодирования по методу Хаффмана
Таблица Б.1 – Коды Хаффмана Huff(D)
k    dk    F(dk)    Huff(dk)    символов
1    А    23    10    1
2    М    20    11    1
3    _    19    001    1
4    О    19    000    1
5    Т    19    01    1
6    ТО    16    01000    2
7    МА    12    1110    2
8    _Т    9    00101    2
9    _ТО    9    00101000    3
10    АМ    9    1011    2
11    ОМ    8    00011    2
12    ТОМ    8    0100011    3
13    ОМА    7    0001110    3
14    ТОМА    7    010001110    4
15    _ТОМ    6    0010100011    4
16    _ТОМА    6    001010001110    5
17    А_    6    10001    2
18    М_    6    11001    2
19    _А    5    00110    2
20    МА_    5    1110001    3
21    О_    5    000001    2
22    ТО_    5    01000001    3
23    АМ_    4    1011001    3
Таблица Б.2 – Коды Хаффмана Huff(X)
k    dk    F(dk)    Huff(dk)
1    А    23    10
2    М    20    11
3    _    19    001
4    О    19    000
5    Т    19    01