Алгоритм Хаффмана (Huffman) - сжатие данных без потерь C++ Visual Studio
Учебная программа сжатия информации (данных) без потерь.
Суть его можно изложить так:
Считаем количество вхождений каждого символа в исходный текст. Для наиболее часто встречающихся символов назначаем сочетание бит (код) меньшего размера, а
по мере уменьшения встречаемости символов в тексте их код будет более длинным.
Для автоматизации подсчета встречаемости символов и оптимизации назначения кода используется специальный математический аппарат:
- создание очереди символов (сортированного списка)
- создание очереди узлов дерева (каждый символ - это листок, т.е. конечный узел)
- создание дерева Хаффмана
- создание таблицы Хаффмана
Для выполнения задачи кодирования используется таблица Хаффмана, а для декодирования - дерево Хаффмана.
Задание:
Написать программу сжатия текста, состоящего из символов уникода.
Представить сжатый текст в виде последовательности битов и в виде последовательности символов.
Решение:
По органам управления на форме все понятно. Одна кнопка вызывает «метод сжатия» Encode , а вторая обратный метод Decode (восстановление первоначального текста из архива).
Вот так выглядит обработчик события нажатия кнопки «Создание таблицы»:
Void Form1::button1_Click(System::Object^ sender, System::EventArgs^ e) {
if (textBox1->Text!="") {
//Строим дерево по строке для кодирования
codeTree = buildTree(textBox1->Text);
//Строим таблицу Хаффмана по этому дереву
codeTable = buildTable(codeTree);
//заполнение textBox4 для наглядности
textBox4->Text="";
hlNode *cur=codeTable->first;
while (cur!=NULL) {
String ^sym = ((wchar_t)(cur->symbol)).ToString();
String ^cod = gcnew String(cur->code);
textBox4->Text=" '"+sym+"' - "+cod+"\r\n"+textBox4->Text;
cur=cur->next;
}
}
else { MessageBox::Show( "Отсутствует строка для кодирования", "Внимание!!!",
System::Windows::Forms::MessageBoxButtons::OK,System::Windows::Forms::MessageBoxIcon::Error );
textBox4->Text="";
}
}
В файлах Huffman.h, Huffman.cpp, pQueue.h, pQueue.cpp содержатся все необходимые функции для обеспечения работы алгоритма.
htTree * buildTree(System::String ^inputString); //построение дерева по строке символов
и другие…
hlTable * buildTable(htTree *huffmanTree); //построение таблицы по дереву
System::String ^ Encode(hlTable *table, System::String ^stringToEncode); //кодирование по таблице и строке символов
System::String ^ Decode(htTree *tree, System::String ^stringToDecode); //декодирование по дереву и строке кода
Эта программа учебная и очень упрощена. Здесь не рассмативается вопрос передачи сжатой информации... Ведь надо понимать, что для передачи сжатой информации вместе с ней должна передаваться информация позволяющая декодировать ее в исходный текст. Это либо таблица, либо дерево, или хотя бы частоты встречаемости символов...
скачать exe-файл для тестирования
Имеется проект с точно таким же интерфейсом, но на C# Visual Studio 2012 .
Условия получения кода? Показать?
А это еще одна версия программы, демонстрирующая алгоритм Хаффмана, но написанная на С++ Borland Builder 6.0
Изменяя текст в первом окне и щелкнув кнопку «Сжатие», Вы увидите произошедшие изменения в частотах символов (окно 5… можете пересчитать, если не верите…), в Таблице Хаффмана (окно2), сжатом тексте (окно 3), последовательности битов сжатого текста (окно 4).
В процессе восстановления текста исходными данными будут являться последовательность битов и значения частот символов… По частотам символов строится дерево Хаффмана и с его помощью из последовательности битов получается первичный текст.
Чтобы убедиться, что программа честно работает с последовательностью битов, можете стереть в четверном окне (сжатый текст в битах), например, первые пять символов (00100). Из таблицы Хаффмана видно, что так (00100) кодируется символ заглавной буквы «Т». Щелкайте кнопку «Восстановление» и в шестом окне видите результат – начальная буква «Т» исчезла...
Так же можно удалять любой другой символ или дописывать новые, использую 0 и 1 в соответствии с таблицей Хаффмана…., но если вы хоть один раз ошибётесь… (в разряде или цифре), получите значительные искажения…
скачать exe-файл для тестирования
для Windows 10 скачать exe-файл для тестирования
Другие примеры на тему «Шифрование, Кодирование и/или Сжатие Информации»
Другие примеры на языках «C»,«C++»,«C#»
Поделиться в соц сетях: