Двойное сжатие: RLE + Huffman - сжатие данных без потерь.


Задание:

Написать программу сжатия текста, состоящего из символов уникода.
Для увеличения степени сжатия использовать последовательно алгоритмы RLE и Хаффмана (Haffman).
Оценить степень (%) сжатия для каждого случая.

Решение:

RLE (Run Length Encoding) очень простой и понятный алгоритм сжатия информации.

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

Служебный байт должен начинать каждую цепочку (или серию) в архиве.
Поэтому старший бит служебного байта будет равен 1 у цепочки из одинаковых символов и 0 у других цепочек.
В цепочке одинаковых символов может храниться от 2 до 129 символов, т.к. оставшиеся 7 бит служебного байта могут хранить число от 0 до 127.
В цепочке разных символов может храниться от 1 до 128 символов, т.к. оставшиеся 7 бит служебного байта могут хранить число от 0 до 127.
Например:

  • служебный байт 10000000 (в дополнительном коде -128) говорит о том, что это серия с одинаковыми символами и таких символов в серии всего 2.
  • служебный байт 10000011 (в дополнительном коде -125) говорит о том, что это серия с одинаковыми символами и таких символов в серии всего 5.
  • служебный байт 00000011 (в дополнительном коде 3) говорит о том, что это серия с разными символами и символов в серии всего 4.
  • служебный байт 01111111 (в дополнительном коде 127) говорит о том, что это серия с разными символами и символов в серии всего 128.

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

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

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

Учебная программа - алгоритм RLE + Huffman сжатия данных

Вот так выглядит обработчик события нажатия кнопки «Декомпрессия»:

Void Form1::button4_Click(System::Object^ sender, System::EventArgs^ e)    {

   if (textBox1->Text!="") {   //если сжатая строка есть
       rleOperac ^decompr=gcnew rleOperac();   //создаем объект класса (операцию RLE)
       textBox11->Text=decompr->RLE_decompress(textBox1->Text);
   //метод вернет разархивированную строку
   }
   //если сжатая строка отсутствует, то окно сообщения
   else { MessageBox::Show( "Отсутствует строка для восстановления после сжатия", "Внимание!!!",
   System::Windows::Forms::MessageBoxButtons::OK,System::Windows::Forms::MessageBoxIcon::Error );
    textBox11->Text="";
   }
}

В файлах RLE.h и RLE.cpp описаны классы rleOperac (предназначен для работы со строкой System::String^) и RLE_Auto (предназначен для работы с единственной серией (или цепочкой) символов).

Среди методов класса RLE_Auto есть:
public: System::Void Step(wchar_t s) ;    //очередной шаг для автомата Тьюринга
public: System::Void Check127(void) ;    //проверка от переполнения служебного байта
public: System::Char GetServise(void) ;   //получение служебного байта
public: System::Void ReadServise(System::Char serv) ;    //чтение служебного байта
и другие…
А класс rleOperac имеет всего три метода:
System::String ^ RLE_compress(System::String ^stringToCompress);    //кодирование по алгоритму RLE (сжатие)
System::String ^ RLE_ShowService(System::String ^stringToDecompress);    //преобразует служебные байты в строку цифр
System::String ^ RLE_decompress(System::String ^stringToDecompress);    //декодирование по алгоритму RLE (декомпрессия)

Работать с методами классов намного проще... не говоря уже про возможность повторного их (классов) использования…

А вот так выглядит обработчик события нажатия кнопки «Создание таблицы», создающий таблицу Хаффмана:

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»,«C++»,«C#»

Поделиться в соц сетях:




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

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

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

Акция !!!
исходный код комментарии цена минимальная


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


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

Program code