Rle сжатие онлайн. Тренажеры для изучения алгоритмов сжатия. Алгоритм сжатия lzw

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

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

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

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

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

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

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

Новости

Алгоритм RLE

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

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

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

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

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

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

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

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

Лицензия

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

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

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

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

Кодирование длин серий (англ. 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 заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

Как открыть RLE файлы

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

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

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

Программа(ы), умеющие открыть файл .RLE

Windows

Mac OS

Linux

Возможные проблемы с файлами в формате RLE

Отсутствие возможности открытия и работы с файлом RLE, совсем не должен значить, что мы не имеем установленного на своем компьютере соответствующего программного обеспечения. Могут выступать другие проблемы, которые также блокируют нам возможность работы с файлом Run Length Encoded Bitmap. Ниже находится список возможных проблем.

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

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

Как связать файл с установленной программой?

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

Есть ли универсальный метод открытия неизвестных файлов?

Многие файлы содержат данные в виде текста или чисел. Возможно, что во время открытия неизвестных файлов (напр. RLE) популярный в системе Windows простой редактор текста, которым является Notatnik позволит нам увидеть часть данных, закодированных в файле. Этот метод позволяет просмотреть содержимое многих файлов, однако не в такой форме, как программа, предназначенная для их обслуживания.

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

XnView - довольно мощная программа, сочетающая в себе множество функций по работе с изображениями. Это может быть и простой просмотр файлов, и их конвертирование, и незначительная обработка. Является кроссплатформенной, что позволяет использовать её практически в любой системе. Программа уникальна ещё и тем, что поддерживает около 400 различных форматов изображений, среди которых встречаются как самые используемые и популярные, так и нестандартные форматы. XnView может производить пакетную конвертацию изображений. Правда, сконвертировать их можно только в 50 форматов, но среди этих 50 форматов присутствуют все популярные расшир...

XnConvert – полезная утилита для конвертирования и первичной обработки фотографий и изображений. Работает с 400+ форматами. Поддерживает все популярные графические форматы. С помощью простых инструментов XnConvert можно регулировать яркость, гамму и контрастность. В приложении можно менять размер фотографий, накладывать фильтры и ряд популярных эффектов. Пользователь может добавлять водяные знаки и заниматься ретушью. При помощи приложения можно удалять мета-данные, обрезать файлы и вращать их. XnConvert поддерживает журнал, в котором пользователь увидит всю подробную информацию о своих недавних манипуляциях с изображениями.

IrfanView – бесплатный просмотрщик графических файлов, отличительными чертами которого является малый размер и функциональность. IrfanView поддерживает большое количество форматов, обладает понятным интерфейсом и необходимым набором функций. Так, с её помощью можно не только просматривать изображения, но и поворачивать их под любым углом, заниматься небольшим исправлением цветов, убирать эффект красных глаз с фотографий и т.п. Также, с помощью IrfanView можно делать скриншоты (как всего экрана, так и отдельных областей), выдирать значки и иконки из различных файлов, переименовывать файлы по заранее заданному шаблону, а...

Xlideit Image Viewer - маловесная и удобная утилита, созданная для облегчения редактирования изображений, фотографий. Приложение позволяет одновременно просматривать интересующие картинки и редактировать их. Встроенный редактор помогает корректировать размер, поворачивать изображения, создавать своё слайд-шоу. Также посредством программы можно обрезать картинки до нужных размеров, изменять их масштаб. Пользователь может изменять широкий спектр конфигурационных настроек под собственные нужды. Поддерживает полноэкранный режим, достаточно нажать F11 и режим будет запущен. Принцип работы Xlideit Image Viewer прост: достаточно загру...

Vintager - небольшая по размерам утилита, предназначенная для редактирования фотоснимков, в которой встроены несколько необходимых функций. С помощью программы можно не только менять фото, но и обрезать его, поворачивать и изменять пиксельный размер снимка. Также в Vintager встроена функция состаривания фотографии, что делает снимок старым. Из-за небольшого размера, установка программы занимает несколько секунд. Утилита отличается от других редакторов высокой скоростью работы и имеет комфортный вид интерфейса, благодаря чему отлично подойдет даже для начинающих пользователей. Меню настроек программы очень просто в использовании...

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

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

WildBit Viewer – программа для просмотра цифровых фотографий, отличающаяся обилием функций и возможностей. Так, например, в программе присутствует стандартный редактор эффектов, а также имеется возможность использовать готовое изображение в качестве фона для рабочего стола. Кроме этого, вы можете просматривать изображения в режиме слайд шоу, что удобно, если вы показываете свои фотографии кому-то и не хотите вручную их листать. В программе имеется более 70 эффектов перехода при показе слайд шоу. Ещё одна функция программы – отображение всех метаданных, а также переименование изображений. Поддерживается и пакетное переи...

Программное обеспечение, которое представляет собой набор специальных многофункциональных средств, предназначенных для проведения работы с разнообразными графическими файлами. Кроме того, поддерживает определенные аудио и видеофайлы. Здесь пользователям предоставляются возможности по просмотру цифровых фото, организации процессов их сортировки и хранения в пределах жесткого диска. Также поддерживается работа с файлами типа RAW. Удобная функция – возможность использования программы в качестве медиапроигрывателя. Есть возможность создания различных презентаций и их записи на диски. Имеется полный набор графических инструментов дл...

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

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

Задание:

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

Решение:

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

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

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