Анализ трудоемкости алгоритмов - Программирование, компьютеры и кибернетика контрольная работа

Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


Данная работа представляет собой описание программы, реализующей алгоритм Хаффмана, а именно, позволяет закодировать текст двоичным кодом так, чтобы объем информации был минимален, а также оценку вычислительной сложности данной программы.
Существует несколько алгоритмов кодирования информации двоичным кодом, но для решения поставленной задачи наиболее подходит алгоритм Хаффмана кодирования информации.
Идея метода - часто повторяющиеся символы нужно кодировать более короткими цепочками битов, чем цепочки редких символов. Строится двоичное дерево, листья соответствуют кодируемым символам, код символа представляется последовательностью значений ребер (эти значения в двоичном дереве суть 1 и 0), ведущих от корня к листу. Листья символов с высокой вероятностью появления находятся ближе к корню, чем листья маловероятных символов.
Это позволяет закодировать информацию (текст) двоичным кодом, причем объем информации будет минимален. Однако, для раскодирования текста нам потребуется алфавит, а именно «дерево Хаффмана», которое было построено при кодировании. Решение этой проблемы не включено в решение поставленной задачи, т.к. при небольших объемах информации алфавит может занимать большее количество памяти, чем сама информация (текст).
Программа реализована на языке C++. Она считывает входной файл и записывает его двоичное представление в выходной файл. Нужно заметить, что, теоретически, входной файл может быть абсолютно любым, будь то текстовый файл, картинка или видеофайл, т.к. чтение файла происходит по байтам. Но правильность работы проверялась только на текстовых файлах.
Программа выводит на частоту появления символа в тексте, код каждого символа после кодирования, и начальный текст в двоичном представлении.
vector symbol_vector; //список всех символов
vector Tree_vector; //дерево Хаффмана
vector code; //бинарный код символов
Tree* main_tree; //указатель на корень дерева
void Find_this_symbol(char c) //поиск символов в списке
for (int i=0;isymbol = symbol_vector[i].symbol;
tr->weight = symbol_vector[i].amount;
void Sort() //Сортировка эл-тов дерева по их весу
for (int i=1;iweight>Tree_vector[i-1]->weight)
void Create_Tree() //создаем дерево Хаффмана
while (Tree_vector.size()!=1) //до тех пока не останется один узел (корень)
Sort(); //сортируем символы по их весу (частоте)
Tree* temp = new Tree; //создаем новый узел
//вес нового узла равен сумме весов двух эл-тов с наименьшим весом
Tree_vector[tr_size-2]->weight + Tree_vector[tr_size-1]->weight;
//левый сын нового узла указывает на последний эл-т
temp->left_son = Tree_vector[tr_size-1];
Tree_vector.pop_back(); //выбрасываем из списка эл-т с минимальным весом
//повторяем операцию для предпоследнего эл-та
temp->right_son = Tree_vector[tr_size-2];
//вместо двух выброшенных эл-т записываем новый
main_tree = Tree_vector[0]; //запоминаем указатель на корень дерева
void Coding_Tree(Tree* a) //кодируем дерево Хаффмана
if(a->left_son!=NULL) //если у узла есть левый сын
code.push_back(0); //добавляем в строчку кода 0
Coding_Tree(a->left_son); //рекурсивно повторяем операции
if(a->right_son!=NULL) //если у узла есть правый сын
code.push_back(1); //добавляем в строчку кода 1
for (int i=0;i< symbol_vector.size();i++)
if (symbol_vector[i].symbol == c) //ищем эл-т с найденным символом
symbol_vector[i].code = code; //и присваиваем ему "собранный" код
code.pop_back(); //выбрасываем из строчки кода последний эл-т
void Print_Symbol_Codes() //вывести на экран коды символов
for (int i=0;i Tree_vector в отдельный файл и потом считать, т.к. в ней хранятся коды всех элементов.
При нахождении вычислительной сложности (анализе трудоемкости) алгоритма за N мы примем количество символов исходного кода.
Можно заметить, что из всех используемых функций только две функции используют сам алгоритм Хаффмана и, поэтому, являются важными при анализе трудоемкости. Это функции Create_Tree где мы создаем дерево в зависимости от веса символов и функция Coding_Tree. Начнем с оценки этих функций.
В функции Create_Tree мы используем цикл «пока размер вектора не равен 1», следовательно, цикл выполняется N-1 раз. Отсюда можно предположить что сложность функции будет O(N), т.е. изменяется линейно. Однако в цикле вызывается функция Sort, поэтому нужно рассчитать и сложность этой функции.
Функция Sort представляет собой сортировку вектора Tree_vector, а точнее элементов внутри него по параметру weight (вес). Сортировка представляет собой улучшенный метод пузырька. Т.е. цикл управляет флажком repeat и следовательно количество проходов цикла будет меньше, чем при статичном методе пузырьке, где выполняется вложенный цикл. Таким образом, получаем, что в «лучшем» случае цикл выполнится N раз, а в «худшем» случае он выполнится N2 раз. В такой ситуации мы смотрим на «худший» случай и принимаем сложность функции Sort как O(N2).
В итоге, т.к. функция Sort вызывается внутри функции Create_Tree, чтобы получить общую сложность функции нам необходимо перемножить O(N) и O(N2). Таким образом, сложность функции Create_Tree составит O(N3).
Следует заметить, что сложность алгоритма Хаффмана (в общем случае) считается равной O(N*log(N)), где первый множитель - количество проходов по циклу (основной цикл) и следовательно его сложность, а второй (log(N)) - сложность сортировки элементов по их весу(частоте). Т.е. в данной программе функция Sort реализована «неидеально», отсюда получается разная сложность алгоритма в теории и на практике.
Перейдем к функции Coding_Tree. Здесь представлена рекурсивная функция обхода бинарного дерева. Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(N)). Соответственно, для N объектов сложность будет составлять O(N*log(N)). В нашем случае мы ищем листья дерева без «сыновей». Причем при нахождении этого листа мы в цикле ищем символ в векторе символов и присваиваем ему код. Цикл выполняется N раз (статично). Посчитаем общую сложность функции Coding_Tree:
O((N*log(N)) + O(N) = O(N*(log(N)+1)) = O(N*log(N))
программа алгоритм кодировка хаффман
Отсюда имеем, что трудоемкость алгоритма составляет O(N3) + O(N*log(N)).
Это трудоемкость самого алгоритма Хаффмана, реализованного в программе. Но программа состоит из больших частей, чем сам расчет. Для практики расчитаем общую сложность всей программы:
- Функция Read_File имеет сложность O(N2), т.к. в ней вызывается функция Find_this_symbol имеющая сложность O(N) , т.к. она в «худшем случае» проходит по всем N элементам, а сама функция Read_File также имеет сложность O(N).
- Функция Create_Null_Nodes статична и имеет сложность O(N).
- Функция Print_Symbol_Codes имеет двойной цикл, и оба цикла проходят значения от 0 до N, отсюда сложность всей функции составляет O(N2).
- Функция Print_Coded_Text которая представляет собой цикл выполняемый N раз, причем в себе он содержит двойной цикл, аналогичный циклу в предыдущей функции. Отсюда сложность всей функции составит O(N3).
- Функция Binary_Writing по строению аналогичная функции Print_Coded_Text и её трудоемкость составит O(N3).
В функции int main мы последовательно вызываем все перечисленные функции, поэтому можем составить общую трудоемкость алгоритма как сумму сложностей этих функций:
O(N) + O(N)+ O(N3)+ O(N*log(N))+ O(N2)+ O(N3)+ O(N3) =
= 2*O(N) + O(N2) + 3* O(N3) + O(N*log(N)) =
= O(N) + O(N2) + O(N3) + O(N*log(N)) = O(N*log(N))
Данная арифметика складывается из того, что константы при O(x) не учитываются. А сумма получилась равной O(N*log(N)), т.к. остальным сложности имеют меньшее значение, и являются слишком незначительными.
Программа представляет собой упрощенную версию архиватора, потому что размер исходного файла уменьшается приблизительно в 2 раза. На примере строчки «Hello, my name is Boxxy» мы можем увидеть, что исходный файл занимает 23 байта, а выходной - 10 байт. На примере стихотворения Тютчева «Silentium!» исходный файл занимает 492 байта, а выходной 293 байта (почти аналогичное отношение размеров). На примере первого тома произведения «Война и Мир» Л.Н. Толстого размер исходного файла составляет 709 килобайт, а выходного - 441 кб. Следует заметить, что выполнение последней операции затратило около 8 минут, из которых: 2 минуты выводился исходный текст, выполнение алгоритма Хаффмана и кодирование символов заняло порядка секунды, и остальное время - вывод закодированного файла на экран ( в виде нулей и единиц). Запись в файл также заняла около 10 секунд.
Отсюда вытекает что временные затраты самого алгоритма незначительны и не сильно увеличиваются с ростом входных данных. Дольше всего происходит обращение к диску на чтение/запись файла.
Реализация самой программы может быть улучшена в некоторых аспектах (лучшая сортировка, прерывание циклов вместо статического количества проходов, упрощение поиска символов в векторе символов использованием гибкостей языка C++ (например, структура map или list вместо vector)),однако на скорость выполнения программы это повлияет незначительно.
1. Лекция №8 «Анализ трудоемкости алгоритмов» из курса «Математическая логика и теория алгоритмов».
2. Статьи сайта habrahabr.ru «Оценка сложности алгоритмов» и «Метод Хаффмана на пальцах».
3. Статьи портала Wikipedia на тему оценки сложностей алгоритмов, метода Хаффмана, методов сортировки массивов, двоичных деревьев и обходов этих деревьев.
4. Статья сайта planetmath.org «Huffman's algorithm».
5. Произведения русских писателей Ф.И.Тютчева «Silentium!» и Л.Н.Толстого «Война и Мир».
Особенности кодирования информации с помощью метода Хаффмана. Реализация кодера и декодера с использованием статического алгоритма Хаффмана. Структура программы, оценка ее эффективности (степени сжатия) в зависимости от типа и размера сжимаемых файлов. курсовая работа [136,2 K], добавлен 15.06.2013
Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77. курсовая работа [51,7 K], добавлен 24.12.2012
Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ. презентация [528,9 K], добавлен 19.10.2014
Описание метода сжатия информации на основе двоичных кодирующих деревьев Хаффмана. Среда разработки Delphi версии 7.0. Понятия объектно-ориентированного программирования. Программа, разработанная в Delphi. Реализация на Delphi метода кодирования Хаффмана. курсовая работа [2,1 M], добавлен 26.03.2013
Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена. курсовая работа [487,3 K], добавлен 14.07.2011
Методы предобработки изображений текстовых символов. Статистические распределения точек. Интегральные преобразования и структурный анализ. Реализация алгоритма распознавания букв. Анализ алгоритмов оптического распознавания символов. Сравнение с эталоном. курсовая работа [2,1 M], добавлен 20.09.2014
Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе. реферат [90,6 K], добавлен 27.11.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Анализ трудоемкости алгоритмов контрольная работа. Программирование, компьютеры и кибернетика.
Сочинение По Тексту Чехова Чувство Веры
Доклад: Понятие системы права, отрасли права
Эсси Сайт
Темы Курсовых Работ По Психологии Управления
Транспортное право
Сочинение По Картине Степанова Лоси 2 Класс
Реферат: Примирение с потерпевшим. Скачать бесплатно и без регистрации
Реферат: Social Security
Принципы Рационального Природопользования Реферат
Примерные Эссе По Обществознанию 2022
Курсовая Работа На Тему Экономический Потенциал И География Базово-Межотраслевого Топливо-Энергетического Комплекса Страны
Эксплуатационная Практика Отчет
Курсовая работа по теме Инженерное обустройство территории квартала г. Кемерово
Детский Оздоровительный Лагерь Реферат
Реферат На Тему Методологічні Засади Розуміння Національної Культури
Реферат: Индия. Проблемы и пути их решения. Скачать бесплатно и без регистрации
Контрольная работа по теме Упаковка муки пшеничной
Дипломная работа по теме Анализ состояния геоинформационных технологий в решении типовых задач управления региональной недвижимостью Тульской области
Сочинение 8 Предложений Про Осень
Реферат: Строки в цивільному праві
Социально-педагогическая деятельность в России - Педагогика курсовая работа
Помилки у текстах телерадіомовлення - Иностранные языки и языкознание курсовая работа
Проблемы происхождения и развития Земли - Биология и естествознание контрольная работа