Реферат на тему:


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...

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

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

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

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

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

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

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

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

Если при сжатии данных происходит изменение их содержания, то метод сжатия необратим, т.е. при восстановлении (разархивирования) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулируемыми потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео-и аудиоданные, а также графические данные. Методы сжатия с регулируемыми потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть: JPEG (Joint Photographic Experts Group) для графических данных; MPG - для для видеоданных; MP3 - для аудиоданных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия обратим. В этом случае из архива можно восстановить информацию полностью. Обратные методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графических данных; 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-строка. Когда считывается очередной символ входной последовательности данных, он добавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущую строку перестает отвечать какой-нибудь фразе словаря. В этот момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, состоящий из индекса совпадения и следующего за ним символа, нарушившего совпадение строк. Кроме того, новая фраза, состоящая из индекса совпадения и следующего за ним снмвола, добавляется в словарь. В следующий раз, когда эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает степень сжатия информации.

Алгоритм LZW построен вокруг таблицы фраз (словаря), которая отражает строки символов стиснуваного сообщения в

Загрузка...

Страницы: 1 2