В чем состоит процесс сжатия данных. Кодирование с помощью деревьев Шеннона-Фано. Перемещение и копирование сжатых файлов и папок

Лекция №4. Сжатие информации

Принципы сжатия информации

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

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного - запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

Виды сжатия

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

Сжатие без потери информации.

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

Методы сжатия этого класса не могут допустить утрату информа­ции, поэтому они основаны только на устранении ее избыточности, а информация имеет избыточность почти всегда (правда, если до этого кто-то ее уже не уплотнил). Если бы избыточности не было, нечего было бы и сжимать.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ( - -) и «Ц» (- - ), кодиру­ются четырьмя знаками. Неэффективная кодировка - второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Наличие повторяющихся фрагментов - третье основание для избыточности. В текстах это встречается редко, но в таблицах и в графике повторение кодов - обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding ).

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

Сжатие с потерей информации.

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

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

В то же время, существуют материалы, в которых стоит пожерт­вовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». Но поскольку при создании этих мате­риалов определенный «шум» все равно присутствует, его неболь­шое увеличение не всегда выглядит критичным, а выигрыш в раз­мерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются.MPG для видео и.МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Код Шеннона-Фэно

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

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

Сумма этих вероятностей составляет, естественно, единицу. Разобьем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов - двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой - цифрой 1.

Снова разобьем первую группу (А-В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй - цифру 1.

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

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

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

где ni - количество бит, кодирующих i-й символ, pi - вероятность появления i-го символа.

Код Хаффмана.

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

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

Недостатки методов

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

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

Еще один недостаток кодов - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

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

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". («красный, красный, ..., красный» записывается как «N красных»).

Одна из реализаций алгоритма такова: ищут наименнее часто встречающийся байт, называют его префиксом и делают замены цепочек одинаковых символов на тройки "префикс, счетчик, значение". Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару "префикс, 1" или "префикс, 2". Остается одна неиспользованная пара "префикс, 0", которую можно использовать как признак конца упакованных данных.

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF - файла находится палитра - таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

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

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

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

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

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

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

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG. Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

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

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

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

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

Стоит ли сжимать данные?

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

Однако при этом нужно правильно понимать, что с течением времени увеличивается также и объем тех данных, которые необходимо передавать. И если буквально десять лет назад стандартным для обычного фильма было принято считать объем 700 Мб, то на сегодняшний день фильмы, выполненные в HD-качестве, могут иметь объемы, равные нескольким десяткам гигабайт, не говоря уже о том, сколько свободного места занимают высококачественные картины в формате Blu-ray.

Когда сжатие данных необходимо?

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

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

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

Как можно сжать данные?

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

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

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

Сжатие с потерями

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

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

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

Универсальные методы

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

• Преобразование потока. В данном случае описание новой поступающей несжатой информации осуществляется через уже обработанные файлы, при этом не осуществляется вычисление каких-либо вероятностей, а производится кодирование символов на основе исключительно тех файлов, которые уже подвергались определенной обработке.
• Статистическое сжатие. Данный процесс сжатия информации с целью уменьшения занимаемого ей на диске места распределяется на две подкатегории - адаптивные и блочные методы. Адаптивный вариант предусматривает вычисление вероятностей для новых файлов по информации, которая уже обрабатывалась в процессе кодирования. В частности, к таким методам следует также отнести различные адаптивные варианты алгоритмов Шеннона-Фано и Хаффмана. Блочный алгоритм предусматривает отдельное высчитывание каждого блока информации с последующим добавлением к самому сжатому блоку.
• Преобразование блока. Входящая информация распределяется на несколько блоков, а впоследствии происходит целостное трансформирование. При этом следует сказать о том, что определенные методы, особенно те, которые основываются на перестановке нескольких блоков, в конечном итоге могут привести к значительному снижению объема сжимаемой информации. Однако нужно правильно понимать, что после проведения такой обработки в конечном итоге происходит значительное улучшение вследствие чего проведение последующего сжатия через другие алгоритмы осуществляется гораздо более просто и быстро.

Сжатие при копировании

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

Зачем это нужно?

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

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

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

Перед тем как начинать процесс сжатия файла или папки, очень важно понять все получаемые от этого выгоды, и разобрать сами доступные в Windows 7 методы сжатия:

• NTFS сжатие файла
• Сжатие (zip) папки.

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

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

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

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

• Сжатие - атрибут для файла или папки.
• Папки и файлы на томе NTFS, либо сжаты, либо нет.
• Новые файлы, созданные в сжатой папке сжимаются по умолчанию.
• Состояние сжатой папки не обязательно отражает состояние сжатия файлов в этой папке. Например, папки могут быть сжаты без сжатия его содержания, и некоторые или все файлы в сжатой папке можно распаковать.
• Работа с NTFS-сжатыми файлами без их распаковки, так как они распаковываются и снова сжимаются без вмешательства пользователя.
• Если сжатый файл открыт, система автоматически его распаковывает.
• При закрытии файла Windows снова его сжимает.
• Для упрощения распознавания, NTFS сжатые имена файлов и папок отображаются в другом цвете.
• NTFS-сжатые файлы и папки остаются в сжатом виде, только на NTFS томе.
• NTFS сжатые файлы не могут быть зашифрованы.
• Сжатые байты файла недоступны для приложений; они видят только несжатые данные.
• Приложения, открывающие сжатые файлы могут работать с ними, как с не сжатыми.
• Сжатые файлы не могут быть скопированы в другой файловой системе.

Примечание: для управления сжатием NTFS можно использовать компактный инструмент командной строки.

Перемещение и копирование сжатых файлов и папок.

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

Копирование внутри раздела раздела NTFS.

Как изменяется состояние сжатого файла или папки, если вы его копируете внутри раздела NTFS? При копировании файла или папки внутри файловой системы NTFS раздел, файл или папка наследует состояние сжатия целевой папки. Например, если скопировать сжатый файл или папку в распакованную папку, файл или папка будут автоматически распакованы.

Перемещение внутри NTFS раздела.

Что происходит с состоянием сжатия файла или папки при перемещении в пределах раздела NTFS?

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

Копирование или перемещение между NTFS разделами.

Что происходит с сжатыми файлом или папкой при копировании или перемещении его между разделами NTFS?

При перемещении файла или папки между разделами NTFS, файл или папка наследует состояние сжатия целевой папки. Поскольку Windows 7 рассматривает движение между разделами как копирование с последующей операцией удаления, файлы наследуют состояние сжатия целевой папки.

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

Копирование или перемещение между FAT и NTFS томами.

Что происходит с сжатием файла, который копируется или перемещается между FAT и NTFS томами?

Сжатые файлы, скопированные в раздел FAT становятся не сжатыми, так как FAT тома не поддерживают сжатие. Однако, если вы копируете или перемещаете файлы из раздела FAT в раздел NTFS, они наследуют атрибут сжатия папки, в которую вы их копируете.

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

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

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

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

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

Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run Length Encoding – RLE ). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов на один кодирующий байт -заполнитель и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других, – не кодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже – с малым числом повторяющихся байтов в сериях.

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

Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока ("фразы") заменяются указателем на то место , где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия .

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

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

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

p(S 1)=0,2, p(S 2)=0,15, p(S 3)=0,55, p(S 4)=0,1 . Отсортируем символы по убыванию вероятности появления и представим в виде таблицы ( рис. 14.3 , а).

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

Рис. 14.3.

На втором этапе осуществляется построение кодового дерева по свернутой таблице ( рис. 14.4 , а). Дерево строится, начиная с последнего столбца таблицы.

Корень дерева образует единица , расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45 , изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S 3 и, таким образом, дальнейшее ветвление этого узла не происходит.

Второй узел, маркированный вероятностью 0,45 , соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2 . Вероятность 0,2 соответствует символу S 1 , а вероятность 0,25 , в свою очередь , образуется из вероятностей 0,15 появления символа S 2 и 0,1 появления символа S 4 .

Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами 0 и 1 (например, левые ребра – 0 , а правые – 1 ). На третьем, заключительном этапе, строится таблица , в которой сопоставляются символы источника и соответствующие им кодовые слова кода Хаффмана. Эти кодовые слова образуются в результате считывания цифр, которыми помечены ребра, образующие путь от корня дерева к соответствующему символу. Для рассматриваемого примера код Хаффмана примет вид, показанный в таблице справа ( рис. 14.4 , б).

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

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

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

Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1} . Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит .

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

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