Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Архивация данных

Министерство образования Российской Федерации

ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина»

Институт военно-технического образования и безопасности

Кафедра защиты в чрезвычайных ситуациях

Курсовая работа по информатике на тему:

Архивация данных

Нормоконтроль

Научный руководитель

Курс, группа

Студент

_____________

Суханова Н.Г.

ВБ-120201

Томашова Л.А.

Екатеринбург

2013

Содержание

Введение

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

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

Задачи:

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

В данной работе будут приведены ответы на такие вопросы как:

«Что такое архивация?», «Какие существуют программы-архиваторы?» – и приведу пример способов архивации.

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

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

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

Архивация

Электронный архив

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

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

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

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

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

Создавать электронный архив документов следует по следующим причинам:

Удобство. С электронной копией документа намного проще работать: ее легко печатать, пересылать, копировать, а также использовать информацию из нее в других документах.
Простота поиска. В электронном архиве документов намного проще и быстрее найти нужную информацию.
Сохранность. В электронном архиве пользователь работает с копией документа, а потому в отличие от бумажного архива не имеет возможности повредить или утерять оригинал. Кроме того, бумага со временем изнашивается, чего нельзя сказать об электронной копии.
Доступное резервирование. Электронный архив документов дает 100%-ную гарантию, что в чрезвычайных ситуациях вся ваша информация останется в целости и сохранности. Резервирование электронного архива занимает немного времени и обходится намного дешевле, чем резервирование бумажных документов.
Экономия времени. Пользователю не нужно тратить время, чтобы идти на склад и долго искать определенный каталог и информацию в нем. В электронном архиве нужный документ можно найти за считанные минуты. Документы не вывозятся из их обычного места хранения, работы по скоростному сканированию производятся в непосредственной близости с архивным хранилищем заказчика. Изъятия документов из архива не происходит – документ лишь ненадолго покидает архивные полки.
Экономия денежных средств. Проведение массового сканирования документов архива силами специализированной внешней организации значительно дешевле (особенно для больших архивов) за счет исключения затрат на приобретение мощных сканеров и систем ввода, обучение персонала, выделение и оснащение рабочих помещений. Модель «заказчик-исполнитель» оптимальна в терминах цена/качество. На произведенный массив дается гарантия качества сканирования и точности индексации документов.

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

Архивация данных

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

Архивация — это подготовительная обработка (сбор, классификация, каталогизация, сжатие) данных для долгосрочного хранения или передачи их по сети.

Архивация файлов — перекодирование данных с целью уменьшения их объёма без значительных информационных потерь.

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

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

(Резервное копирование (англ. backup) — процесс создания копии данных на носителе (жёстком диске, дискете и т. д.), предназначенном для восстановления данных в оригинальном или новом месте их расположения в случае их повреждения или разрушения.)

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

В оглавлении архива для каждого содержащегося в нем файла хранится следующая информация:

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

Любой из архивов имеет свою шкалу степени сжатия. Чаще всего можно встретить следующую градацию методов сжатия:

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

Степень сжатия зависит от:

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

Степень сжатия характеризуется коэффициентом сжатия:

, (1)

где K_c – коэффициент сжатия;

V_c – объем сжатого файла;

V_и – объем исходного файла.

Файлы различных типов сжимаются по-разному. Например, коэффициент сжатия текстовых документов значительно выше, чем графических. Лучше всего архивируются графические файлы в формате .bmp, документы MS Office и Web-страницы.

Если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному.

Если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что, поскольку число различных сообщений длиной n бит составляет ровно 2n, число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит, их нельзя отличить. Но даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более чем на 1 бит. То есть сделать так, чтобы даже в самом худшем случае имело место неравенство:

K=So/(So+1)

Делается это следующим образом: если объём сжатых данных меньше объёма исходных, возвращаются сжатые данные путем добавления к ним «1», иначе возвращаем исходные данные, добавив к ним «0». Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п.), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:

средний (обычно по некоторому тестовому набору данных);
максимальный (случай наилучшего сжатия);
минимальный (случай наихудшего сжатия);

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

Для сжатия файлов используются программы архиваторы.

Архиваторы

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

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

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

Процесс сжатия файлов называется архивированием. Процесс восстановления сжатых файлов – разархивированием.

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

распространителям. Большинство программ-архиваторов позволяют

создавать многотомные архивы различной размерности. Такого рода

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

распространенных программ-архиваторов можно назвать ARJ, PKZIP, LHA,

PKPAK, PAK, ZIP, RAR, WinZIP и WinRAR.

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

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

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

Сжатие данных обычно происходит значительно медленнее, чем обратная операция.

Характеристики архиваторов:

по степени сжатия;
по скорости сжатия.

Характеристики архиваторов – обратно зависимые величины. То есть, чем больше скорость сжатия, тем меньше степень сжатия, и наоборот.

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

Программные и аппаратные средства

Алгоритмы сжатия

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

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

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

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

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

Сжатие без потерь

Сжатие способом кодирования серий (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 является достаточно низкая степень сжатия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

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

Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву и обычно называется LZ-compression.

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

Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем.

Экспериментальным путем установлено, что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP - 8-ми, а ARJ - 16-килобайтный.

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

В случае, если такая подстрока не найдена, в выходной поток просто копируется очередной символ входного потока.

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

Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице (length + distance).

Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмана или арифметическое кодирование).

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

Перечень программ сжатия с кратким указанием алгоритмов их работы

PKPAK 3.61:

Метод Packed – алгоритм RLE.

Метод Crunched – алгоритм LZW.

Метод Squashed – двухпроходное статическое кодирование Хаффмана.

PKZIP 1.10:

Метод Shrinked – модифицированный алгоритм LZW с частичной очисткой словаря и переменной длиной кода.

Метод Imploded – модифицированный алгоритм Лемпеля-Зива и

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

LHArc:

Алгоритм Лемпеля-Зива и динамическое кодирование Хаффмана.

LHA:

Алгоритм Лемпеля-Зива и статическое кодирование Хаффмана.

ARJ:

Алгоритм Лемпеля-Зива и оригинальный метод кодирования.

Алгоритмы сжатия с потерями

Сжатие графики

Растровые изображения представляют собой двумерный массив чисел - пикселей, а изображения можно подразделить на две группы: с палитрой и без нее. У первых в пикселе хранится число – индекс в некотором одномерном векторе цветов, называемом палитрой (из 16 и 256 цветов).

Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого. При использовании некой системы цветопредставления каждый пиксель является структурой, полями которой являются компоненты цвета (например, RGB и CMYK).

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

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

Фрактальное сжатие

Так называемые фрактальные алгоритмы обеспечивают степень сжатия изображения до 1:2000 (формат FIF). Кроме того, при разархивации изображение можно масштабировать. Уникальность этих алгоритмов в том, что изображение не дробится на квадраты и учитывается не близость цветов в локальной области, а подобие разных по размеру областей изображения.

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

Архивация данных 📙 Курсовая → 🆔 28502