Двойное сжатие: 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) заключается в следующем:
Считается количество вхождений каждого символа в исходный текст. Наиболее часто встречающиеся символы обозначаются (кодируются) наименьшим сочетанием бит, а
по мере уменьшения частоты символов в тексте их код будет более длинным. Для автоматизации подсчета встречаемости символов
и оптимизации назначения кода используется специальный математический аппарат:
- создание очереди символов (сортированного списка)
- создание очереди узлов дерева (каждый символ - это листок, т.е. конечный узел)
- создание дерева Хаффмана
- создание таблицы Хаффмана
Для выполнения задачи кодирования используется таблица Хаффмана, а для декодирования - дерево Хаффмана.
Вот так выглядит обработчик события нажатия кнопки «Декомпрессия»:
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#»
Поделиться в соц сетях:
