Алгоритм 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 сжатия данных

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

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




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

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

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

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


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


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

Program code