Курсовая работа тема: Разработка Архиватора

Вид материала

Подобный материал:

КУРСОВАЯ РАБОТА

Тема:

Разработка Архиватора

Архангельск

2009

Разработка Архиватора 1

Введение 3

Основная часть 4

1.Цель разработки 4

2.Задачи разработки 4

3.Назначение разработки 4

4.Описание различных методов компрессии. 4

4.1. Арифметическое кодирование. 5

4.2. LZW сжатие 5

4.3. Групповое кодирование(RLE) 6

5.Аппаратные и технические средства, использованные при разработке. 7

6.Описание библиотеки ZLib. 8

7.Применение Программы 9

7.1.Сжатие файла. 9

7.2.Распаковка файла 10

8.Реализация компрессии/декомпрессии данных. 10

8.1.Компрессия 10

8.2.Декомпрессия 11

9.Сравнительный анализ архиваторов 13

Заключение 15

Список использованной литературы 16

Введение

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

Существует много всяких причин выделять ресурсы ЭВМ в расчете на сжатое представление, т.к. более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и за частую улучшить показатели ЭВМ.

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

Основная часть

1.Цель разработки

Цель данного курсового проекта разработка программы Архиватора.

2.Задачи разработки

Поиск различной информации по теме Сжатие данных.
Разбор различных алгоритмов компрессии.
Написание программы - архиватора.

3.Назначение разработки

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

4.Описание различных методов компрессии.

На сегодняшний день существует множество методов компрессии данных:

Арифметическое кодирование.
LZW сжатие
Расширяющегося префикса
Алгоритм Хаффмана
Групповое кодирование(RLE)
UUE – кодирование
Кодирование методом Шеннона-Фано

Рассмотрим несколько алгоритмов компрессии.

4.1. Арифметическое кодирование.

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

4.2. LZW сжатие

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

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

4.3. Групповое кодирование(RLE)

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение".

Одна из реализаций алгоритма такова: ищут наименнее часто встречающийся байт, называют его префиксом и делают замены цепочек одинаковых символов на тройки "префикс, счетчик, значение". Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару "префикс, 1" или "префикс, 2". Остается одна неиспользованная пара "префикс, 0", которую можно использовать как признак конца упакованных данных.

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode) .

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

5.Аппаратные и технические средства, использованные при разработке.

При разработке использовались:

Операционная система Windows XP SP3
Borland Delphi 7 Second Edition

Для нормальной работы программы требуется:

ОЗУ не менее 256 МБ
Не менее 2 Мб. на жестком диске
Операционная система MS-DOS или Windows (любой версии)

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

Программа тестировалась на компьютере:

Процессор Celeron 2.8 GHz
ОЗУ 1 ГБ
Операционная система Windows XP SP3.

6.Описание библиотеки ZLib.

ZLib — свободная кроссплатформенная библиотека для сжатия данных, Является обобщением алгоритма сжатия данных DEFLATE, используемого в их компрессоре данных gzip. Первая публичная версия 0.9, выпущена 1 мая 1995 года для использования вместе с библиотекой libpng. Распространяется под лицензией zlib.

ZLib является стандартной библиотекой Delphi начиная с 7 версии.

Тип: библиотека для сжатия данных

Разработчик: Jean-loup Gailly, Mark Adler

Написана на: C

ОС: кроссплатформенное ПО

Версия: 1.2.3 — 18 июля 2005

Лицензия: лицензия zlib
Сайт: ссылка скрыта

7.Применение Программы

Программа имеет интуитивно-понятный интерфейс.

После запуска программы пользователь видит основное окно программы.

7.1.Сжатие файла.

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

7.2.Распаковка файла

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

8.Реализация компрессии/декомпрессии данных.

8.1.Компрессия

input: =TFileStream.Create(EditFile.Text,fmOpenRead);

prefix:=ExtractFileExt(EditFile.Text);

if EditName.Text<>'' then begin

output:=TFileStream.Create(EditName.Text+prefix+'.Zlib',fmCreate)

end

else

begin

output:=TFileStream.Create(EditFile.Text+'.Zlib',fmCreate);

end;

CompresSstream:=TCompressionStream.Create(clMax,output);

try

repeat

bytesread:=input.Read(mainbuffer,buffer_size);

CompresSstream.Write(mainbuffer,bytesread);

until bytesread<1024;

except

CompresSstream.free;

input.Free;

output.Free;

end;

Из поля Edit получаем адрес исходного файла, плюс получаем расширение исходного файла.
Создаем файл-результат в директории исходного файла + расширение исходного файла + расширение ZLib.
Посредством команды CompresSstream:=TCompressionStream.Create(clMax,output) сжимаем исходный файл с максимальной степенью сжатия.
С помощью цикла repeat until пробегаем по всему исходному фалу
Очищаем память

8.2.Декомпрессия

outName:=ExtractFileName(EditFile.Text);

index:=length(outName);

delete(outName,art-4,index);

fullFilePath:= ExtractFilePath(EditFile.Text);

prefix:=ExtractFileExt(outName);

input:=TFileStream.Create(EditFile.Text,fmOpenRead);

if EditName.Text<>'' then output:=TFileStream.Create(fullFilePath+EditName.Text+prefix,fmCreate)

else

output:=TFileStream.Create(fullFilePath+outName,fmCreate);

decompressStream:=TDecompressionStream.Create(input);

try

repeat

bytesread:=decompressStream.Read(mainbuffer,buffer_size);

output.Write(mainbuffer,bytesread);

until bytesread<1024;

except

decompressStream.Free;

input.Free; output.Free; end;

Из поля Edit извлекаем Имя исходного файла
Находим длину имени файла и удаляем расширение ZLib
Извлекаем из поля Edit путь к директории исходного файла
Присваиваем новое имя файла или оставляем без изменений
Создаем файл-результат
Посредством команды decompressStream:=TDecompressionStream.Create(input) распаковываем файл.
С помощью цикла repeat until пробегаем по всему исходному фалу
Очищаем память

9.Сравнительный анализ архиваторов

Для сравнения степени сжатия данных был проведен сравнительный анализ самых распространенных архиваторов и нашей программы.

В анализе использовались следующие архиваторы:

7-Zip
WinRaR
WinAce
Наш архиватор в последствии Arxivator.

Анализ осуществлялся по следующим критериям:

процент сжатия
Затраченное время
Размер выходного файла

В качестве тестовых файлов были выбраны:

аудио файл размером 3,75 Мб.
Текстовый файл размером 154 Мб.

Таблица 1

Анализ компрессии аудио файла.

	7-Zip	WinRaR	WinAce	Arxivator
Затраченное время	4 сек.	4 сек.	6 сек	4 сек.
Процент сжатия	97 %	97 %	96 %	97 %
Размер выходного файла	3.67 Мб	3.67 Мб	3.68 Мб	3.67 Мб

Таблица 2

Анализ компрессии текстового файла.

	7-Zip	WinRaR	WinAce	Arxivator
Затраченное время	50 сек	27 сек.	29 сек.	17 сек.
Процент сжатия (приблизительно)	99 %	97 %	98 %	95 %
Размер выходного файла	24 кб.	526 кб.	157 кб.	807 кб.

Выводы.

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

Заключение

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

В итоге получили готовый программный продукт, соответствующий теме курсовой работы «Разработка архиватора».

Все цели и задачи поставленные в работе были выполнены.

Список использованной литературы

Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

ZLib – библиотека для сжатия общего назначения [Электронный ресурс]:Руководство по библиотеке ZLib –Режим доступа: ссылка скрыта

Википедия [Электронный ресурс]: Свободная энциклопедия – Режим доступа: ссылка скрыта

Сжатие данных [Электронный ресурс]: Крупнейший каталог ресурсов по сжатия данных – Режим доступа: ссылка скрыта

Библиотека алгоритмов [Электронный ресурс] – Режим доступа: http://algolist.manual.ru

Blog