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

Реферат по теме:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Студента

БАП1301

Рулько М.А

2.

 

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

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

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

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

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

 

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

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

Том-это составная часть многотомного архива.

 

 

 

 

 

 

 

3.

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

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

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

Алгоритм Лемпеля-Зива. Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования. Он формулируется следующим образом: «если в более раннем тексте уже встречалась подобная последовательность байт, то в архивный файл записывается только ссылка на эту последовательность (смещение, длина), а не сам текст». Так фраза “КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ” [24]закодируется в последовательность “КОЛО(-4,3)_О(-6,4)_(-7,7)ЬНИ” [13]. Коэффициент сжатия - 54%. Аналогично сжимается изображение. Большие области одного цвета заменяются на ссылку: (цвет, длина).

Все методы сжатия данных делятся на два основных класса:

• Сжатие без потерь (см. стр. 4)
• Сжатие с потерями (см. стр. 5)

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

 

 

 

 

4.

 

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

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

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

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG, используют только сжатие без потерь; тогда как другие (TIFF, MNG) или GIF могут использовать сжатие, как с потерями, так и без.

Техника сжатия без потерь

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

00 → 0

01 → 10

10 → 110

11 → 111

В таком случае шестнадцать битов

00 01 00 00 11 10 00 00

будут преобразованы  в тринадцать битов

0 10 0 0 111 110 0 0

Такая подстановка является префиксным кодом, то есть обладает такой особенностью: если мы запишем сжатую строку без пробелов, мы всё равно сможем расставить в ней пробелы — а значит, восстановить исходную последовательность. Наиболее известным префиксным кодом является код Хаффмана.

 

5.

 

Сжатие данных с потерями

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

Типы сжатия с потерями

Существуют две основных схемы сжатия с потерями:

• В трансформирующих кодеках фреймы изображений или звука обычно трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными методами.
• В предсказывающих кодеках предыдущие и/или последующие отсчеты данных используются для того, чтобы предсказать текущий отсчет изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется.

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

Сжатие с потерями против сжатия без потерь

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

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

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

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

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

Недостатки

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.

Коэффициент сжатия

Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть:

где k — коэффициент сжатия, S_o — объём исходных данных, а S_c — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;
• если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

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

Допустимость потерь

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

8.

 

В их числе:

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

Системные требования алгоритмов

Различные алгоритмы  могут требовать различного количества ресурсов вычислительной системы, на которых  они реализованы:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

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

Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления.

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

 

 

 

9.