Алгоритм 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.
По органам управления на форме все понятно. Одна кнопка вызывает «метод сжатия» RLE_compress объекта класса rleOperac, а вторая обратный метод RLE_decompress (восстановление первоначального текста из архива).
Вот так выглядит обработчик события нажатия кнопки «Декомпрессия»:
Void Form1::button1_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 (методы перечислены выше), описан класс 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) ; //чтение служебного байта
и другие…
Работать с классами намного проще, не говоря уже про повторное их использование…
Цепочки из разных символов в архиве будут повторять все символы исходной цепочки и дополняться служебным байтом, поэтому сжатием в этом случае и не пахнет. И лучше, чтобы эта цепочка была длинной, чтобы служебный байт дал меньший процент приращения размера архива по сравнению с исходным текстом…
Таким образом, понятно, что не всякий текст будет сжиматься. Если нет длинных цепочек с одинаковыми символами, то, скорее всего, длина архива даже увеличится, по сравнению с исходной строкой (за счет введения служебных байтов).
скачать exe-файл для тестирования
Другие примеры на тему «Шифрование, Кодирование и/или Сжатие Информации»
Другие примеры на языках «C»,«C++»,«C#»
Поделиться в соц сетях: