работа по теме: «Программа для разархивации файла, созданного по алгоритму rle» (стр. 2 из 2)

Программы, осуществляющие упаковку и распаковку файлов, называются программами – архиваторами.

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

1.1. Основные виды программ-архиваторов

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

ARJ, PKPAK, LHA, ICE, HYPER, ZIP, РАК, ZOO, EXPAND, разработанные за рубежом, а также AIN и RAR, разработанные в России. Обычно упаковка и распаковка файлов выполняются одной и той же программой, но в некоторых случаях это осуществляется разными программами, например, программа РКZIР производит упаковку файлов, a PKUNZIP - распаковку файлов.

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

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

Самораспаковывающийся архив получил название SFX - архив (SelF - eXtracting). Архивы такого типа в MS DOS обычно создаются в форме .ЕХЕ - файла.

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

Программа EXPAND, входящая в состав утилит операционной системы MS DOS и оболочки Windows, применяется для распаковки файлов программных продуктов, поставляемых фирмой Microsoft.

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

1.2. Способы управления программой - архиватором

Управление программой - архиватором осуществляется одним из двух способов:

─ с помощью командной строки, в которой формируется команда запуска, содержащая имя программы - архиватора, команду управления и ключи ее настройки, а также имена архивного и исходного файлов; подобное управление характерно для архиваторов ARJ, AIN, ZIP, РАК, LHA и др.;

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

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

1. АЛГОРИТМ АРХИВАЦИИ RLE

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

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

1 1 1 1 2 2 3 4 4 4

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

В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

2.1. Алгоритм декомпрессии

Алгоритм декомпрессии выглядит так:

Initialization(...);

do {

byte = ImageFile.ReadNextByte();

if(является счетчиком(byte)) {

counter = Low6bits(byte)+1;

value = ImageFile.ReadNextByte();

for(i=1 to counter)

DecompressedFile.WriteByte(value)

}

else {

DecompressedFile.WriteByte(byte)

} while(ImageFile.EOF());

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмем в 32 раза.

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

Данный алгоритм реализован в формате PCX.

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

Коэффициенты компрессии: 32, 2, 0,5. (Лучший, средний, худший коэффициенты)

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

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

1. РАЗРАБОТКА ПРОГРАММЫ ДЛЯ РАЗАРХИВАЦИИ ФАЙЛА, СОЗДАННОГО ПО АЛГОРИТМУ RLE

string str1 = textBox1.Text/*закодированая часть*/, str = "", ch = "", s = "", symb = "";

int i, k = 0, j;

for (i = 0; i < str1.Length; ) {

ch = str1.Substring(i, 1); // текущий символ i

k = 0;

s = "";

if ("0123456789".Contains(ch)) /* если символ ch является цифрой */ {

for (j = i; j < str1.Length; j++) {

if ("0123456789".Contains(str1.Substring(j, 1))) {

s += str1.Substring(j, 1);

} else break;

}

symb = str1.Substring(j, 1); // получаем букву

i = j + 1;

} else i++;

if (s.Length != 0) {

for (j = 0; j < Convert.ToInt32(s); j++) // декодирование буквы

str += symb;

} else

str += Convert.ToString(ch);

}

out_shifr.Text = str;

Декодирование закодированной строки выполняется путем поиска числа, которое является количеством повторений символа

и самого символа.

И так, получаем закодированную строку из текстового поля “textBox1” и записывает полученный текст в переменную “str1”.

При каждом проходе цикла, который выполняется, пока недостигнут последний символ, записываем в переменную “ch” текущий

символ и если он является цифрой, выполняем поиск цифр идущих друг за другом. Тем самым последовательность найденных

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

последовательности. В конце в строковую переменную “str” записываем букву столько раз, сколько равно значение числа.

ЗАКЛЮЧЕНИЕ

Существует множество алгоритмов архивирования и разархивирования. Каждый из них по своему хорош. Каждым из них лучше всего архивирует определённый тип данных.

Мы же рассматриваем алгоритм RLE, он имеет наиболее частое применение в архивировании графических типов данных.

СПИСОК ЛИТЕРАТУРЫ

1. Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видио».

1. Курс лекций "Основы информатики" Лекция 9 "Сжатие данных".

1. http://helloworld.ru - документация и книги по программированию.

1. Методическое пособие МГУ Д.С. Ватолин «Алгоритмы cжатия изображений»