Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
Реферат/Курсовая Архивация методом Лемпеля-Зива
Информация:
Тип работы: Реферат/Курсовая.
Добавлен: 25.04.13.
Год: 2012.
Страниц: 12.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Федеральное агентство по образованию
Тульский Государственный
педагогический университет
имени Л.Н.Толстого
Кафедра информатики
и вычислительной техники
Курсовая работа
Архивация методом Лемпеля-Зива
студентки 2 курса группы
В
специальности 351500 –
МОиАИС
Шутовой Анны Владимировны
Допускается к защите.
Научный руководитель:
Зав. кафедрой ___ Гордеев
Вячеслав Валерьевич
«___» ___ 2010 г.
Тула – 2010
ОГЛАВЛЕНИЕ
стр.
ВВЕДЕНИЕ
Архивация - это сжатие,
уплотнение, упаковка информации с
целью ее более рационального размещения на внешнем носителе
(диске или дискете). Архиваторы - это программы,
реализующие процесс архивации, позволяющие
создавать и распаковывать архивы.
Необходимость архивации связана
с резервным копированием информации
на диски и дискеты с целью
сохранения программного обеспечения
компьютера и защиты его от порчи и уничтожения
(умышленного, случайного или под действием
компьютерного вируса). Чтобы уменьшить
потери информации, следует иметь резервные
копии всех программ и файлов.
Программы-упаковщики (архиваторы) позволяют
за счет специальных методов сжатия
информации создавать копии файлов меньшего
размера и объединять копии нескольких
файлов в один архивный файл. Это даёт
возможность на дисках или дискетах разместить
больше информации, то есть повысить плотность
хранения информации на единицу объёма
носителя (дискеты или диска).
Кроме того, архивные файлы широко
используются для передачи информации
в Интернете и по электронной почте,
причем благодаря сжатию информации повышается
скорость её передачи. Это особенно важно,
если учесть, что быстродействие модема
и канала связи (телефонной линии) намного
меньше, чем процессора и жесткого диска.
Работа архиваторов основана на
том, что они находят в файлах
повторяющиеся участки и пробелы, помечают
их в архивном файле и затем при распаковке
восстанавливают по этим отметкам исходные
файлы.
Программы-упаковщики (или архиваторы)
позволяют помещать копии файлов
в архив и извлекать файлы из архива,
просматривать оглавление архива и тестировать
его целостность, удалять файлы, находящиеся
в архиве, и обновлять их, устанавливать
пароль при извлечении файлов из архива
и др. Разные программы архивации отличаются
форматом архивных файлов, скоростью работы,
степенью сжатия, набором услуг (полнотой
меню для пользователя), удобством пользования
(интерфейсом), наличием помощи, собственным
размером.
Ряд архиваторов позволяют
создавать многотомные архивы, самоизвлекающиеся
архивы, архивы, содержащие каталоги. Наиболее
популярны и широко используются следующие
архиваторы: ARJ, PKZIP/PKUNZIP, RAR, ACE, LHA, ICE, PAK, PKARC/PKXARC,
ZOO, HYPER, AIN.
Наиболее высокоэффективными
являются архиваторы RAR, ACE, AIN, ARJ.
Они обеспечивают наибольшую
степень сжатия информации и имеют
наиболее высокую скорость работы. Архиватор RAR имеет
удобный графический интерфейс и позволяет
читать текстовые файлы, находящиеся как
в rar-архиве, так и в arj и zip-архивах. Архиватор
AIN имеет русскоязычный интерфейс.
Глава 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) с помощью командной
строки MS DOS, в которой формируется
команда запуска, содержащая имя программы - архиватора,
команду управления и ключи ее настройки,
а также имена архивного и исходного файлов;
подобное управление характерно для архиваторов
ARJ, AIN, ZIP, РАК, LHA и др.;
2) с помощью встроенной
оболочки и диалоговых панелей,
появляющихся после запуска программы
и позволяющих вести управление
с использованием меню и функциональных
клавиш, что создает для пользователя
более комфортные условия работы. Такое управление
имеет программа - архиватор RAR.
Показатель - степени сжатия файлов
Необходимость архивации
связана с резервным копированием
информации на диски и дискеты
с целью сохранения программного
обеспечения компьютера и защиты его от порчи и уничтожения (умышленного,
случайного или под действием компьютерного
вируса). Чтобы уменьшить потери информации,
следует иметь резервные копии всех программ
и файлов.
Архивация - это сжатие,
уплотнение, упаковка информации с
целью ее более рационального размещения на внешнем
носителе (диске или дискете) в виде так
называемых архивных файлов.
Архивный файл - это
специальным образом организованный
файл, содержащий в себе один или
несколько файлов в сжатом или
несжатом виде и служебную информацию об именах файлов, дате и времени
их создания или модификации, размерах
и т.п.
Сжатие информации в
архивных файлах производится за счет
устранения избыточности различными способами,
например за счет упрощения кодов, исключения
из них постоянных битов или представления повторяющихся
символов или повторяющейся последовательности
символов в виде коэффициента повторения
и соответствующих символов. Алгоритмы
подобного сжатия информации реализованы
в специальных программах-архиватора
(наиболее известные из которых arj/arjfolder,
pkzip/pkunzip/winzi , rar/winrar) применяются определенные
Сжиматься могут как один, так и несколько
файлов, которые в сжатом виде помещаются
в так называемый архивный файл или архив.
Целью упаковки файлов обычно
являются обеспечение более компактного размещения информации
на диске, сокращение времени и соответственно
стоимости передачи информации по каналам
связи в компьютерных сетях. Поэтому основным
показателем эффективности той или иной
программы-архиватора является степень
сжатия файлов.
Степень сжатия файлов характеризуется
коэффициентом Кс, определяемым как
отношение объема сжатого файла Vc к объему
исходного файла Vо, выраженное в процентах
(в некоторых источниках используется
обратное соотношение):
Кс=(Vc/Vo)*100%
Степень сжатия зависит от используемой
программы, метода сжатия и типа исходного
файла.
Наиболее хорошо сжимаются файлы
графических образов, текстовые
файлы и файлы данных, для которых
коэффициент сжатия может достигать
5 - 40%, меньше сжимаются файлы исполняемых
программ и загрузочных модулей Кс = 60
- 90%. Почти не сжимаются архивные файлы.
Это нетрудно объяснить, если знать, что
большинство программ-архиваторов используют
для сжатия варианты алгоритма LZ77 (Лемпеля-Зива),
суть которого заключается в особом кодировании
повторяющихся последовательностей байт
(читай - символов). Частота встречаемости
таких повторов наиболее высока в текстах
и точечной графике и практически сведена
к нулю в архивах.
Кроме того, программы для архивации
все же различаются реализациями
алгоритмов сжатия, что соответственно
влияет на степень сжатия.
В некоторые программы-архиваторы
дополнительно включаются средства,
направленные на уменьшение коэффициента
сжатия Кс. Так в программе WinRAR реализован
механизм непрерывного (solid) архивирования,
при использовании которого может быть
достигнута на 10 - 50% более высокая степень
сжатия, чем дают обычные методы, особенно
если упаковывается значительное количество
небольших файлов однотипного содержания.
Сжатие файлов при архивации
При работе на персональном компьютере довольно часто
возникает необходимость уменьшить размер
файла с целью экономии места на диске.
Например, требуется перенести файлы с
одного компьютера на другой на дискетах.
Или нужно переслать большой файл по электронной
почте - уменьшив его размер, можно сэкономить
и время и деньги. Лучшее решение в таких
случаях создать так называемый архивный
файл, или, проще говоря, архив. Это единый
файл, в который для компактного хранения
информации помещены в сжатом виде один
или несколько исходных файлов.
Как известно, подавляющее большинство
современных форматов записи данных
содержат их в виде, удобном для быстрого
манипулирования, для удобного прочтения
пользователями. При этом данные занимают
объем больший, чем это действительно
требуется для их хранения. Алгоритмы,
которые устраняют избыточность записи
данных, называются алгоритмами сжатия
данных, или алгоритмами архивации. В настоящее
время существует огромное множество
программ для сжатия данных, основанных
на нескольких основных способах.
Все алгоритмы сжатия данных делятся
на:
1) алгоритмы сжатия без потерь,
при использовании которых данные
на приемной восстанавливаются без
малейших изменений;
2)алгоритмы сжатия с потерями,
которые удаляют из потока
данных информацию, незначительно
влияющую на суть данных, либо вообще не
воспринимаемую человеком (такие алгоритмы
сейчас разработаны только для аудио-
и видео- изображений).
Преимущество отдается естественно,
первой группе алгоритмов.
Существует два основных метода
архивации без потерь:
алгоритм Хаффмана (англ. Huffman), ориентированный
на сжатие последовательностей байт, не
связанных между собой,
алгоритм Лемпеля-Зива (англ. Lempel, Ziv),
ориентированный на сжатие любых
видов текстов, то есть использующий факт
неоднократного повторения "слов"
- последовательностей байт.
Практически все популярные программы
архивации без потерь
(ARJ, RAR, ZIP и т.п.) используют объединение
этих двух методов - алгоритм LZH.
Алгоритм Хаффмана. Алгоритм основан
на том факте, что некоторые символы
из стандартного 256-символьного набора
в произвольном тексте могут встречаться
чаще среднего периода повтора, а другие,
соответственно, - реже. Следовательно,
если $+o записи распространенных символов
использовать короткие последовательности
бит, длиной меньше 8, а для записи редких
символов - длинные, то суммарный объем
файла уменьшится.
Алгоритм Лемпеля-Зива. Классический
алгоритм Лемпеля-Зива -
LZ77, названный так по
году своего опубликования, предельно
прост. Он формулируется следующим образом : <если в прошедшем
ранее выходном потоке уже встречалась подобная
последовательность байт, причем запись
о ее длине и смещении от текущей позиции
короче чем сама эта последовательность,
то в выходной файл записывается ссылка
(смещение, длина), а не сама последовательность&g ;.
Так фраза <КОЛОКОЛ_ОКОЛО_КО ОКОЛЬНИ>
закодируется как <КОЛО(-4,3)_(-5,4 О_(-14,7)ЬНИ>.
Глава 2. АЛГОРИТМЫ АРХИВАЦИИ ДАННЫХ
Сжатие информации - проблема,
имеющая достаточно давнюю историю,
гораздо более давнюю, нежели история развития вычислительной
техники, которая (история) обычно шла
параллельно с историей развития проблемы
кодирования и шифровки информации.
Все алгоритмы сжатия
оперируют входным потоком информации,
минимальной единицей которой является
бит, а максимальной - несколько бит, байт
или несколько байт.
Целью процесса сжатия, как
правило, есть получение более компактного
выходного потока информационных единиц
из некоторого изначально некомпактного
входного потока при помощи некоторого
их преобразования.
Основными техническими
характеристиками процессов сжатия
и результатов их работы являются:
степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.
Все способы сжатия можно разделить на
две категории: обратимое и необратимое
сжатие.
Под необратимым сжатием
подразумевают такое преобразование
входного потока данных, при котором
выходной поток, основанный на определенном
формате информации, представляет, с некоторой точки зрения, достаточно
похожий по внешним характеристикам на
входной поток объект, однако отличается
от него объемом.
Степень сходства входного
и выходного потоков определяется
степенью соответствия некоторых свойств
объекта (т.е. сжатой и несжатой информации в соответствии с
некоторым определенным форматом данных),
представляемого данным потоком информации.
Такие подходы и алгоритмы
используются для сжатия, например
данных растровых графических файлов
с низкой степенью повторяемости
байтов в потоке. При таком подходе используется
свойство структуры формата графического
файла и возможность представить графическую
картинку приблизительно схожую по качеству
отображения (для восприятия человеческим
глазом) несколькими (а точнее n) способами.
Поэтому, кроме степени или величины сжатия,
в таких алгоритмах возникает понятие
качества, т.к. исходное изображение в
процессе сжатия изменяется, то под качеством
можно понимать степень соответствия
исходного и результирующего изображения,
оцениваемая субъективно, исходя из формата
информации. Для графических файлов такое
соответствие определяется визуально,
хотя имеются и соответствующие интеллектуальные
алгоритмы и программы. Необратимое сжатие
невозможно применять в областях, в которых
необходимо иметь точное соответствие
информационной структуры входного и
выходного потоков. Данный подход реализован
в популярных форматах представления
видео и фото информации, известных как
JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.
Обратимое сжатие всегда
приводит к снижению объема выходного потока информации
без изменения его информативности, т.е.
- без потери информационной структуры.
Более того, из выходного потока, при помощи
восстанавливающего или декомпрессирующего
алгоритма, можно получить входной, а процесс
восстановления называется декомпрессией
или распаковкой и только после процесса
распаковки данные пригодны для обработки
в соответствии с их внутренним форматом.
Перейдем теперь
непосредственно к алгоритмическим
особенностям обратимых алгоритмов
и рассмотрим важнейшие теоретические подходы
к сжатию данных, связанные с реализацией
кодирующих систем и способы сжатия информации.
Сжатие способом кодирования серий (RLE)
Наиболее известный
простой подход и алгоритм сжатия
информации обратимым путем - это
кодирование серий последовательностей (Run
Length Encoding - RLE).
Суть методов данного
подхода состоит в замене цепочек
или серий повторяющихся байтов
или их последовательностей на один
кодирующий байт и счетчик числа
их повторений.
Например:
44 44 44 11 11 11 11 11 01 33 FF 22 22 - исходная последовательность
03 44 04 11 00 03 01 03 FF 02 22 - сжатая последовательность
Первый байт указывает
сколько раз нужно повторить
следующий байт
Если первый байт равен
00, то затем идет счетчик, показывающий
сколько за ним следует неповторяющихся данных.
Данные методы, как
правило, достаточно эффективны для
сжатия растровых графических изображений
(BMP, PCX, TIF, GIF), т.к. последние содержат
достаточно много длинных серий
повторяющихся последовательностей байтов.
Недостатком метода RLE является достаточно
низкая степень сжатия.
Алгоритм Хаффмана
Сжимая файл по алгоритму
Хаффмана первое что мы должны сделать
- это необходимо прочитать файл
полностью и подсчитать сколько
раз встречается каждый символ из
расширенного набора ASCII.
Если мы будем
учитывать все 256 символов, то
для нас не будет разницы
в сжатии текстового и EXE файла.
После подсчета
частоты вхождения каждого символа,
необходимо просмотреть таблицу
кодов ASCII и сформировать бинарное
дерево.
Пример:
Мы имеем файл длинной в 100 байт и имеющий 6 различных
символов в себе . Мы подсчитали вхождение
каждого из символов в файл и получили
следующее :
Теперь мы берем эти
числа и будем называть их частотой
вхождения для каждого символа.
Мы возьмем из последней
таблицы 2 символа с наименьшей частотой.
В нашем случае это D (5) и како и т.д.................
