Работа со сжатыми данными архивирование реферат

Обновлено: 02.07.2024

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных.

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

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

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

1. Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

2. Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

3. Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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

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

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

· JPEG - для графических данных;

· MPG - для для видеоданных;

· MP3 - для аудиоданных.

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

· GIF, TIFF - для графических данных;

· AVI - для видеоданных;

· ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

· алгоритм RLE (Run Length Encoding);

· алгоритмы группы KWE(KeyWord Encoding);

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

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

где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

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

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке.

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

Алгоритм Хаффмана

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

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

Пусть задан текст, в котором бурва 'А' входит 10 раз, буква 'В' - 8 раз, 'С'- 6 раз , 'D' - 5 раз, 'Е' и 'F' - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Символ	Частота вхождения	Битовый код
A
B
C
D
E
F

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Общие сведения об архивации файлов, её методы и цели. Алгоритмы Хаффмана, Лемпеля-Зива. Отличительные особенности программ-архиваторов: WinZip, WinRar, WinAce. Факторы, влияющие на эффективность процесса архивации. Упаковка файлов с помощью мастера.

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	15.06.2016
Размер файла	460,6 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Министерство сельского хозяйства Российской Федерации

Забайкальский аграрный институт - филиал ФГБОУ ВО

На тему: Архивация данных. Архиваторы

Выполнила: студентка 1-го курса

Проверил: Колосова О.Е

Введение

архивация упаковка хаффман

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

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

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

В ходе написания данной курсовой работы я использую знания, приобретенные на занятиях информатики, по использованию программ пакета Microsoft Office XP: Microsoft Word, Microsoft Excel, Microsoft Access.

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

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

Microsoft Access - система управления базами данных, входящая в Microsoft Office, позволяющая создавать базы данных, а также обеспечивать обработку (сортировку) и поиск данных.

Архивация данных (на примере программы WinRaR)

Постановка задачи. Написать реферат по заданной теме на 12 - 15 печатных листах. В реферате предусмотреть использование маркированного и нумерованного списков, вставку специального символа, вставку сноски, рисунка, оформление одного из абзацев в виде двух колонок.

Общие сведения об архивации файлов

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

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

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

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

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

Степень сжатия файлов характеризуется коэффициентом К_с, определяемым как отношение объема сжатого файла V_c к объему исходного файла V_о, выраженное в процентах:

Архивация (упаковка) - помещение (загрузка) исходных файлов в архивный файл в сжатом или не сжатом виде.

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

Методы архивирования

Существует два основных метода архивации:

Алгоритм Хаффмана. Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, - реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 1 байта, а для записи редких символов - более длинные, то суммарный объем файла уменьшится. Например буквы а,о,е,и - встречаются очень часто в русском тексте, объем каждой буквы равен 1 байт (8 бит), их можно заменить на цифры 0,1,2,3, которые можно разместить в 2-х битах. Т.е. коэффициент сжатия будет равен 25%.

Цели архивации

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

· Высвобождения места на жестком диске компьютера.

· Сокращения объема файлов, пересылаемых по электронной почте.

· Размещение данных на едином носители.

· Размещение 1 объемного файла на нескольких носителях, когда он не помещается на 1 носитель.

· Распаковка сжатых файлов.

Программы - архиваторы

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

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

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

WinZip, версия 8.0 пожалуй самый известный архиватор. Это наиболее популярный архиватор, используемый в Интернете. Часто является бесплатным или входит еще в какую - нибудь программу в качестве бесплатного бонуса. Начиная с версии ME (Millenium Edition), WinZip входит даже в систему Windows. Кроме того, существует немало модификаций архиватора WinZip, таких как zip - magic, 7 - zip, g - zip и т.п., различных по эффективности сжатия.

WinAce 2.0 - свежая версия старого архиватора, пополнившаяся очень интересными функциями и новым алгоритмом сжатия. Этот архиватор использует самый большой размер словаря для архивирования (4 Мб), что во многом объясняет его высокие результаты.

Различных архиваторов существует немало. Эффективность того или иного архиватора зависит от нескольких факторов:

1. Содержимого сжимаемого файла (текстовый, графический, звуковой).

2. От того, какая программа выбрана в качестве архиватора.

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

Типы архивных файлов

В файловой системе компьютера архивные файлы имеют строго заданный тип (расширение). Так, наиболее часто встречающиеся архивы имеют тип: ZIP, RAR, ARJ.

Кроме них на компьютерах используются архивы: CAB, LZH, TAR, GZ, UUE, BZ2, ISO и т.д.

Упаковка файлов

Рассмотрим работу с архиватором WinRaR. Упаковать файл можно тремя различными способами.

· При помощи мастера упаковки WinRaR.

· При помощи контекстного меню Windows, если вы встроили WinRaR в оболочку.

· Непосредственно в самой программе WinRaR, без помощи мастера, щелкнув мышью по кнопке Добавить или воспользовавшись контекстным меню самой программы WinRaR.

Рассмотрим все три способа.

Упаковка файлов с помощью мастера

Ш Щелкните мышью по кнопке Мастер на экране появится первый диалог Мастера (рис. 1.1).

Рис.1.1 Первый диалог Мастер: Выбор действий

Ш Чтобы выполнить упаковку, щелкните мышью на переключатель Создать новый архив, затем - на кнопке Далее.

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

Рис. 1.2. Диалог Выберете файлы, которые нужно добавить

Ш Выберете в рабочем поле диалога папку или файл, который будете упаковывать, - выделите их. Щелкните мышью по кнопке ОК.

Рис.1.3. Диалог Выбор названия для будущего архива

Ш На экране появится диалог Мастер: Выбор архива, как показано на рис. 1.3. В поле ввода Имя архива введите название будущего архива.

Ш Щелкните мышью по кнопке Далее. На экране появится диалог Мастер: Параметры архивации, как показано на Рис. 1.4. В этом окне можно сделать определенные настройки архивации, установить флажки в соответствующих полях.

Рис. 1.4. Диалог Мастер: Параметры архивации

Ш Щелкните мышью по кнопке Готово, запустив тем самым процесс упаковки.

После слов Создание архива в название диалога отображается название будущего файла (Рис. 1.5). Архивный файл расположится в том же месте, где находилась исходная папка.

Упаковка файлов из контекстного меню Windows

Заархивируем текстовый файл, созданный ранее в Microsoft Word. Если вы при установки архиватора выбрали Встроить WinRaR в оболочку, можно поступать так:

Ш Перейти к файлу на диске при помощи проводника Windows.

Ш Щелкните правой кнопкой мыши на файле.

Ш Щелкните мышью в контекстном меню на строке Добавить в архив

Ш В возникшем окне (Рис. 1.6) щелкните мышью на кнопке ОК.

Рис. 1.6. Диалог Имя и параметры архива

Упаковка файлов из самой программы WinRaR

Упаковка из самой программы WinRaR предоставляет больше возможностей, чем в предыдущих двух способах. В данном способе можно реализовать настройки программы наиболее полно. Заархивируем для начала текстовый файл, созданный ране в Microsoft Word.

Ш Откройте WinRaR.

Ш В файловом окне выделите файл для упаковки, затем щелкните на кнопке Добавить. На экране появится диалог Имя и параметры архива с открытой вкладкой Общие (Рис.1.6.)

Ш Щелкните мышью по кнопке ОК. Файл архива будет создан в том же самом месте, где располагались исходные файлы.

Упаковка непосредственно из программы WinRaR в данном случае почти ничем не отличается от упаковки из контекстного меню Windows.

Только в последнем случае пришлось запускать вначале программу WinRaR, а в первом она запускалась автоматически.

Профили архивации

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

· Профиль по умолчанию - ничего не изменится, до тех пор пака вам не захочется изменить сам профиль по умолчанию.

· Прикрепление к e - mail - наиболее оптимальный для создания архива, который будет, затем, отправлен по электронной почте.

· Резервная копия выбранных файлов - оптимальные для создания архива с важными для вас файлами.

· Тома размером 1,44 Мб - архивируемый файл будет при необходимости автоматически разбит на несколько файлов (их называют томами) размером 1,44 Мб - так чтобы каждый из них уместился на стандартной дискете.

· Zip - архив (низкая степень сжатия) - выберете его если хотите создать архив в формате zip.

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

Ш После этого откройте вкладку Общие, затем щелкните на кнопке Профили и в возникшем контекстном меню - на строке Сохранить текущие параметре как новый профиль. На экране возникает диалог Параметры профиля, как показано на Рис. 1.7.

Ш В поле ввода Имя профиля впечатайте желаемое название - после сохранения оно будет отображаться в списке при щелчке на кнопке Профили.

Ш Сохранить профиль.

Настройки на вкладке Общие. В группе элементов управления Формат архива выберете, в каком формате вы хотите создать архив - zip или RaR.

Ш Щелкните по нужному переключателю.

Ш В одноименном открывающемся списке выберете Метод сжатия. Помните, что скорость и степень сжатия связаны друг с другом обратной связью. Чем выше скорость, тем ниже степень сжатия и наоборот.

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

Параметры архивации

· Удалить файлы после упаковки. При установке флажка исходные файлы будут удалены сразу после упаковки - останется только созданный архив.

· При установке флажка Создать SFX - архив - будет создан самораспаковывающийся архив (SFX - аббревиатура от слов Self Extractor - самораспаковывающийся), замечательная возможность предоставляемая архиватором.

Рис. 1.8. Диалог Самораспаковывающийся архив

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

· Добавить информацию для восстановления - при установке флажка в архив запишется информация для восстановления, которая будет использована в случае повреждения архива. При этом размер архива незначительно возрастет (по умолчанию на 1% от исходного текста).

Чтобы сделать это, выполните такие шаги.

· Установите флажок Добавить информацию для восстановления.

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

· Протестировать файл после упаковки - если вы установите флажок, то после упаковки архив будет проверен на ошибки. Если вы одновременно с этим флажком установите также флажок Удалить файл после упаковки, то исходные файлы будут удалены только в том случае, если вновь созданный архив не будет содержать ошибок.

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

Создание многотомного самораспаковывающегося архива

Новый файл сохранен в папке Мои документы.

Ш Найдите файл и щелкните на нем правой кнопкой мыши. В открывшимся меню щелкните мышью по строке добавить в архив. Появится диалог Имя и параметры архива.

После этого нужно сделать необходимые настройки архиватора.

Ш На вкладке Общие щелкните на кнопке открывающегося списка Разделить на тома размером (в байтах) и выберите пункт Автоопределение.

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

Ш Откройте дискету - щелкните мышью по кнопке обзор, откроется диалог Поиск архива. Щелкните мышью на открывающемся списке Папка, затем когда список откроется, на строке Диск 3,5 А и далее на кнопке Открыть.

В результате в поле ввода Имя архива будет указан путь к дискете.

Ш Щелкните ОК. На экране появится диалог Создание архива.

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

Многотомный самораспаковывающийся архив создан и записан на дискеты.

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

Так же как и упаковку, распаковку файлов можно проводить, по крайней мере, тремя способами:

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

Министерство образования РФ.

Новгородский государственный университет имени Ярослава Мудрого.

Кафедра математики и информатики.

Лабораторная работа №6

Винник Людмила Ивановна

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

2. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ

2.1 Применение архиваторов

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

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

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

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

2.2 Понятие процесса архивации файлов

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

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

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

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

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

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

Степень сжатия зависит от используемой программы, метода сжатия и типа исходного файла. Наиболее хорошо сжимаются файлы графических образов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5 - 40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей — 60 - 90%. Почти не сжимаются архивные файлы. Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия.

Архивация (упаковка) — помещение (загрузка) исходных файлов в архивный файл в сжатом или несжатом виде. Разархивация (распаковка) — процесс восстановления файлов из архива точно в таком виде, какой они имели до загрузки в архив. При распаковке файлы извлекаются из архива и помещаются на диск или в оперативную память;

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

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

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

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

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

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

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

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

Основными техническими характеристиками процессов сжатия и результатов их работы являются:

* степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

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

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

2.3. Алгоритмы архивации данных

Все способы сжатия можно разделить на две категории: обратимое (сжатие без потерь) и необратимое сжатие.

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

Такие подходы и алгоритмы используются для сжатия, например данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.

Обратимое сжатие всегда приводит к снижению объема выходного потока информации без изменения его информативности, т.е. - без потери информационной структуры.

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

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

2.3. 1 Алгоритмы сжатия без потерь

2.3.1.1. Сжатие способом кодирования серий (RLE)

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE).

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

44 44 44 11 11 11 11 11 01 33 FF 22 22 - исходная последовательность

03 44 05 11 01 01 01 33 01 FF 02 22 - сжатая последовательность

Первый байт указывает сколько раз нужно повторить следующий байт

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

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.

Недостатком метода RLE является достаточно низкая степень сжатия.

2.3.1.2 Алгоритм Хаффмана

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

Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе . Мы подсчитали вхождение каждого из символов в файл и получили следующее :

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

Мы возьмем из последней таблицы 2 символа с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов ( B и E ).

Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.

Теперь когда наше дерево создано, мы можем кодировать файл . Мы должны всегда начинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу . Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

A = 0100 ( 4 бита )

D = 0101 ( 4 бита )

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

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

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

Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби.

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

Пусть алфавит состоит из двух символов: a и b с вероятностями соответственно 0,75 и 0,25.

Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0; 0,75) и [0,75; 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из интервала [0, 1) а пустому слову соответствует весь интервал [0, 1). После получения каждого следующего символа интервал уменьшается с выбором той его части, которая соответствует новому символу. Кодом цепочки является интервал, выделенный после обработки всех ее символов, точнее, двоичная запись любой точки из этого интервала, а длина полученного интервала пропорциональна вероятности появления кодируемой цепочки.

Применим данный алгоритм для цепочки "aaba":

Границы интервала вычисляются так берется расстояние внутри интервала (0,5625-0,421875=0,140625), делится на частоты [0; 0,10546875) и [0,10546875; 1) и находятся новые границы [0,421875; 0,52734375) и [0,52734375; 0,5625).

В качестве кода можно взять любое число из интервала, полученного на шаге 4, например, 0,43.

Алгоритм декодирования работает аналогично кодирующему. На входе 0,43 и идет разбиение интервала.

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

2.3.1.4 Алгоритм Лемпеля – Зива - Велча (Lempel-Ziv-Welch - LZW)

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

Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования.

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

Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе (сразу после t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе.

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

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

Вложенные файлы: 1 файл

Архивация и сжатие файлов.docx

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Уральский федеральный университет

Высшая школа экономики и менеджмента

Архивация и сжатие файлов

Руководитель Лалов А. А.

Нормоконтроль Лалов А. А.

ЭМ-133201: Юрташкина А. А.

Дата защиты ____________

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Уральский федеральный университет

по курсовой работе

Студент группы ЭМ – 133201 специальность Бизнес и менеджмент в энергетике и наукоемких отраслях.

Фамилия Имя Отчество Юрташкина Анастасия Александровна

Руководитель курсовой работы Лалов А. А.

Срок работы с 2013 годапо 2013 года

Архивация и сжатие файлов

2. Содержание работы (Архивация и сжатие файлов: назначение, способы и программы)

3. Особые дополнительные сведения

______________________________ ______________________________ ____________

4. План выполнения курсовой работы

Наименование элементов курсовой работы

Отметка о выполнении

Раздел 1. Архивация и сжатие файлов

Раздел 2. Примеры алгоритма архивации и сжатия информации c применением различных программных средств.

Список использованных источников

Курсоваяработазакончена
Оценкаработы
Руководитель__________________ ____________

ВВЕДЕНИЕ

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

Производительность компьютеров и размер оперативной памяти и жесткого диска постоянно увеличиваются. Однако объемы данных, которые необходимо сохранить, растут гораздо быстрее. Еще недавно казалось, что диск в 300-500 гигабайт надежно решит проблему нехватки дискового пространства. Однако появляются новые, очень требовательные к аппаратным ресурсам программы. Размеры же мультимедийных файлов, которые хотелось бы сохранить, превышают все разумные пределы. В результате оказывается, что жесткий диск полон и перед пользователем встает задача хоть чуть-чуть освободить его.

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

Цель: Познакомиться с программами по архивированию файлов и научиться применять знания на практике.

РАЗДЕЛ 1. АРХИВАЦИЯ И СЖАТИЕ ФАЙЛОВ: НАЗНАЧЕНИЯ, СПОСОБЫ И ПРОГРАММЫ.

1.1 Понятие процесса архивации файлов

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

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

Степень сжатия файлов характеризуетсякоэффициентом К с, определяемым как отношение объема сжатого файла Vc к объему исходного файла VQ, выраженное в процентах: Кс=Vc IVQ*100. Степ ень сжатия зависит от используемой программы, метода сжатия и типа исходного файла.

1.2 Назначение программ архиваторов.

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

1.3 Методы сжатия компьютерных файлов

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

Кодирование длин серий (RLE - сокращение от run-lengthencoding - кодирование длин серий)

Метод, в котором последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. В качестве самостоятельного метода применяется, например, в графическом формате BMP.

Словарный метод(LZ - сокращение от LempelZiv - имена авторов)

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

Основным параметром словарного метода является размер словаря. Чем больше словарь, тем больше эффективность

Энтропийный метод (Huffman - кодирование Хаффмена, Arithmeticcoding - арифметическое кодирование)

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

Метод контекстного моделирования (CM - сокращение от contextmodeling - контекстное моделирование)

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

PPM (PPM - PredictionbyPartialMatching - предсказание по частичному совпадению)

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

Предварительные преобразования или фильтрация

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

Метод сортировки блока данных (BWT - сокращение от BurrowsWheelerTransform - по имени авторов)

Это особый вид или группа преобразований, в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части. Основным параметром является размер блока, который подвергается сортировке. Для распаковки данных необходимо проделать почти те же действия, что и при упаковке. Поэтому скорость и требования к оперативной памяти почти одинаковы. Архиваторы, которые используют данный метод, обычно показывают высокую скорость и степень сжатия для текстовых данных.

1.4 Программы архиваторы

компьютерный файл сжатие архив

Следует различать собственно программу-архиватор, формат архивов и методы сжатия. Даже один и тот же метод сжатия может иметь варианты реализации. Например, существует более десятка программ-архиваторов, которые могут создавать архивы в формате ZIP. В свою очередь данные в формате ZIP могут быть сжаты различными методами: Deflate, Deflate64, BZip2. Метод Deflate имеет несколько реализаций с разной скоростью и степенью сжатия. С помощью этого метода архиватор 7-zip позволяет создавать архивы в формате ZIP и 7Z.

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

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

Сжатие некоторых файлов и целых директорий;
Создание самораспаковывающихся (SFX) архивов. То есть для распаковки архива программа-архиватор не требуется;
Изменение содержимого архива;
Шифрование содержимого архива;
Информация для восстановления архива при частичном повреждении и возможность восстановления поврежденных архивов;
Разбивка архива на несколько частей или томов;
Консольная версия программы для работы из командной строки;
Графическая (GUI) версия программы.

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

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

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

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

Читайте также: