Алгоритм кодирования Хаффмана, разработанный через несколько лет после алгоритма Шеннона-Фано, тоже обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью, именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:
1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;
2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;
3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;
4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;
5. На основе построенного дерева каждому символу алфавита присваивается префиксный код;
6. Сообщение кодируется полученными кодами.
Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:
Рисунок 2.
Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.
2. Разработка консольного приложения справочной системы основных ключевых слов С++ с примерами.
Цель курсовой работы достигнута – консольное приложение справочной системы ключевых слов C++ является готовым программным продуктом, но при этом предоставляется возможность совершенствования данного компьютерного приложения.
Список используемой литературы
1. Сайт: https://xreferat.com/33/3655-1-yazyki-programmirovaniya.html - «Языки программирования».
2. Сайт: https://itandlife.ru/programming/cpp/alfavit-identifikatory-klyuchevye-slova-i-konstanty-c/ - «Алфавит языка программирования C++».
3. Сайт: https://msdn.microsoft.com/ru-ru/library - «Библиотеки языка программирования C++».
4. Сайт:https://ru.wikipedia.org/wiki/Стандартная_библиотека_языка_C%2B%2B – «Стандартные библиотеки языка программирования С++».
5. Сайт: https://msdn.microsoft.com/ru-ru/library/2e6a4at9.aspx - «Ключевые слова языка программирования С++».
6. Сайт: https://entropiya-blog.ru/etapy-proektirovaniya-spravochnoj-sistemy.html - «Этапы проектирования справочной системы»
7. Сайт:https://programminglang.com/ru/comp_programming/meyers/1/j66.html - «Использование istreambuf_iterator».
8. Сайт: https://ravesli.com/uroki-cpp/ - «Уроки по программированию на языке C++»
9. Сайт: https://www.draw.io – «Создание блок-схем к программе»
Приложение
Листинг программы.
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <conio.h>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "Russian");
ifstream txt("C:\\Help.txt");
string file_text{ istreambuf_iterator<char>(txt),
istreambuf_iterator<char>() };
string ent_word;
cout << "\n Чтобы получить справку по ключевому слову языка C++,\n введите интересующее вас слово, ознакомившись со списком поддерживаемых слов.\n";
;
cout << " Для того, чтобы получить список поддерживаемых слов, введите команду <keywords>.\n";
cout << " Для получения информации о программе и авторе введите команду <about>.\n";
cout << " Для выхода из программы введите команду <exit> или закройте консольное приложение, \n нажав на крестик в правом верхнем углу.\n\n";
cout << "\tДля начала работы нажмите Enter\n";
_getch();
while (ent_word!= "exit")
{ cout << " Введите ключевое слово или справочную команду: ";
cin >> ent_word;
system("cls");
if (ent_word == "exit")
{
exit(0);
}
ent_word = "[" + ent_word + "]";
int metka = 0;
metka = file_text.find(ent_word);
if (metka!= -1)
{
for (int i = 0; i < file_text.size(); i++)
{
if (file_text.at(metka + ent_word.size() + i + 2) == '$')
{
break;
}
else
{
cout << file_text.at(metka + ent_word.size() + i + 2);
}
}
}
else
{
cout << "Извините, но такого слова нет в списке." << endl;
}
cout << endl;
}
return 0;
}