Алгоритм Хаффмана (Huffman) - сжатие данных без потерь.

Учебная программа сжатия информации (данных) без потерь.

Суть его можно изложить так:
Считаем количество вхождений каждого символа в исходный текст. Для наиболее часто встречающихся символов назначаем сочетание бит (код) меньшего размера, а по мере уменьшения встречаемости символов в тексте их код будет более длинным.

Для автоматизации подсчета встречаемости символов и оптимизации назначения кода используется специальный математический аппарат:

  • создание очереди символов (сортированного списка)
  • создание очереди узлов дерева (каждый символ - это листок, т.е. конечный узел)
  • создание дерева Хаффмана
  • создание таблицы Хаффмана

Для выполнения задачи кодирования используется таблица Хаффмана, а для декодирования - дерево Хаффмана.

Задание:

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

Решение:

Учебная программа - работа алгоритма Хаффмана (Huffman) сжатия (кодирования) данных

По органам управления на форме все понятно. Одна кнопка вызывает «метод сжатия» 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 .


Условия получения кода?    Показать?






C++ Builder 6.0 - работа алгоритма Хаффмана (Huffman) сжатия (кодирования) данных

А это еще одна версия программы, демонстрирующая алгоритм Хаффмана, но написанная на С++ Borland Builder 6.0

Изменяя текст в первом окне и щелкнув кнопку «Сжатие», Вы увидите произошедшие изменения в частотах символов (окно 5… можете пересчитать, если не верите…), в Таблице Хаффмана (окно2), сжатом тексте (окно 3), последовательности битов сжатого текста (окно 4).

В процессе восстановления текста исходными данными будут являться последовательность битов и значения частот символов… По частотам символов строится дерево Хаффмана и с его помощью из последовательности битов получается первичный текст.

Чтобы убедиться, что программа честно работает с последовательностью битов, можете стереть в четверном окне (сжатый текст в битах), например, первые пять символов (00100). Из таблицы Хаффмана видно, что так (00100) кодируется символ заглавной буквы «Т». Щелкайте кнопку «Восстановление» и в шестом окне видите результат – начальная буква «Т» исчезла... Так же можно удалять любой другой символ или дописывать новые, использую 0 и 1 в соответствии с таблицей Хаффмана…., но если вы хоть один раз ошибётесь… (в разряде или цифре), получите значительные искажения…

скачать exe-файл для тестирования

Другие примеры на тему «Шифрование, Кодирование и/или Сжатие Информации»

Другие примеры на языках «C»,«C++»,«C#»




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

исходный код на заказ. orenstudent.ru Автоматизация документов MS Office. orenstudent.ru исходный код на заказ. orenstudent.ru Помогите найти и устранить ошибку в исходном коде программы. orenstudent.ru Skype-консультирование по программированию
Скайп-консультации

Акция !!!
Весь код по 49 руб


требуются
школьники!


и СТУДЕНТЫ!
Кому не плевать
на деньги!
Сайт помощи студентам по программированию и информатике