Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. , Рябко Б.Я. , Witten I.H. , Rissanen J. , Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. и др.
Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации. Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт. Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются:
Степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
Скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
Качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.
Существует несколько различных подходов к проблеме сжатия информации. Одни имеют весьма сложную теоретическую математическую базу, другие основаны на свойствах информационного потока и алгоритмически достаточно просты. Любой способ подход и алгоритм, реализующий сжатие или компрессию данных, предназначен для снижения объема выходного потока информации в битах при помощи ее обратимого или необратимого преобразования. Поэтому, прежде всего, по критерию, связанному с характером или форматом данных, все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие.
Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации, в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например, данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.
Обратимое сжатие всегда приводит к снижению объема выходного потока информации без изменения его информативности, т.е. - без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой, и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом.
В обратимых алгоритмах кодирование как процесс можно рассматривать со статистической точки зрения, что еще более полезно, не только для построения алгоритмов сжатия, но и для оценки их эффективности. Для всех обратимых алгоритмов существует понятие стоимости кодирования. Под стоимостью кодирования понимается средняя длина кодового слова в битах. Избыточность кодирования равна разности между стоимостью и энтропией кодирования, а хороший алгоритм сжатия всегда должен минимизировать избыточность (напомним, что под энтропией информации понимают меру ее неупорядоченности.). Фундаментальная теорема Шеннона о кодировании информации говорит о том, что "стоимость кодирования всегда не меньше энтропии источника, хотя может быть сколь угодно близка к ней". Поэтому, для любого алгоритма, всегда имеется некоторый предел степени сжатия, определяемый энтропией входного потока.
Перейдем теперь непосредственно к алгоритмическим особенностям обратимых алгоритмов и рассмотрим важнейшие теоретические подходы к сжатию данных, связанные с реализацией кодирующих систем и способы сжатия информации.
Сжатие способом кодирования серий
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.
Сжатие без применения метода RLE
Процесс сжатия данных без применения метода RLE можно разбить на два этапа: моделирование (modelling) и, собственно, кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы.
Процесс кодирования и его методы
Под кодированием обычно понимают обработку потока символов (в нашем случае байтов или полубайтов) в некотором алфавите, причем частоты появления символов в потоке различны. Целью кодирования является преобразование этого потока в поток бит минимальной длины, что достигается уменьшением энтропии входного потока путем учета частот символов. Длина кода, представляющего символы из алфавита потока должна быть пропорциональна объему информации входного потока, а длина символов потока в битах может быть не кратна 8 и даже переменной. Если распределение вероятностей частот появления символов из алфавита входного потока известно, то можно построить модель оптимального кодирования. Однако, ввиду существования огромного числа различных форматов файлов задача значительно усложняется т.к. распределение частот символов данных заранее неизвестно. В таком случае, в общем виде, используются два подхода.
Первый заключается в просмотре входного потока и построении кодирования на основании собранной статистики (при этом требуется два прохода по файлу - один для просмотра и сбора статистической информации, второй - для кодирования, что несколько ограничивает сферу применения таких алгоритмов, т.к., таким образом, исключается возможность однопроходного кодирования "на лету", применяемого в телекоммуникационных системах, где и объем данных, подчас, не известен, а их повторная передача или разбор может занять неоправданно много времени). В таком случае, в выходной поток записывается статистическая схема использованного кодирования. Данный метод известен как статическое кодирование Хаффмена .
|
|
АРХИВАТОРЫ
Сжатие информации – это процесс преобразования информации, хранящейся в файле, путем уменьшения избыточности данных. Целью этого процесса является уменьшения обьема, занимемого данными.
Архивный файл – это специально созданный файл, содержащий в себе один или несколько файлов в сжатом виде.
Степень сжатия : K c =V c /V o *100%
K c – коэффициент сжатия, V c – объем сжатого файла, V o – исходный объем файла.
Степень сжатия зависит от:
1) используемой пограммы – архиватора,
2) метода сжатия,
3) типа исходного файла: текстового, графического, видео, звукового и т.д.
Программы, осуществляющие упаковку и распаковку файлов называются архиваторами. Наиболее распространенными являются: ARJ, ZIP, RAR. Расширение архивных файлов совпадает с названием использованного для их создания архиватора.
Архиваторы позволяют создавать самораспаковывающиеся архивные файлы, т.е. для их распаковки не требуется запуска программы-архиватора, т.к. они сами содержат программу распаковки. Эти архивы называются SFX-архивы
(SelF-eXtracting). Расширение таких файлов *.EXE.
Принципы сжатия информации
В любом тексте встречаются повторяющиеся символы. Возможно указать один символ и число повторений. Еще выше эффективность этого алгоритма применительно к графическим файлам. Если взглянуть на монитор, то можно видеть очень много повторяющихся точек одного цвета. На этом принципе сжатия информации основан формат графических файлов PCX. Современные архиваторы выделяют, не только повторяющиеся символы, но и цепочки символов, отдельные слова.
Если в тексте используются не все символы алфавита ПК, то для их кодирования можно использовать в место одного байта, 8-ми бит, меньше число. Этот принцип используется в телеграфном аппарате, где используются только русские заглавные буквы, для их представления достаточно 5 бит, что позволяет записать в два байта три символа.
3. В следующим принципе используется закономерность что в тексте буквы встречаются с разной частотой. Например в этом тексте пробел самый распространенный символ, очень часто встречаются символы «а», «и». Эти часто встречающиеся символы можно представлять короткой комбинацией битов, остальные символы возможно кодировать более длинной последовательностью. Например:
4. Физически ПК выделяет место для размещения файлов на диске по кластерам - блоками по 4 кБ. Меньше выделить невозможно. Например если файл имеет размер 8193 байта (8 кБ и 1 байт), физически он будет занимать 16 кБ или 16384 байта. Объединение группы файлов в один позволяет сэкономить на этих остатков. При упаковки маленьких файлов это дает большую экономию.
Итого, при отдельном размещении файлов не используются 6 кБ, что составляет 100% от содержания файлов. Во втором случае неиспользуемыми остается 2 кБ, 33%.
Архиватор zip
Запаковка файлов pkzip [ключи] <имя архива> [пути файлов]
Ключи: -rp архивация с подкаталогами с сохранением структуры
SPWD защита архива паролем (PWD)
A добавить файлы в архив
M переместить файлы в архив
V просмотр содержимого архива
Если производится архивация всех файлов каталога, то обязательно указывать маску *.*
Распаковка файлов pkunzip [ключи] <имя архива> [имена файлов]
Ключи: -d распаковка с подкаталогами с сохранением структуры
SPWD пароль архива (PWD)
Архиватор arj
arj <команда> [ключи] <имя архива> [имена файлов]
Для архиватора arj один файл выполняет операции и распаковки и запаковки.
Команды: a архивация
e распаковка без сохранения структуры каталогов
x распаковка с сохранением структуры
l просмотр содержимого архива
m переместить файлы в архив
d удалить файлы из архива
Ключи: -r упаковка с подкаталогами с сохранением структуры
V разбивка архива на тома с объемом vol(если указан)
размер для стандартных дискет (360, 720, 1200, 1440) указывается в килобайтах, размер нестандартных дискет указывается в байтах
V указывается при распаковке многотомного архива
GPWD пароль архива (PWD )
Запаковка файлов
Распаковка файлов
©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-08
Принципы сжатия информации
В основе любого способа сжатия информации лежит модель источника информации, или, более конкретно, модель избыточности. Иными словами для сжатия информации используются некоторые сведения о том, какого рода информация сжимается - не обладая никакми сведениями об информации нельзя сделать ровным счётом никаких предположений, какое преобразование позволит уменьшить объём сообщения. Эта информация используется в процессе сжатия и разжатия. Модель избыточности может также строиться или параметризоваться на этапе сжатия. Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспецифичные алгоритмы, применяемые для работы с хорошо определёнными и неизменными характеристиками. Подавляющая часть же достаточно универсальных алгоритмов являются в той или иной мере адаптивными.
Любой метод сжатия информации включает в себя два преобразования обратных друг другу:
- преобразование сжатия;
- преобразование расжатия.
Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.
Все методы сжатия делятся на два основных класса
- без потерь,
- с потерями.
Кардинальное различие между ними в том, что сжатие без потерь обеспечивает возможность точного восстановления исходного сообщения. Сжатие с потерями же позволяет получить только некоторое приближение исходного сообщения, то есть отличающееся от исходного, но в пределах некоторых заранее определённых погрешностей. Эти погрешности должны определяться другой моделью - моделью приёмника, определяющей, какие данные и с какой точностью представленные важны для получателя, а какие допустимо выбросить.
Характеристики алгоритмов сжатия и применимость
Коэффициент сжатия
Коэффициент сжатия - основная характеристика алгоритма сжатия, выражающая основное прикладное качество. Она определяется как отношение размера несжатых данных к сжатым, то есть:
k = S o /S c ,где k - коэффициент сжатия, S o - размер несжатых данных, а S c - размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:
- если k = 1, то алгоритм не производит сжатия, то есть получает выходное сообщение размером, равным входному;
- если k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.
Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон:Е:бит составляет ровно 2 n . Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n . Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.
Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон , μ-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:
- среднее (обычно по некоторому тестовому набора данных);
- максимальное (случай наилучшего сжатия);
- минимальное (случай наихудшего сжатия);
или каким либо другим. Коэффициент сжатия с потерями при этом сильно зависит от допустимой погрешности сжатия или его качества , которое обычно выступает как параметр алгоритма.
Допустимость потерь
Основным критерием различия между алгоритмами сжатия является описанное выше наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их можно применять на данных любого типа, в то время как применение сжатия потерь должно быть обосновано. Некоторые виды данных не приемлят каких бы то ни было потерь:
- символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.;
- жизненно важные данные, изменения в которых могут привести к критическим ошибкам: например, получаемые с медицинской измерительной техники или контрольных приборов летательных, космических аппаратов и т. п.
- данные, многократно подвергаемые сжатию и расжатию: рабочие графические, звуковые, видеофайлы.
Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC , позволяет в большинстве случаев сжать звук в 1,5-2,5 раза, в то время как алгоритм с потерями Vorbis , в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.
Системные требования алгоритмов
Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых исполняются:
- оперативной памяти (под промежуточные данные);
- постоянной памяти (под код программы и константы);
- процессорного времени.
В целом, эти требования зависят от сложности и «интеллектуальности» алгоритма. По общей тенденции, чем лучше и универсальнее алгоритм, тем большие требования с машине он предъявляет. Однако в специфических случаях простые и компактные алгоритмы могут работать лучше. Системные требования определяют их потребительские качества: чем менее требователен алгоритм, тем на более простой, а следовательно, компактной, надёжной и дешёвой системе он может работать.
Так как алгоритмы сжатия и разжатия работают в паре, то имеет значение также соотношение системных требований к ним. Нередко можно усложнив один алгоритм можно значительно упростить другой. Таким образом мы можем иметь три варианта:
Алгоритм сжатия гораздо требовательнее к ресурсам, нежели алгоритм расжатия. Это наиболее распространённое соотношение, и оно применимо в основном в случаях, когда однократно сжатые данные будут использоваться многократно. В качетсве примера можно привести цифровые аудио и видеопроигрыватели. Алгоритмы сжатия и расжатия имеют примерно равные требования. Наиболее приемлемый вариант для линии связи, когда сжатие и расжатие происходит однократно на двух её концах. Например, это могут быть телефония. Алгоритм сжатия существенно менее требователен, чем алгоритм разжатия. Довольно экзотический случай. Может применяться в случаях, когда передатчиком является ультрапортативное устройство, где объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков, или это могут быть данные распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.
См. также
Wikimedia Foundation . 2010 .
Смотреть что такое "Сжатие информации" в других словарях:
сжатие информации - уплотнение информации — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы уплотнение информации EN information reduction …
СЖАТИЕ ИНФОРМАЦИИ - (сжатие данных) представление информации (данных) меньшим числом битов по сравнению с первоначальным. Основано на устранении избыточности. Различают С. и. без потери информации и с потерей части информации, несущественной для решаемых задач. К… … Энциклопедический словарь по психологии и педагогике
адаптивное сжатие информации без потерь - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN adaptive lossless data compressionALDC … Справочник технического переводчика
уплотнение/сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compaction … Справочник технического переводчика
цифровое сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compression … Справочник технического переводчика
Звук является простой волной, а цифровой сигнал является представлением этой волны. Это достигается запоминанием амплитуды аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за… … Википедия
Процесс, обеспечивающий уменьшение объема данных путем сокращения их избыточности. Сжатие данных связано с компактным расположением порций данных стандартного размера. Различают сжатия с потерей и без потери информации. По английски: Data… … Финансовый словарь
сжатие цифровой картографической информации - Обработка цифровой картографической информации в целях уменьшения ее объема, в том числе исключения избыточности в пределах требуемой точности ее представления. [ГОСТ 28441 99] Тематики картография цифровая Обобщающие термины методы и технологии… … Справочник технического переводчика
Цель урока: развивать внимательность, сообразительность, воспитывать интерес к предмету.
Оборудование: компьютеры, лабораторные диски, соответствующее программное обеспечение, карты с тестовым заданием.
Ход урока
1. Организационная часть.
2. Актуализация опорных знаний.
3. Изучение нового материала
4. Закрепление нового материала.
5. Домашнее задание.
6. Подведение итогов урока.
Изучение нового материала
1. Что такое архивирование. Понятие о сжатии данных.
2. Основные виды программ-архиваторов.
3. Программа-архиватор WIN-RAR.
4. Как добавлять файл в архив, а также извлекать его из архива.
С развитием информационных технологий остро встал вопрос о способах хранения данных. Начиная с 40-х годов ХХ в., Ученые разрабатывают методы представления данных, при которых пространство на носителях информации использовался бы экономнее. Результатом этого стала технология сжатия данных и архивации данных (backup).
Архивация данных - это слияние нескольких файлов или каталогов в единый файл-архив.
Сжатие данных - сокращение объема исходных файлов путем устранения избыточной информации.
Для выполнения этих задачах являются программы-архиваторы, которые обеспечивают сжатие данных: в частности, архивирование файлов. С помощью специальных алгоритмов архиваторы удаляют из файлов всю избыточную информацию, а при обратных операциях распаковки они восстанавливают информацию в первичном виде. Размер сжатого файла от двух до десяти раз менее файла-оригинала. При этом сжатие и восстановление информации происходит без потерь. Сжатие без потерь актуально при работе с текстовыми и программными файлами, в задачах криптографии. Существуют также методы сжатия с потерями.
Степень сжатия зависит от типа файлов и от программы - архиватора. Более всего сжимаются текстовые файлы, менее всех – звуковые и видеофайлы.
Архивирование файлов. Задачи
До сих пор речь шла об одном назначении архивации данных - экономнее использования носителей информации. Однако с помощью архивации можно выполнять целый комплекс задач:
1. Уменьшение объема файлов (актуально не только для экономии места на носителях, но и для быстрого переноса файлов по сети).
2. Резервное копирование на внешние носители для хранения важной информации.
3. Архивация при шифровании данных с целью уменьшения вероятности взлома криптосистемы.
Процесс записи информации в архивный файл называется - архивирование.
Извлечение файлов из архива - разархивирование.
Первые программы-архиваторы появились в середине 80-х годов. Они были ориентированы на работу в MS-DOC и поддерживали популярные архивные форматы: ARC, ICE, ARJ, ZIP и RAR и др. Существовала также группа архиваторов, которые упаковывали данные в самораспаковывающиеся архивы - файлы с расширениями. eхе,. cоm. Для сжатия всего диска были созданы резидент архиваторы. Они позволяли поднять эффективность использования дискового пространства путем создания крупных архивных файлов - «сжатий» дисков.
Значительно более удобной стала работа с архивами при появлении Windows и Windows-версий архиваторов. Из бывших архивных форматов среди пользователей Windows по-настоящему прижились ARJ, ZIP - программы которые распаковывают файлы. Большие по объему архивные файлы могут быть размещены на нескольких дискетах (томах). Такие архивы называются многотомными.
Том - это составная часть многотомного архива.
Сейчас используется десятки программ-архиваторов, которые отличаются перечнем функций и параметрами работы, однако лучшие из них имеют примерно одинаковые характеристики. Мы знаем, что упаковка и распаковки файлов выполняется одной и той же программе, но в некоторых случаях это осуществляется разными программами, например, программа РКZIP упаковывает файлы, а РКUNZIP - распаковку файлов.
Программы-архиваторы позволяют создавать такие архивы, для извлечения из которых не нужны какие-либо программы, так как архивные файлы содержат в себе программу самораспаковки. Такие архивы называются SFX-архивами.
Помещение файлов в архив: Пуск Программы WINRAR или в виде ярлыка на Рабочем столе.
Универсальный архиватор WINRAR
Архиватор WINRAR также предназначен для архивирования файлов. Он имеет удобную графическую оболочку и поддерживает технологию Drag and Drop. Программа WINRAR позволяет работать не только с архивными файлами rar, но и с другими архивными форматами: zip, cab, arj, lzh. Запускается WINRAR любым из возможных способов, предусмотренных в Windows. Запуск программы с помощью Главного меню кнопки Пуск Программы WINRAR WINRAR или с помощью ярлыка на Рабочем столе.
Тестовый опрос по основам работы с дисками.
Домашнее задание.
Самоанализ урока.
Для выполнения этих задачах являются программы-архиваторы, которые обеспечивают как архивирование, так и сжатия данных. С помощью специальных алгоритмов архиваторы удаляют из файлов всю избыточную информацию, а при обратных операциях распаковки они восстанавливают информацию в первичном виде. Размер сжатого файла от двух до десяти раз менее файла-оригинала.