}
}
}
}
}
}_file.close();_file.close();
}main (int argc, char *argv[])
{(1251);(1251);_File();_Null_Nodes();_Tree();_Tree(main_tree);_Symbol_Codes();_Coded_Text();_Writing();();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*> 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:
((N*log(N)) + O(N) = O(N*(log(N)+1)) = 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 мы последовательно вызываем все перечисленные функции, поэтому можем составить общую трудоемкость алгоритма как сумму сложностей этих функций:
(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 «Анализ трудоемкости алгоритмов» из курса «Математическая логика и теория алгоритмов».
.Статьи сайта habrahabr.ru «Оценка сложности алгоритмов» и «Метод Хаффмана на пальцах».
.Статьи портала Wikipedia на тему оценки сложностей алгоритмов, метода Хаффмана, методов сортировки массивов, двоичных деревьев и обходов этих деревьев.
.Статья сайта planetmath.org «Huffman's algorithm».
.Произведения русских писателей Ф.И.Тютчева «Silentium!» и Л.Н.Толстого «Война и Мир».