Курсовая с практикой на тему Реализация алгоритмов кодирования

Содержание:

ВВЕДЕНИЕ……………………………………………………………………………………………………………………….. 3

ГЛАВА 1. ТЕОРЕТИЧЕСКИЙ ОБЗОР………………………………………………………………………………… 4

1.1 Поточные и словарные алгоритмы……………………………………………………………………………. 4

1.1.1 Кодирование длин серий……………………………………………………………………………………. 4

1.1.2 Словарное сжатие (алгоритмы LZ)…………………………………………………………………….. 6

1.2 Энтропийное кодирование……………………………………………………………………………………….. 6

1.2.1 Арифметическое кодирование……………………………………………………………………………. 6

ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ…………………………………………………………………….. 9

2.1 Структура кода…………………………………………………………………………………………………………. 9

2.2 Примеры запуска…………………………………………………………………………………………………….. 11

ГЛАВА 3. ЭЛЕМЕНТЫ БЕЗОПАСНОСТИ КОДА……………………………………………………………. 13

ЗАКЛЮЧЕНИЕ………………………………………………………………………………………………………………… 14

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

ПРИЛОЖЕНИЕ А. КОД ПРОГРАММЫ…………………………………………………………………………… 16

Файл main.cpp………………………………………………………………………………………………………………. 16

Файл Encoding_classes.h……………………………………………………………………………………………….. 17

Файл Encoding_classes.cpp…………………………………………………………………………………………….. 22

Введение:

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

1. Кодирования серий последовательностей
(RLE)

2. Арифметического кодирования

3. Словарного алгоритма Лемпеля-Зива

Также будет экспериментально и теоретически изучена
эффективность данных алгоритмов в целом и в сравнении друг с другом.

Для программирования этих алгоритмов будет использован
язык Си/Си++, каждый из алгоритмов будет реализован в виде класса.[1,2]

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

Заключение:

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

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

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

3. Словарный алгоритм Лемпеля-Зива
увеличивает эффективность при увеличении объёма кодируемых данных за счёт
накопления словаря в процессе кодирования. Предел эффективности кодирования
ограничен максимальным размером словаря/доступной памяти. Также возможно
увеличить эффективность за счёт использования двоичных файлов, однако в случае
данного алгоритма положительная эффективность сжатия достижима в том числе за
счёт сжатия большого объёма текста и достаточного большого размера словаря.

В
целом, наибольшая эффективность выявлена у алгоритма Лемпеля-Зива. Это также
подтверждается изученным материалом по данным алгоритмам.[5]

Фрагмент текста работы:

ГЛАВА
1. ТЕОРЕТИЧЕСКИЙ ОБЗОР

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

1. Поточные и словарные алгоритмы. К этой
группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и т.п.
Особенностью всех алгоритмов этой группы является то, что при кодировании
используется не исходная информация о частотах символов в сообщении, а
информация, встречавшаяся ранее в процессе кодирования.[3]

2. Алгоритмы статистического(энтропийного)
сжатия. Эти алгоритмы сжимают информацию, используя неравномерность частот, с
которыми различные символы встречаются в сообщении. К алгоритмам этой группы
относятся алгоритмы арифметического и префиксного кодирования. [4]

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

1.1.1
Кодирование длин серий

Кодирование длин серий (RLE — Run-Length Encoding) —
это один из самых простых и распространённых алгоритмов сжатия данных. В этом
алгоритме повторяющиеся символы заменяются символом и количеством повторов.

Например, строку «ААААА», требующую для хранения 5
байт (при условии, что на хранение одного символа отводится байт), можно
заменить на