Анализ трудоемкости алгоритмов

СОДЕРЖАНИЕ Введение

1. Решение задачи

2. Программная реализация

3. Алгоритм программы

4. Анализ трудоемкости алгоритма

Заключение

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

ВВЕДЕНИЕ

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

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

Идея метода — часто повторяющиеся символы нужно кодировать более короткими цепочками битов, чем цепочки редких символов. Строится двоичное дерево, листья соответствуют кодируемым символам, код символа представляется последовательностью значений ребер (эти значения в двоичном дереве суть 1 и 0), ведущих от корня к листу. Листья символов с высокой вероятностью появления находятся ближе к корню, чем листья маловероятных символов.

Это позволяет закодировать информацию (текст) двоичным кодом, причем объем информации будет минимален. Однако, для раскодирования текста нам потребуется алфавит, а именно «дерево Хаффмана», которое было построено при кодировании. Решение этой проблемы не включено в решение поставленной задачи, т.к. при небольших объемах информации алфавит может занимать большее количество памяти, чем сама информация (текст).

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

Программа выводит на частоту появления символа в тексте, код каждого символа после кодирования, и начальный текст в двоичном представлении.

Текст программы:

#include

#include

#include

#include

#include «Windows.h»

using namespace std;

class Tree

{

public:

char symbol;

int weight;

Tree* left_son;

Tree* right_son;

};

class Symbol_class

{

public:

char symbol; //символ

int amount; //его частота в тексте

vector code; //код символа

};

vector symbol_vector; //список всех символов

vector Tree_vector; //дерево Хаффмана

vector code; //бинарный код символов

Tree* main_tree; //указатель на корень дерева

void Find_this_symbol (char c) //поиск символов в списке

{

cout<

if (symbol_vector.size () ≠ 0)

{

for (int i=0;i

{

if (c==symbol_vector[i]. symbol) // если символ уже есть в списке

{

symbol_vector[i]. amount++;

//увеличиваем его частоту

return; //и выходим из функции

}

}

}

//Иначе добавляем в список новый символ

Symbol_class new_symbol;

new_symbol.symbol = c;

new_symbol.amount = 1;

symbol_vector.push_back (new_symbol);

}

void Read_File () //чтение файла

{

ifstream input_file («Input.txt»); //открываем файл

cout<<" Исходный текст: n" ;

while (! input_file.eof ())

{

char read_symbol = input_file.get (); //считываем файл посимвольно

if (!input_file.eof ())

Find_this_symbol (read_symbol); //ищем символ в списке

}

input_file.close (); //закрываем файл

}

void Create_Null_Nodes () //создаем пустые узлы для дерева

{

for (int i=0;i< symbol_vector.size ();i++)

{

Tree* tr = new Tree ;

tr->symbol = symbol_vector[i]. symbol;

tr->weight = symbol_vector[i]. amount;

tr->left_son = NULL;

tr->right_son = NULL;

Tree_vector.push_back (tr);

}

}

void Sort () //Сортировка эл-тов дерева по их весу

{

Tree* temp;

bool repeat;

do

{

repeat = false;

for (int i=1;i

{

if (Tree_vector[i]->weight>Tree_vector[i-1]->weight)

{

temp = Tree_vector[i];

Tree_vector[i] = Tree_vector[i-1];

Tree_vector[i-1] = temp;

repeat = true;

}

}

} while (repeat);

}

void Create_Tree () //создаем дерево Хаффмана

{

while (Tree_vector.size ()≠1) //до тех пока не останется один узел (корень)

{

int tr_size = Tree_vector.size ();

Sort (); //сортируем символы по их весу (частоте)

Tree* temp = new Tree; //создаем новый узел

//вес нового узла равен сумме весов двух эл-тов с наименьшим весом

temp->weight =

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];

Tree_vector.pop_back ();

temp->symbol = 0;

//вместо двух выброшенных эл-т записываем новый

Tree_vector.push_back (temp); }

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

Coding_Tree (a->right_son);

}

// если у узла нет сыновей, то:

char c = a->symbol;

for (int i=0;i< symbol_vector.size ();i++)

{

if (symbol_vector[i]. symbol == c) //ищем эл-т с найденным символом

{

symbol_vector[i]. code = code; //и присваиваем ему «собранный» код

}

}

if (code.size ()≠0)

code.pop_back (); //выбрасываем из строчки кода последний эл-т

}

void Print_Symbol_Codes () //вывести на экран коды символов

{

cout<<" nnКоды символов: n" ;

for (int i=0;i

{

cout<<<" [" <<<" ] = «;

for (int j=0;j

cout<

cout<

}

}

void Print_Coded_Text () //вывести на экран закодированный текст

{

ifstream input_file («Input.txt»);

cout<<" nТекст в двоичном представлении: n" ;

while (! input_file.eof ())

{

char read_symbol = input_file.get ();

if (!input_file.eof ())

{

for (int i=0;i

{

if (read_symbol == symbol_vector[i]. symbol)

{ for (int j=0;j

cout<

cout<<" «;

}

}

}

}

input_file.close ();

}

void Binary_Writing () //записать в бинарный файл

{

ifstream input_file («Input.txt»);

ofstream output_file («Output.bin»);

int count=0; char buf=0;

while (! input_file.eof ())

{

char read_symbol = input_file.get ();

if (!input_file.eof ())

{

for (int i=0;i

{

if (read_symbol == symbol_vector[i]. symbol)

{

for (int j=0;j

{

buf = buf | symbol_vector[i]. code[j]<<(7-count);

count++;

if (count==8)

{ count=0;

output_file<

buf=0; }

}

}

}

}

}

output_file.close ();

input_file.close ();

}

int main (int argc, char *argv[])

{

SetConsoleCP (1251);

SetConsoleOutputCP (1251);

Read_File ();

Create_Null_Nodes ();

Create_Tree ();

Coding_Tree (main_tree);

Print_Symbol_Codes ();

Print_Coded_Text ();

Binary_Writing ();

getchar ();

return 0;

}

3. Алгоритм программы Сопоставим алгоритм Хаффмана и код программы.

Шаг 1.

В исходном тексте необходимо посчитать частоту появления каждого символа (иначе, вес). Функция Read () считывает файл побайтово. В ней вызывается функция Find_this_symbol () принимающая считанный символ. Она ищет его в векторе символов (symbol_vector) и увеличивает параметр amount (вес или частота) на 1, или если не находит то добавляет этот элемент в вектор.

Шаг 2.

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

Далее вызывается функция Create_Tree (). В ней сначала вызывается функция Sort (), сортирующая элементы дерева (Tree_vector) в соответствии с частотой символов (их весом), по убыванию. После этого выбрасывается два элемента с минимальным весом из конца вектора и заменяется новым элементом, вес которого равен сумме весов этих двух элементов. Также создается связь между двумя «сыновьями» и «родителем». Цикл повторяется до тех пор, пока не останется один элемент — корень. Таким образом строится дерево Хаффмана.

Шаг 3.

Теперь, чтобы получить код для каждого символа, нужно пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1 — если направо. Таким способом мы получим код для каждого символа. Эта часть алгоритма выполняется в функции Coding_Tree (). Это рекурсивная функция. Код накапливается в векторе code и если найден узел без «сыновей», то элементу присваивается «накопленный» при обходе код. После этого последний символ из code выбрасывается и функция рекурсивно повторяется. Таким образом, мы кодируем дерево Хаффмана.

На этом алгоритм кодирования заканчивается. Программа выводим на экран закодированный текст. Раскодирование текста, как упоминалось, не предусмотрено, но это несложно сделать, если записать структуру vector Tree_vector в отдельный файл и потом считать, т.к. в ней хранятся коды всех элементов.

4. Анализ трудоемкости алгоритма При нахождении вычислительной сложности (анализе трудоемкости) алгоритма за 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!» и Л. Н. Толстого «Война и Мир».