Очень простой и понятный алгоритм сжатия информации.

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

Задание:

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

Решение:

Служебный байт должен начинать каждую цепочку (или серию) в архиве.
Поэтому старший бит служебного байта будет равен 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) ; //чтение служебного байта
и другие…

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

Цепочки из разных символов в архиве будут повторять все символы исходной цепочки и дополняться служебным байтом, поэтому сжатием в этом случае и не пахнет. И лучше, чтобы эта цепочка была длинной, чтобы служебный байт дал меньший процент приращения размера архива по сравнению с исходным текстом…

Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов - простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.

Характеристики алгоритма RLE:

Коэффициенты компрессии : Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты). Класс изображений : Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Симметричность: Примерно единица.

Характерные особенности : К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

Первый вариант алгоритма

Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение > уменьшает избыточность данных.

Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.

Второй вариант алгоритма

Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

29. Алгоритм сжатия lzw

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel , Ziv и Welch .

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк - 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

Характеристики алгоритма LZW: Коэффициенты компрессии : Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. Класс изображений : Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке. Симметричность : Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

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

Процесс сжатия выглядит достаточно просто. Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова.

Особенность LZW заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

Этот сайт больше не обновляется. Сайт К. Полякова «Преподавание, наука и жизнь» переехал по адресу kpolyakov.spb.ru . Новый адрес страницы, к которой вы обратились: Пожалуйста, обновите свои закладки. Через 5 секунд вы будете перенаправлены на новый сайт автоматически.

Сжатие данных

тренажеры для изучения алгоритмов сжатия

Что это такое?

Тренажёры «RLE » и «Huffman » предназначены для изучения темы «Сжатие данных» в школьном курсе информатики на профильном уровне. Тренажёры можно использовать:

для упаковки и распаковки текстовых строк;
для упаковки и распаковки файлов любого формата;
для анализа предельных возможностей сжатия файлов;
для сравнения эффективности алгоритмов сжатия.

Программы работают под управлением операционных систем линейки Windows на любых современных компьютерах.

Новости

Алгоритм RLE

Алгоритмы Хаффмана, Шеннона-Фано и LZW

В тренажёре «Huffman » реализованы два алгоритма побайтового сжатия данных: алгоритм Шеннона-Фано и Алгоритм Хаффмана . Оба этих алгоритма используют коды переменной длины: часто встречающийся символ кодируется двоичным кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона-Фано и Хаффмана — префиксные, то есть никакое кодовое слово не является началом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов. В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана обеспечивает минимальную избыточность, то есть минимальную длину кодовой последовательности при побайтном кодировании.

При кодировании с помощью алгоритма LZW строится таблица, в которой цепочкам символов ставятся в соответствие кодовые последовательности. Прелесть этого алгоритма состоит в том, что для декодирования не нужна никакая дополнительная информация, кроме закодированного текста: таблица строится прямо в процессе декодировки.

В тренажёре «Huffman » можно упаковывать и распаковывать с помощью алгоритмов Хаффмана, Шеннона-Фано и LZW строки текста, а также файлы любого формата.

После щелчка по кнопке (клавиша F4) текст, введенный в текстовом редакторе, сжимается. Сжатые данные показываются в нижней части окна программы в виде строки, содержащей двоичный код. В левой части показывается таблица кодов символов, использованная при сжатии.

Кнопки в верхней части окна предназначены для сжатия и распаковки файлов. Обратите внимание, что распаковываются только те файлы, которые сделаны в этой программе.

Кнопка Анализ файла позволяет определить для любого файла предельный теоретически достижимый коэффициент сжатия при побайтном кодировании.

Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите .

Лицензия

Программы являются бесплатными для некоммерческого использования. Исходные тексты программ не распространяются.

Программы поставляются «as is », то есть, автор не несет никакой ответственности за всевозможные последствия их использования, включая моральные и материальные потери, вывод оборудования из строя, физические и душевные травмы.

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

распространение неполных или измененных материалов;
включение материалов в сборники на любых носителях информации, распространяемые на коммерческой основе;
получение коммерческой выгоды от продажи или другого использования материалов.

Мы надеемся, что помогли Вам решить проблему с файлом RLE. Если Вы не знаете, где можно скачать приложение из нашего списка, нажмите на ссылку (это название программы) - Вы найдете более подробную информацию относительно места, откуда загрузить безопасную установочную версию необходимого приложения.

Посещение этой страницы должно помочь Вам ответить конкретно на эти, или похожие вопросы:

Как открыть файл с расширением RLE?
Как провести конвертирование файла RLE в другой формат?
Что такое расширение формата файлов RLE?
Какие программы обслуживают файл RLE?

Если после просмотра материалов на этой странице, Вы по-прежнему не получили удовлетворительного ответа на какой-либо из представленных выше вопросов, это значит что представленная здесь информация о файле RLE неполная. Свяжитесь с нами, используя контактный формуляр и напишите, какую информацию Вы не нашли.

Что еще может вызвать проблемы?

Поводов того, что Вы не можете открыть файл RLE может быть больше (не только отсутствие соответствующего приложения).
Во-первых - файл RLE может быть неправильно связан (несовместим) с установленным приложением для его обслуживания. В таком случае Вам необходимо самостоятельно изменить эту связь. С этой целью нажмите правую кнопку мышки на файле RLE, который Вы хотите редактировать, нажмите опцию "Открыть с помощью" а затем выберите из списка программу, которую Вы установили. После такого действия, проблемы с открытием файла RLE должны полностью исчезнуть.
Во вторых - файл, который Вы хотите открыть может быть просто поврежден. В таком случае лучше всего будет найти новую его версию, или скачать его повторно с того же источника (возможно по какому-то поводу в предыдущей сессии скачивание файла RLE не закончилось и он не может быть правильно открыт).

Вы хотите помочь?

Если у Вас есть дополнительная информация о расширение файла RLE мы будем признательны, если Вы поделитесь ею с пользователями нашего сайта. Воспользуйтесь формуляром, находящимся и отправьте нам свою информацию о файле RLE.

Чем открыть файл.RLE? Алгоритм сжатия rle.