Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

СПОСОБЫ СЖАТИЯ И АРХИВАЦИИ ИНФОРМАЦИИ

Prezintaciya
by

Maxim Vorobey

on 1 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of СПОСОБЫ СЖАТИЯ И АРХИВАЦИИ ИНФОРМАЦИИ

СПОСОБЫ СЖАТИЯ И АРХИВАЦИИ ИНФОРМАЦИИ СПОСОБЫ СЖАТИЯ И АРХИВАЦИИ ИНФОРМАЦИИ Проблема, тесно связанная с моделями представления информации, - сжатие информации.
При архивировании и передаче по каналам связи объем информации является основным параметром. Поэтому модели представления дополняются процедурами сжатия, т.е. плотной упаковкой информации.
Разработаны и применяются два типа алгоритмов сжатия:
1.сжатие с изменением структуры данных (оно происходит без потери данных)
2.сжатие с частичной потерей данных.
Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы (Хаффмена и Лемпеля-Зива). Алгоритмы второго типа не позволяют полностью восстановить оригинал и применяются для хранения графики или звука; для текстов, чисел или программ они неприменимы.
Сжатие без потерь Сжатие – это кодирование с уменьшением объема данных и возможностью однозначного декодирования. Обратный процесс – декодирование – называется разжатие. Другие названия: компрессия/декомпрессия, упаковка\распаковка. Эффективность алгоритма сжатия зависит не только от степени сжатия (отношение длины несжатых данных к длине соответствующих им сжатых данных), но и скорости сжатия и разжатия, объема памяти, необходимого для работы алгоритмов и т.д. На практике выделяют следующие два вида компрессии данных.
1. Сжатие без потерь (lossless compression) – собственно сжатие в смысле приведенного выше определения.
2. Сжатие с потерями (lossy compression) – процесс, состоящий из двух этапов:
Выделение сохраняемой части информации в зависимости от цели сжатия и особенностей приемника и источника;
Собственно сжатие без потерь.
АЛГОРИТМЫ СЖАТИЯ В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые – длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины. Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника: элемент , вероятность появления которого равняется выгоднее всего представлять бит. Если при кодировании размер элементарных кодов в точности получается равным , то длина кода будет минимальной из всех возможных способов алфавитного кодирования и равна энтропии Сжатие всегда осуществляется за счет устранения статистической избыточности в представлении информации. Компрессор не может сжать любой файл. Размер некоторых файлов уменьшается, а остальных остается неизменным или увеличивается МЕТОДЫ СЖАТИЯ БЕЗ ПОТЕРЬ Алгоритмы Зива-Лемпела (LZ-методы) СПОСОБЫ СЖАТИЯ И АРХИВАЦИИ ИНФОРМАЦИИ Коды Хаффмана (Huffman Coding) или коды с минимальной избыточностью Кодирование длин повторов, Run Length Encoding (RLE) Характеристики: степени сжатия – от 1 до 8, средняя – 1,5, не увеличивает размер файла (не считая таблицы перекодировки). Один из наиболее старых методов сжатия, идея метода состоит в замене идущих подряд одинаковых символов (бит или байт) парой (количество, символ). В основном используется для кодирования растровых изображений. ХАРАКТЕРИСТИКА: степень сжатия от 0,5 до 32. Реализации LZ77, LZ78, LZW и LZH. Относятся к словарным методам сжатия, т.е. сообщение кодируется не побуквенно (алфавитное кодирование), а по словам. Характеристики LZ78: степень сжатия в зависимости от данных, обычна 2-3, алгоритмы универсальны, но лучше всего подходят для сжатия текстов, рисованных картинок или других однородных данных. Применение LZ-методы: практически все известные архиваторы (программы WinRar, WinZip, форматы файлов rar, zip, arj, cad, ace и т.д.); графические файлы gif, tiff.
RLE: графические файлы jpeg, tiff.
Коды Хаффмана: jpeg, tiff.
Алгоритм LZ78 Идея словарного метода состоит в обнаружении во входном тексте повторяющихся цепочек байтов (слов), составлении таблицы таких слов (словаря). Все слова в исходном сообщении заменяются на код – номер слова в словаре. Алгоритм устроен так, что распаковщик, анализируя сжатые данные. Может построить копию исходной таблицы, и следовательно, ее не надо хранить вместе с сжатыми данными.
Рассмотрим подробнее алгоритм LZ78. Кодируемый текст разбивается на слова, каждое из которых кодируется парой (номер, символ). За один проход по тексту динамически строится словарь и сжатый текст. Изначально словарь содержит одно слово с номером 0 – пустое . На каждом шаге алгоритма считываются символы, начиная с текущего, и формируется слово наибольшей длины, совпадающее с каким-нибудь из уже имеющихся в словаре плюс еще один символ.
Рассмотрим, например, входную последовательность 010 001 011 001 010 001 101 011 00. На первом шаге рассматривается слово из одного символа 0, оно добавляется в словарь под номером 1, и кодируется в выходной последовательности (0,0), что означает слово из словаря под номером 0 (пустое слово) + символ 0. На втором шаге в словарь добавляется слово 1 под номером 2, имеющее код (1,0). На третьем шаге имеем совпадение с непустым словом в словаре 0, в словарь добавляется слово 00, имеющее код (1,0). И т.д. На шестом шаге мы уже закодировали последовательность 010001011, словарь имеет вид { ,0,1,00,01,011}, остался текст 0010100011. Максимальное совпадение с третьим словом словаря ‘00’. Данная последовательность вместе со следующим символом (здесь 1) кодируется парой чисел (номер совпадающего слова в словаре, следующий символ) (здесь (3,1)) и добавляется в словарь (теперь словарь имеет вид { ,0,1,00,01,011,001}. На следующем шаге считывается следующий за уже закодированными символ. И т.д. до конца входного текста.
В результате последовательности 010 001 011 001 010 001 101 011 00 соответствует словарь { , 0,1,00,01,011,001,010,0011,0101,10}, разбиение последовательности на слова и код
0 1 00 01 011 001 010 0011 0101 10 0
(0,0) (0,1) (1,0) (1,1) (4,1) (3,1) (4,0) (6,1) (7,1) (2,0) (0,0)
При декодировании одновременно строится словарь и сжатое сообщение.
Сжатие с потерями
АРИФМЕТИЧЕСКОЕ СЖАТИЕ
(ARIC, Arithmetic Coding) Характеристики: один из самых эффективных методов, степень сжатия от 1 до 8, т.е. не увеличивает размер данных в худшем случае, обеспечивает лучшую степень сжатия, чем алгоритм Хаффмана (в среднем 1-10%). Не является алфавитным кодированием. Весь кодируемый текст представляется в виде дроби из [0,1).
Дробь строится таким образом, чтобы текст был представлен как можно компактнее. Возьмем начальный интервал [0,1) и разобьем на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов. Пусть x=математика. Получим таблицу
Будем считать, что таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0,1). Он разбивается на диапазоны в соответствии с заданными частотами символов. В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считывается следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т.д.

ПРИМЕР Таким образом, окончательная длина интервала равна произведению вероятностей всех встретивших символов, а его начало зависит от порядка следования символов в потоке. Если обозначить диапазон символ c как
пока не конец слова
В качестве кода берется произвольное число, лежащее в полученном интервале Для последовательности x=”мате”, состоящей из 4 символов, можно взять y=0,339. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки. Дальше это число можно перевести в двоичную дробь и закодировать цифрами после запятой.
Рассмотрим работу алгоритма декомпрессии. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0,339, то первым символом может быть только М, так как только его диапазон включает это число. В качестве интервала берется диапазон М [0,3;0,5), разбивается на подинтервалы, среди которых находится содержащий 0,339. Это [0,3;0,36), соответствующий символу «А». Дальше разбивается в соответствии с таблицей этот интервал и т.д.
Архивация информации Средства архивации информации Иногда резервные копии информации приходится выполнять при общей ограниченности ресурсов размещения данных, например владельцам персональных компьютеров. В этих случаях используют программную архивацию. Архивация это слияние нескольких файлов и даже каталогов в единый файл — архив, одновременно с сокращением общего объема исходных файлов путем устранения избыточности, но без потерь информации, т. е. с возможностью точного восстановления исходных файлов. Действие большинства средств архивации основано на использовании алгоритмов сжатия, предложенных в 80-х гг. Абрахамом Лемпелем и Якобом Зивом. Наиболее известны и популярны следующие архивные форматы;

-ZIP, ARJ для операционных систем DOS. и Windows
-TAR для операционной системы Unix
-межплатформный формат JAR (Java ARchive)
-RAR (все время растет популярность этого нового формата, так как разработаны программы позволяющие использовать его в операционных системах DOS, Windows и Unix),

Пользователю следует лишь выбрать для себя подходящую программу, обеспечивающую работу с выбранным форматом, путем оценки ее характеристик – быстродействия, степени сжатия, совместимости с большим количеством форматов, удобности интерфейса, выбора операционной системы и т.д.. Список таких программ очень велик – PKZIP, PKUNZIP, ARJ, RAR, WinZip, WinArj, ZipMagic, WinRar и много других. Большинство из этих программ не надо специально покупать, так как они предлагаются как программы условно-бесплатные (Shareware) или свободного распространения (Freeware). Также очень важно установить постоянный график проведения таких работ по архивации данных или выполнять их после большого обновления данных.
Full transcript