Курсовая работа

Кодирование методом Шеннона-Фано. Обработка множеств с использованием структуры «Магазин»

Категория:

Курсовая работа

Дисциплина:

Языки программирования

Город:

Беларусь, Минск

Учебное заведение:

БНТУ, ФИТР

Стоимость работы:

20 руб.

Оценка: 10
Объем страниц: 32
Год сдачи: 2021
Дата публикации: 07.05.2021

* Кроме файла с работой, также есть архив с дополнительными файлами.

Описание дополнительных файлов:

Исходный код программы

Фрагменты для ознакомления

Кодирование методом Шеннона-Фано. Обработка множеств с использованием структуры «Магазин»

 

СОДЕРЖАНИЕ

1 ВВЕДЕНИЕ.. 5

2 ТЕОРИТИЧЕСКИЙ ВОПРОС.. 6

2.1 Кодирование методом Шеннона-Фано. 6

3 ПРАКТИЧЕСКИЙ РАЗДЕЛ.. 13

3.1 Постановка задачи. 13

3.2 Математическая модель. 13

3.3 Описание программы.. 15

3.4 Блок-схема. 17

3.5 Контрольный пример. 21

4 ВЫВОДЫ... 27

5 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 28

6 Приложение. 29

 

 

1 ВВЕДЕНИЕ

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

Понятие множества в языке программирования несколько отличается от математического определения этого понятия, но смысл сохраняется. Основное отличие в том, что в программировании множество может содержать только конечное число элементов, т.е. не может состоять из бесконечного числа объектов. В математике же последнее допустимо. Например, мы можем определить множество натуральных чисел, которое бесконечно: N = {1, 2, 3, ...}

Множеством называется совокупность элементов, объединенных по какому-либо признаку. Объекты, из которых состоит множество, называются элементами множества. Множество, не содержащее ни одного элемента, называется пустым. Множества, содержащие равные элементы, называются равными.

Правила действия над множествами:

  • объединение множеств – множество, состоящее из всех элементов, принадлежащих хотя бы одному множеству;
  • пересечение множеств – множество, состоящее из элементов, принадлежащих всем множествам;
  • разность множеств – множество, состоящее из элементов, не принадлежащих другому множеству.

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

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

Учет статистики сообщений на основании теоремы Шеннона позволяет строить код, в котором часто встречающимся сообщением присваиваются более короткие кодовые комбинации, а редко встречающимся – более длинные. 

Методы построения таких кодов впервые предложили одновременно в 1948-49 годах Р. Фано и К. Шеннон, поэтому код назвали кодом Шеннона-Фано.

 

2 ТЕОРИТИЧЕСКИЙ ВОПРОС

2.1 Кодирование методом Шеннона-Фано

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

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

Оптимальным статическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу символа алфавита в зависимости от априорных вероятностей их появлений. 

Оптимальными неравномерными кодами (ОНК) называются коды, в которых символы алфавита кодируются кодовыми словами минимальной средней длины. 

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

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

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

Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона-Фано.

Кодирование методом Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano).

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

Также с помощью кодирования методом Шеннона-Фано, анализируя входные данные, можно построить бинарное дерево минимального кодирования. Используя это дерево можно выполнить повторное считывание входных данных и закодировать их.

Рассмотрим алгоритм вычисления кодов Шеннона-Фано, в качестве примера представлена последовательность “Кодирование Шеннона-Фано.”. Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)), и отсортировать её в порядке убывания вероятности символов (см. таблицу 1).

Таблица 1. Частота появления символов в примере предложения
c(i) – символp(c(i)) – частота появления
н5
о4
а3
е2
и2
Таблица 1. Частота появления символов в примере предложения
пробел 1
в1
д1
К1
р1
Ф1
Ш1
- (дефис)1
. (точка)1

Ниже представлена таблица, разделенная на две части так, чтобы общее число появлений символов в верхней половине таблицы приблизительно равнялось общему числу появлений в нижней половине. Предложение содержит 25 символов, то верхняя половина таблицы должна отражать приблизительно 12 появлений символов. Значит разделительная линия будет находиться между символом №3 и символом №4. В результате этого верхняя половина таблицы будет отражать появление 12 символов, а нижняя 13 (см. таблицу 2). 

 

Таблица 2. Начало построения дерева Шеннона-Фано

 СимволКоличество появлений

1

н

5

2

о

4

3

а

3

4

е

2

5

и

2

6

пробел 

1

7

в

1

8

д

1

9

К

1

10

р

1

11

Ф

1

12

Ш

1

 

Таблица 2. Начало построения дерева Шеннона-Фано

13

 (дефис)

1

14

 (точка)

1

 

Результирующее дерево Шеннона-Фано представлено на рисунке 2.1.

Рисунок 2.1 – Результирующее дерево Шеннона-Фано

 

Разделительные линии в таблице 3 изображены различными по длине, чтобы разделительная линия 1 была самой длинной, разделительная линия 2 немного короче и так далее, вплоть до самой короткой разделительной линии 6. Этот подход обусловлен тем, что разделительные линии образуют повернутое на 90° бинарное дерево (чтобы убедиться в этом, можно повернуть таблицу на 90° против часовой стрелки). Разделительная линия 1 является корневым узлом дерева, разделительные линии 2 двумя его дочерними узлами и т.д. Символы образуют листья дерева. Результирующее дерево в обычной ориентации показано на рисунке 2.2

 

3 ПРАКТИЧЕСКИЙ РАЗДЕЛ

3.1 Постановка задачи

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

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

Предусмотреть многоуровневое меню:

  1. Заполнение массива из файла (выбор файла, тек. папка, любая папка). 
  2. Выбор операции
  3. Завершение либо переход к пункту 1
  4. Вывод результата: на экран или в файл
  5. Выход

Структура Магазин:

i)     Номер (ключ)

ii)    Название

iii)   Фамилия И.О. директора

iv)   К-во сотрудников

v)    Годовой доход

 

3.2 Математическая модель

Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит во множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Для удобства множества изображают в виде кругов, которые называются диаграммами Эйлера–Венна. Самой фундаментальной операцией над множествами является определение того, принадлежит некоторый элемент данному множеству или нет. Операции над множествами:

Объединение множеств смотрите рисунок 3.1

Рисунок 3.1 – Объединение множеств

 

Объединение множеств А и B – это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или B, т.е. принадлежат А или принадлежат B.  Объединение А и B обозначается через А∪B. Формально А∈А∪B ⇔ А∈А или А∈B.

Объединение множеств А и B – это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или B, т.е. принадлежат А или принадлежат B.  Объединение А и B обозначается через А∪B. Формально А∈А∪B ⇔ А∈А или А∈B.

Пример 1. Даны множества А = {-6, -3, 0, 3, 6} и B = {0, 2, 4, 6, 8}. Тогда A∪B = {-6, -3, 0, 2, 3, 4, 6, 8}. 

  1. Пересечение множеств смотрите рисунок 3.2

Рисунок 3.2 – Пересечение множеств

 

Пересечение множеств А и B – это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству А, так и множеству B. Пересечение множеств обозначается А∩B. Формально А∈А∩B ⇔ А∈А и А∈B.

Пример 2. Даны множества А = {-6, -3, 0, 3, 6} и B = {0, 2, 4, 6, 8}. Тогда A ∩ B = {0, 6}.

 Если A – множество точек левого круга, а B – множество точек правого круга, то А∩B представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

  1. Разность множеств смотрите рисунок 3.3

Рисунок 3.3 – Разность множеств

 

Разность множеств определена только для двух множеств. Разностью множеств А и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат А и не принадлежат B. Обозначается: А\B. Формально: А∈А\B ⇔ А∈А и А∉B.

Пример 3. А={1,2,3,4,5}, B={2,4,6,8}, А\B={1,3,5}, B\А={6,8}.

 

3.3 Описание программы

В начале программы пользователю предлагается меню с выбором режима работы. В первом пункте меню пользователь может выбрать выбор множеств и перейти к операциям над ними. При выборе второго пункта меню – программа будет завершена. Если будет введены некорректный пункт меню, на экран будет выведено сообщение «Режим работы задан неправильно» и «Для продолжения работы нажмите Enter», и после нажатия клавиши Enter пользователь вернётся в меню выбора режима работы.

После выбора первого пункта на экран будет выведено сообщение «Для работы можно использовать 5 множеств, которые хранятся в следующих файлах:» и выведен список файлов. После выводится сообщение «Вам нужно выбрать два множества для работы, введя номер соответствующего файла» и «Первое множество из файла номер?». При вводе пользователем некорректных данных будет выведено повторно сообщение «Первое множество из файла номер?» и пользователь сможет повторно выбрать файл с множеством. Если файл выбранный не существует, то будет выведено сообщение «Файл не найден».

После выбора двух множеств будет выведено меню выбора операций над множествами. При некорректным выборе пункта меню будет выведено сообщение «Операция выбрана неправильна» и «Для продолжения работы нажмите ENTER» и после нажатия клавиши Enter осуществляется выход в меню выбора режима работы. Если пользователь выбрал верный пункт меню, то будет выведено сообщение «Результат записан в файл. Вывести его на экран? Y/N». При вводе символа Y или у будет выведен на экран результат работы программы. После ознакомления с результатом нажимаем Enter и переходим в меню выбора режима работы.

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

void CopyData (myTShop *dest, myTShop *src); //копируем данные магазина <src> в магазин <dest>

bool IsEqual (myTShop *sh1, myTShop *sh2); //проверка двух магазинов на равенство

myTShop **FillFromArray (char *file_name); //создаем массив из N = 10 элементов на основе данных файла

void Deletearray (myTShop **arr); //освобождение памяти от массива

bool ShowFile (char *file_name); //вывод данных из файла с именем <file_name> на консоль

bool Unite (myTShop **arr1, myTShop **arr2);//запись в файл объединения двух массивов

bool Intersect (myTShop **arr1, myTShop **arr2);//запись в файл пересечения двух массивов

bool Substract (myTShop **arr1, myTShop **arr2);//запись в файл разности двух массивов

void ShowShop (myTShop *shop);//вывод данных об одном магазине на консоль

void ShowArray (myTShop **arr);   //вывод данных из массива на консоль

void Task();//основной модуль с выбором заданий и выполнением

int main(); // главная функция, которая вызывает функцию Task()

 

3.4 Блок-схема

 

 

 

4 ВЫВОДЫ

В результате работы над данным курсовым проектом были закреплены практические навыки работы в среде программирования Microsoft Visual C++.

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

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

Исходный текст программы разбит на функций. Это позволяет сократить объём программы, сделать её понятнее и доступнее.

В результате работы была написана программа, которая реализует обработку нескольких массивов структур (до 5 массивов по 10 элементов) по примеру множеств. Программа считывает данные из файла. Также она может выводить полученный результат и в файл, и в консоль. В программе реализованы следующие операции с множествами: объединение, пересечение, вычитание. На практике были закреплены знания по алгоритмическому языку С++, а именно работа с операторами циклов и ветвлений, стандартными функциями ввода-вывода, функциями работы с файлами с помощью потока. Программа не использует временных файлов и поэтому .exe файл может находиться на защищенном от записи носителе, главное правильно указать расположение файла результата.

63