Отчет по лабораторной работе по дисциплине «Информационные технологии»




Скачать 160.33 Kb.
НазваниеОтчет по лабораторной работе по дисциплине «Информационные технологии»
Дата19.01.2013
Размер160.33 Kb.
ТипОтчет


Министерство образования Российской Федерации

ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
(ОмГТУ)

Кафедра «Автоматизированные системы обработки информации и управления»


ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ

по дисциплине «Информационные технологии»

УНИВЕРСАЛЬНОЕ КОДИРОВАНИЕ.
СЛОВАРНОЕ МОДЕЛИРОВАНИЕ.
АНАЛИЗ ОПТИМАЛЬНОСТИ КОДОВ ХАФФМАНА


Принял:

преподаватель Юдин Е.Б.

______________________

подпись, дата

Выполнил:

студент гр. АС-323 Кузнецова В.Е.

______________________

подпись, дата


Омск 2005

Реферат

Отчет по лабораторной работе 12 с., 2 части, 4 рис., 4 таб., 2 источника, 2 прил.

КОД ХАФФМАНА, ДИСКРЕТНЫЙ ИСТОЧНИК, СЛОВАРНОЕ МОДЕЛИРОВАНИЕ, КОДИРОВАНИЕ, ЭНТРОПИЯ, ДЛИНА КОДА.

Предметом исследования лабораторной работы являлся принцип универсального кодирования, методы словарного моделирования дискретных источников и кодирование методом Д.А. Хаффмана.

Цель работы – универсальное кодирование дискретного нестационарного источника на примере словарного моделирования и оценка оптимальности кодов Хаффмана.

В ходе работы был сгенерирован псевдотекст (около 150 символов) с использованием четырёх букв и знака подчёркивания в качестве разделителя слов, Был проведён анализ первой трети текста на основании которого построен словарь подстрок, который использовался при кодировании оставшихся двух третей текста.

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


Содержание

Введение 4

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

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

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

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

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

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

7 Анализ графиков оптимальной длины кода и длины кода Хаффмана 8

Заключение 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+С}.

Для эффективного кодирования сообщений алфавита любой мощности может быть использован метод Д.А. Хаффмана, который позволяет построить для каждого сообщения уникальный префиксный код длины 1 округлённой до большего целого [1, 2].

Цель работы являлось универсальное кодирование дискретного нестационарного источника на примере словарного моделирования и оценка оптимальности кодов Хаффмана.


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

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

Для генерации псевдотекста мной был взят алфавит, состоящий из четырех букв названия популярного напитка и знака подчеркивания в качестве разделителя слов: X = {"К", "О", "Л", "А", "_"}.

Из символов полученного алфавита был составлен собственный непрерывный псевдотекст (около 150 символов), интуитивно подражая фонетическим, орфографическим и грамматическим свойствам естественного человеческого языка:

ОКО_КОКО_КОЛА_ЛОЛО_О_А_КОЛА_ОО_ОА_ЛА_КО_ЛА_►ЛО_А_ЛА_КАКА_А_КАЛО_А_ЛАЛАЛАКА_КАЛО_ЛО_ЛА_ЛАКА_КАЛА_КАЛАЛА_ЛАКА_КАЛА_ЛА_ЛО_ЛА_КАКАО

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

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

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

–– нас интересовали подстроки, встречающиеся хотя бы дважды в тексте;

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

Однако в ходе работы подобный способ формирования подстрок оказался неудачным. Действительно, при анализе рисунка А.1 приложения А в соотнесении с оставшимся текстом можно заметить, что сформированное множество подстрок не способно полностью покрыть текст и заменить тем самым алфавит (у нас нет буквы «Д», «И», таких после которых может следовать любая буква, а потребность в них есть). По этой причине множество подстрок было преобразовано. Преобразованное множество строк представлено на рисунке А.2 приложения А.

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

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

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

Р

исунок 1 – Вычисление энтропии в Exel

Перед сравнением полученные оценки энтропии были нормализированы – поделены на среднее количество символов в подстроке ансамбля:


HD=4,198081/3=1,39936 бит. (2)


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


Hmax=-log2N= -log25=2,32193 бит. (3)


В таблице 1 приведены значения полученной энтропии в битах:

Таблица 1 – Значения полученной энтропии

HD

Hmax

HX

1,39936

2,32193

2,22499



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

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

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

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


LX=kNUM=249 бит, (4)


где k – количество знакомест в двоичном представлении кода символа алфавита псевдотекста; NUM – количество символов в тексте (в оставшихся двух третьих).

Далее по (5) вычислялась суммарная длина кода текста LHuff(X) при использовании кодов Хаффмана для основного алфавита:


LHuff(X) = (кол. биткол. символов)=224 бит, (5)


где суммирование происходило по k (количество букв алфавита).

После чего была закодирована оставшаяся часть текста с помощью словаря подстрок D и кодов Хаффмана Huff(D):


ЛО._.А. _ЛА_. К. А. К. А. _. А. _. К. А. ЛО. _. А_Л. А. Л. А. Л. А. К. А. _. К. А. ЛО. _. ЛО. _ЛА_. Л. А. К. А._. К. А. Л. А. _. К. А. Л. А. ЛА_. Л. А. К. А. _. К. А. ЛА_.ЛА_. ЛО. _ЛА_. К. А. К. А. О


01011. 100. 0011. 111101. 1100. 0011. 1100. 0011. 100. 0011. 100. 1100. 0011. 01011. 100. 01100. 0011. 1010. 0011. 1010. 0011. 1100. 0011. 100. 1100. 0011. 01011. 100. 01011. 111101. 1010.0011. 1100. 0011. 100. 1100. 0011. 1010. 0011. 100. 1100. 0011. 1010. 0011. 11101. 1010. 0011. 1100. 0011. 100. 1100. 0011. 11101. 11101. 01011. 111101. 1100. 0011.1100. 0011. 110


В таблице 2 приведены значения длин кода в битах при различных вариантах кодирования:

Таблица 2 – Значения длин кода

LHuff(D)

LHuff(X)

LX

249

224

249


Суммарная длина кода текста, таким образом, LHuff(D)=249 бит. Сравнивая средние длины двоичного кода, приходящиеся на один символ при кодировании, тремя указанными способами между собой можно, сделать вывод, что в данном случае целесообразно было бы кодировать текст по Хаффману без использования словаря подстрок. Что касается кодирования с помощью словаря подстрок D Huff(D), то этот результат (то, что код оказался не больше или меньше, а равным коду, построенному без анализа первой трети) можно объяснить совершенной неоднородностью в построении слов в базовой (первая треть) и исследуемой (оставшиеся две трети) частях текста. Если же текст был бы более однородным, то исходя из значений Hmax, HX и HD, анализ которых был сделан выше, можно предположить, что максимальное сжатие было бы при кодировании с помощью словаря подстрок D.

  1. Анализ графиков оптимальной длины кода и длины кода Хаффмана

В завершении лабораторной работы были построены графики оптимальной длины кода и длины кода Хаффмана для событий с разными вероятностями, изображенные на рисунке 2.



Рисунок 2 – График оптимальной длины кода

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

Заключение

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

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

1 Советов Б.Я. Информационная технология: Учеб. для студ. вузов по спец. «Автоматизир. системы обраб. информ. и управления». – М.: Высш. шк., 1994. – 366 c.

2 Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов: Учеб. пособие для вузов по спец. «Автоматизация и механизация процессов обработки и выдачи информации». – М.: Высш. шк., 1987. – 248 с.


Приложение А
Дерево подстрок псевдотекста


О(13)

ОКО_КО(2): ОКО_КОК, ОКО_КОЛ

ОЛ(3)

ОЛА_(2): ОЛА_Л, ОЛА_О

ОЛО

О_(6)

О_КО(2):ОКОЛ, ОКОК




О_О (2):О_О_,О_ОА




О_А




О_Л

ОА

ОО

КО(6)

КО_(3)

КО_КО(2): КО_КОК, КО_КОЛ

КО_Л

КОК

КОЛА_(2):КОЛА_Л, КОЛА_О

А_(6)

А_О

А_КО(2):А_КОЛ, А_КО_

А_Л(2):А_ЛО, А_ЛА

Л(6)

ЛО(2):ЛО_, ЛОЛ

ЛА_(4):ЛА_Л, ЛА_О, ЛА_К

_(12)

_КО(4)

_КОК

_КОЛА_(2):_КОЛА_О, _КОЛА_Л

_КО_

_Л(3)

_ЛА_(2):_ЛА_К

_ЛО

О(3):_О_, _ОО, _ОА



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


О(13)

ОКО_КО(2): ОКО_КОК, ОКО_КОЛ

ОЛ(3)

ОЛА_(2):ОЛА_Л, ОЛА_О

ОЛО

О_(6)

О_КО(2):ОКОЛ, ОКОК




О_О (2):О_О_,О_ОА




О_А




О_Л

ОА

ОО

К(6)

КО_(3)

КО_КО(2): КО_КОК, КО_КОЛ

КО_Л

КОК

КОЛА_(2):КОЛА_Л, КОЛА_О

А(6)

А_О

А_КО(2):А_КОЛ, А_КО_

А_Л(2):А_ЛО, А_ЛА

Л(6)

ЛО(2):ЛО_, ЛОЛ

ЛА_(4):ЛА_Л, ЛА_О, ЛА_К

_(12)

_КО(4)

_КОК

_КОЛА_(2):_КОЛА_О, _КОЛА_Л

_КО_

_Л(3)

_ЛА_(2):_ЛА_К

_ЛО

О(3):_О_, _ОО, _ОА



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

Приложение Б
Таблицы для кодирования по методу Хаффмана


Таблица Б.1 – Коды Хаффмана Huff(D)

k

dk

F(dk)

Huff(dk)

символов

1

О

13

110

1

2

_

12

100

1

3

О_

6

1011

2

4

КО

6

1100

2

5

А_

6

0011

2

6

Л

6

1010

1

7

_КО

4

0010

3

8

ЛА_

4

11101

3

9



3

11111

2

10



3

00001

2

11

КО_

3

00000

3

12

ОЛ

3

00010

2

13

КО_КО

2

01111

5

14

КОЛА_

2

01110

5

15

А_КО

2

01101

4

16

А_Л

2

01100

3

17

ЛО

2

01011

2

18

О_КО

2

01010

4

19

О_О

2

01001

3

20

ОКО_КО

2

00011

6

21

ОЛА_

2

01000

4

22

_КОЛА_

2

111100

6

23

_ЛА_

2

111101

3

Таблица Б.2 – Коды Хаффмана Huff(X)

k

dk

F(dk)

Huff(dk)

1

К

6

01

2

О

13

10

3

Л

6

000

4

А

6

001

5

_

12

11



Похожие:

Отчет по лабораторной работе по дисциплине «Информационные технологии» iconОтчет по лабораторной работе по дисциплине «Информационные технологии»
Государственное образовательное учреждение высшего профессионального образования "омский государственный технический университет"...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconОтчет по лабораторной работе по дисциплине "Технологии программирования" на тему " Автоматизированная система поиска оптимального пути по заданному критерию "
Произвести анализ предметной области по методологии объектной декомпозиции и разработать логический проект системы по технологии...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconОтчет по лабораторной работе по дисциплине "Технологии программирования" на тему " Автоматизированная система поиска оптимального пути по заданному критерию "
Произвести анализ предметной области по методологии объектной декомпозиции и разработать логический проект системы по технологии...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодические указания к лабораторной работе по дисциплине
Разработка баз данных в среде Delphi: методические указания к лабораторной работе по дисциплине "Информационное обеспечение систем...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодические указания к лабораторной работе по дисциплине
Операции с таблицами баз данных в среде Delphi: методические указания к лабораторной работе по дисциплине "Информационное обеспечение...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодические указания по дисциплине "Информационные системы в экономике" разработали: профессор взфэи брага В. В
Методические указания по выполнению лабораторной работы в среде ms navision по дисциплинам: «Информационные системы в экономике»...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодическое пособие по курсовой работе информационные технологии
Методическое пособие предназначено для студентов, обучающихся по направлению «Информатика и вт» 230100. 62, руководителей курсовых...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconОтчет о научно-исследовательской работе
Квалификации, открытое образование, международная конференция, информационно-образовательная среда, Интернет, Телеконференции, электронные...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодические указания к лабораторной работе по дисциплине «Моделирование систем»
Моделирование простых непрерывных систем с помощью MatLab : Методические указания к лабораторной работе по дисциплине «Моделирование...
Отчет по лабораторной работе по дисциплине «Информационные технологии» iconМетодические указания по выполнению лабораторной работы №14 для студентов специальности 071900 “Информационные системы и технологии”
Установка и администрирование сервера InterBase V. 0 в Linux. Методические указания по выполнению лабораторной работы №14 для студентов...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница