Конспект урока сжатие данных без потерь. Сжатие файлов: Как это происходит? Общие принципы, на которых основано сжатие данных

Всем, кто использует компьютерные программы сжатия информации, хорошо знакомы такие слова, как «zip», «implode», «stuffit», «diet» и «squeeze». Всё это имена программ или названия методов для компрессии компьютерной информации. Перевод этих слов в той или иной степени означает застегивание, уплотнение, набивку или сжатие. Однако обычный, языковый смысл этих слов или их перевод не в полной мере отражают истинную природу того, что происходит с информацией в результате компрессии. На самом деле, при компрессии компьютерной информации ничего не набивается и не ужимается, но лишь удаляется некоторый избыток информации, присутствующий в исходных данных. Избыточность - вот центральное понятие в теории сжатия информации. Любые данные с избыточной информацией можно сжать. Данные, в которых нет избыточности, сжать нельзя, точка.

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

Первый тип информации - это текст. Текст представляет собой важнейший вид компьютерных данных. Огромное количество компьютерных программ и приложений являются по своей природе нечисловыми; они работают с данными, у которых основными элементарными компонентами служат символы текста. Компьютер способен сохранять и обрабатывать лишь двоичную информацию, состоящую из нулей и единиц. Поэтому каждому символу текста необходимо сопоставить двоичный код. Современные компьютеры используют так называемые коды ASCII (произносится «аски», а само слово ASCII является сокращением от «American Standard Code for Information Interchange»), хотя все больше компьютеров и приложений используют новые коды Unicode. ASCII представляет код фиксированной длины, где каждому символу присваивается 8-битовая последовательность (сам код занимает семь битов, а восьмой - проверочный, который изначально был задуман для повышения надежности кода). Код фиксированной длины представляется наилучшим выбором, поскольку позволяет компьютерным программам легко оперировать с символами различных текстов. С другой стороны, код фиксированной длины является по существу избыточным.

В случайном текстовом файле мы ожидаем, что каждый символ встречается приблизительно равное число раз. Однако файлы, используемые на практике, навряд ли являются случайными. Они содержат осмысленные тексты, и по опыту известно, что, например, в типичном английском тексте некоторые буквы, такие, как «Е», «Т» и «А», встречаются гораздо чаще, чем «Z» и «Q». Это объясняет, почему код ASCII является избыточным, а также указывает на пути устранения избыточности. ASCII избыточен прежде всего потому, что независимо присваивает каждому символу, часто или редко используемому, одно и то же число бит (восемь). Чтобы удалить такую избыточность, можно воспользоваться кодами переменной длины, в котором короткие коды присваиваются буквам, встречающимся чаще, а редко встречающимся буквам достаются более длинные коды. Точно так работает кодирование Хаффмана (см. § 1.4).

Представим себе два текстовых файла А и В, содержащие один и тот же текст, причем файл А использует коды ASCII, а В записан с помощью некоторых кодов переменной длины. Мы ожидаем, что размер файла В меньше размера А. Тогда можно сказать, что файл А сжат в файл В. Понятно, что степень сжатия зависит от избыточности взятого текста, а также от используемых кодов переменной длины. Текст, в котором одни символы встречаются очень часто, а другие очень редко, имеет большую избыточность: он будет сжиматься хорошо, если коды переменной длины выбраны подходящим образом. В соответствующем файле В коды часто встречающихся символов будут короткими, а коды редких символов - длинными. Длинные коды не смогут понизить степень сжатия, так как они будут встречаться в файле В достаточно редко. Большая часть В будет состоять из коротких кодов. С другой стороны, случайный текстовый файл не получает преимущество при замене кодов ASCII кодами переменной длины, потому что сжатие, достигнутое с использованием коротких кодов, будет аннулировано длинными кодами. В этом частном примере работает общее правило, которое гласит: случайные данные невозможно сжать, так как в них нет избыточности.

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

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

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

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

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

Предположим, что файл состоит из бит, и мы хотим его сжать эффективным образом. Будем приветствовать любой алгоритм, который сожмет этот файл, скажем, в 10 бит. Компрессия в 11 или 12 бит тоже была бы замечательна. Сжатие файла до половины его размера будет для нас вполне удовлетворительным. Всего существует различных файлов размера . Их надо бы сжать в различных файлов размера не больше . Однако, общее число таких файлов равно

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

Для (файл всего в 100 бит) общее число файлов равно , а число файлов, эффективно сжимаемых, равно . А их частное просто до смешного малая дробь .

Для (файл из 1000 бит, т.е. около 125 байт) число всех файлов равно , а число сжимаемых всего . Их доля просто катастрофически мала, она равна .

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

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

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

а) Компрессор или кодер - программа, которая сжимает «сырой» исходный файл и создает на выходе файл со сжатыми данными, в которых мало избыточности. Декомпрессор или декодер работает в обратном направлении. Отметим, что понятие кодера является весьма общим и имеет много значений, но поскольку мы обсуждаем сжатие данных, то у нас слово кодер будет означать компрессор. Термин кодек иногда используется для объединения кодера и декодера.

б) Метод неадаптивного сжатия подразумевает неспособность алгоритма менять свои операции, параметры и настройки в зависимости от сжимаемых данных. Такой метод лучше всего сжимает однотипные данные. К ним относятся методы группы 3 и группы 4 сжатия факсимильных сообщений (см. § 1.6). Они специально разработаны для сжатия в факс-машинах и будут весьма слабо работать на других типах данных. Напротив, адаптивные методы сначала тестируют «сырые» исходные данные, а затем подстраивают свои параметры и/или операции в соответствии с результатом проверки. Примером такого алгоритма может служить кодирование Хаффмана из § 1.5. Некоторые методы компрессии используют двухпроходные алгоритмы, когда на первом проходе по файлу собирается некоторая статистика сжимаемых данных, а на втором проходе происходит непосредственно сжатие с использованием параметров, вычисленных на первой стадии. Такие методы можно назвать полуадаптивными. Методы компрессии могут быть также локально адаптивными, что означает способность алгоритма настраивать свои параметры исходя из локальных особенностей файла и менять их, перемещаясь от области к области входных данных. Пример такого алгоритма приведен в .

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

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

д) Производительность сжатия: несколько величин используются для вычисления эффективности алгоритмов сжатия.

1) Коэффициент сжатия определяется по формуле

Коэффициент 0.6 означает, что сжатые данные занимают 60% от исходного размера. Значения большие 1 говорят о том, что выходной файл больше входного (отрицательное сжатие). Коэффициент сжатия принято измерять в bpb (bit per bit, бит на бит), так как он показывает, сколько в среднем понадобится бит сжатого файла для представления одного бита файла на входе. При сжатии графических изображений аналогично определяется величина bpp (bit per pixel, бит на пиксел). В современных эффективных алгоритмах сжатия текстовой информации имеет смысл говорить о похожей величине bpc (bit per character, бит на символ), то есть, сколько в среднем потребуется бит для хранения одной буквы текста.

Здесь следует упомянуть еще два понятия, связанные с коэффициентом сжатия. Термин битовая скорость (bitrate) является более общим, чем bpb и bpc. Целью компрессии информации является представление данных с наименьшей битовой скоростью. Битовый бюджет (bit budget) означает некоторый довесок к каждому биту в сжатом файле. Представьте себе сжатый файл, в котором 90% размера занимают коды переменной длины, соответствующие конкретным символам исходного файла, а оставшиеся 10% используются для хранения некоторых таблиц, которые будут использоваться декодером при декомпрессии. В этом случае битовый бюджет равен 10%.

2) Величина, обратная коэффициенту сжатия, называется фактором сжатия:

В этом случае значения большие 1 означают сжатие, а меньшие 1 - расширение. Этот множитель представляется большинству людей более естественным показателем: чем больше фактор, тем лучше компрессия. Эта величина отдаленно соотносится с коэффициентом разреженности, который будет обсуждаться в § 4.1.2.

3) Выражение , где - коэффициент сжатия, тоже отражает качество сжатия. Его значение равное 60 означает, что в результате сжатия занимает на 60% меньше, чем исходный файл.

4) Для оценивания эффективности алгоритмов сжатия образов используется величина bpp. Она показывает, сколько необходимо в среднем использовать битов для хранения одного пиксела. Это число удобно сравнивать с его значением до компрессии.

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

Приведем пример простой модели для черно-белого изображения. Каждый пиксел такого изображения - это один единственный бит. Предположим, что алгоритм уже прочитал и сжал 1000 пикселов и читает 1001-ый пиксел. Какова вероятность того, что пиксел будет черным? Модель может просто сосчитать число черных пикселов в уже прочитанном массиве данных. Если черных пикселов было 350, то модель приписывает 1001-ому пикселу вероятность быть черным. Эта вероятность вместе с пикселом (черным или белым) передаются компрессору. Главным моментом является то, что декодер может также легко вычислить вероятность 1001-ого пиксела.

ж) Слово алфавит означает множество символов в сжимаемых данных. Алфавит может состоять из двух символов, 0 и 1, из 128 символов ASCII, из 256 байтов по 8 бит в каждом или из любых других символов.

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

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

Чудесные дни перед свадьбой сродни живому вступлению к скучной книге.
- Уилсон Мизнер

ТЕМА УРОКА. Сжатие и архивирование данных.

ЦЕЛЬ УРОКА:

Учебная : сформировать привычки использования программ- архиваторов; учить сжимать и архивировать данные.

Развивающая: развивать умение использовать полученные знания в разных ситуациях во время работы за компьютером;

Воспитательная : воспитывать интерес к изучению информатики.

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

Тип урока : комбинированный.

ХОД УРОКА.

І. Организационный момент.

Проверка наличия и готовности учеников к уроку. Создание положительного настроения для проведения урока.

ІІ. Мотивация учебной деятельности.

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

ІІІ. Изучение нового материала

Объяснение учителя с элементами демонстрации или самостоятельная работа учеников с источником информации (презентация)

Часто возникает необходимость в уменьшении размеров данных, которые хранятся в памяти компьютера. Для этого используют специальные способы сжатия данных, которые называют алгоритмами (методами) сжатия данных. Сжатие данных используют во время создания файлов определенных типов, например, графических типа TІFF, JPEC, PNG или звуковых типа MPEG 3, WMA, для передачи файлов по сети и т.д.

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

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

Для создания резервных копий файлов нужно:

1. Открыть окно настройки архивирования и восстановления файлов (Пуск  Панель управления  Система и безопасность  Резервное копирование и восстановление).

3. Указать устройство, на которое будет записан архивный файл.

4. Указать перечень папок с файлами, которые будут включены в резервной копии.

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

Начать процесс создания архива данных пользователя выбором кнопки Сохранить настройки и запустить резервное копирование.

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

К основным операциям над архивами принадлежат:

Создание архивов файлов и папок с возможным сжатием данных;

Добавление файлов и папок к уже существующим архивам и замена у них уже включенных объектов;

Просмотр содержимого архивов;

Замещение и обновление файлов и папок в архивах;

Добыча из архива всех или только избранных файлов и папок;

Создание многотомных архивов (архив разбивается на несколько отдельных файлов - томов); размер томов устанавливает пользователь;

ІV. Физкультминутка

Проведение комплекса упражнений для снятия мышечного напряжения

V. Рефлексия.

VІ. Практическая работа

Техника безопасности и правила поведения в компьютерном кабинете.

VІІ. Обобщение знаний и умений

Фронтальный опрос

1. Для чего используется сжатие данных?

2. В каких случаях возможно использование сжатие с частичной потерей данных?

3. Для чего используется архивирование данных?

4. Что такое архивирование и что такое сжатие файлов?

5. Как называют программы, которые выполняют архивирование данных?

VІІІ. Подведение итогов урока

ІX. Домашнее задание

Обработать соответствующий параграф учебника, конспект урока.

Конспект урока по информатике и ИКТ

Тип : Урок изучения нового материала

Тема : Архиваторы. Методы сжатия информации.

Цели :

Изучить методы сжатия информации (упаковки и Хаффмана)

Развить алгоритмическое мышление

Воспитание ответственного отношения к выполнению задания.

Метод: Объяснительно-иллюстративный

Ход урока:

Организационный момент (2 мин)

Актуализация знаний. (5 мин)

Объяснение материала и запись в тетрадь. (25 мин)

Первоначальное закрепление материала (10 мин)

Подведение итогов. (3 мин)

Вопросы по актуализации знаний:

Как вы понимаете понятие «сжатие информации»?

Каким образом сжимается цифровая информация?

Какие программы архиваторы вы знаете?

Информация в какой форм требует обязательного сжатия?

Теоретический материал:

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

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

Существуют различные алгоритмы архивации данных без потери информации, т.е. при разархивации данные будут восстановлены в исходном виде. Для ОС Windows наиболее популярными являются архиваторы WinRAR, WinZIP,WinACE.

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

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

Метод упаковки

Входной текс «КОЛ_ОКОЛО_КОЛОКОЛА» содержит всего 5 различных символов (К, О, Л, А, _). Следовательно каждый символ может быть закодирован трем битами. Всего в исходном тесте 18 символов, так что потребуется 18Х3=54бита. Коэффициент сжатия равен 144/54=2,7

Метод Хаффмана.

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

Улучшения степени сжатия можно достичь, кодирую часто встречающиеся символы короткими кодами, а редко встречающиеся – более длинными. Именно такова идея метода, опубликованного Д.Хаффманом в 1952 г.

Алгоритм Хаффмана

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

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

Создается их узел- «родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.

Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой – бит 0.

«Родитель» добавляется в список свободных узлов, а двое его «детей» удаляются из этого списка.

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

Задания на закрепления

Упаковать сообщение 2 методами: Архип_осип._Осип_охрип.

Вопросы для подведения итога урока:

Что такое сжатие информации?

Основное назначение программ архиваторов.

Какие методы сжатия сегодня изучили.

Какой метод сжатия наиболее эффективный и почему?

План:

Введение

• 1 Принципы сжатия данных
• 2 Характеристики алгоритмов сжатия и их применимость
  • 2.1 Коэффициент сжатия
  • 2.2 Допустимость потерь
  • 2.3 Системные требования алгоритмов
• 3 Алгоритмы сжатия данных неизвестного формата
Литература

Введение

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

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

1. Принципы сжатия данных

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

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

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

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

2. Характеристики алгоритмов сжатия и их применимость

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

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

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

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

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

Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:

• средний (обычно по некоторому тестовому набору данных);
• максимальный (случай наилучшего сжатия);
• минимальный (случай наихудшего сжатия);

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

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

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

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

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

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

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

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

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

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

3. Алгоритмы сжатия данных неизвестного формата

Имеется два основных подхода к сжатию данных неизвестного формата.

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

Литература

• Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - Диалог-МИФИ, 2002. - С. 384. - ISBN 5-86404-170-X 3000 экз.
• Д. Сэломон. Сжатие данных, изображения и звука. - М .: Техносфера, 2004. - С. 368. - ISBN 5-94836-027-X 3000 экз.

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

Виталий

Совершенно верно, Виталий, это действительно не так просто себе представить, тем более, если не знаешь алгоритма. Но читателям журнала «Компьютер» повезло;), поскольку я в свое время много интересовался алгоритмами сжатия данных и, как программист, даже пробовал писать собственный архиватор.

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

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

Итак, давайте начнем с простого примера. Допустим, у нас есть текстовый файл, который содержит строку текста:

АААГГДЕЕЕЕЖЖУУУККККИИИ

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

А3Г2Д1Е4Ж2У3К4И3

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

Данный пример довольно упрощен и не отражает эффективность, которую обычно демонстрируют при сжатии архиваторы. Так у нас получилось сжатие в 22/16 = 1,375 раза, хотя архиваторы, как правило, способны сжимать файлы в 2-10000 раз. Все зависит от повторяемости значений байт в файле.

Какие архиваторы бывают

Например, во времена незабвенной MS-DOS были архиваторы ARJ, PKZIP, HA, RAR, ARC, ACE и упаковщики программ LZEXE и PKLITE. Позднее для операционной системы Windows были созданы WinAce, WinZIP, WinRAR, 7Zip и известный мне упаковщик UPX.

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

Сжатие с потерями можно назвать адаптивным сжатием, и применяется для упаковки изображений, видео и звука, поскольку такие данные сжатию без потерь поддаются весьма незначительно (всего примерно до 2 раз).

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

На сколько сжимаются разные файлы

Текстовые

Действительно, например, текстовые файлы могут сжиматься весьма плотно. Так, например, книга Аркадия и Бориса Стругацких «Трудно быть богом» размером 354 329 байт архиватором WinRAR сжимается до 140 146 байт, т.е. в 2,5 раза.

Программы

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

Для этого существуют упаковщики программ на подобие UPX и др. Например, мой текстовый редактор Superpad.exe размером 524 288 байт упаковщиком UPX сжимается до 179 200 байт (в 2,9 раза) и при этом может по-прежнему запускаться самостоятельно как программа.

Изображения

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

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

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

Рис. 1. Красивый лягушонок в формате BMP

Для сравнения, возьмем красивого лягушонка (рис. 1) разрешение 799x599 пикселей (точек) и сохраним в разные форматы хранения изображений. Получим файлы:

frog.bmp - размер 1 437 654 байта и тут, по сути, никакого сжатия и никаких потерь качества, поскольку картинка занимает положенные ей байты в формате Ширина x Высота x 3 байта на пиксель + заголовок формата файла BMP согласно качеству True colors (24 бит/пиксель). Т.е. каждая точка представлена тремя компонентами RGB (Red-красный, Green-зеленый и Blue-синий), каждая из которых занимает один байт.

frog24.png - 617 059 байт, сжатие в 2,33 раза и без потерь - основное свойство формата PNG-24. Данные BMP и PNG практически идентичны.

Рис. 2. Файл frog_256colors.gif

frog_256colors.gif - 261 956 байт (рис. 2), сжатие в 5,48 раза с потерями, базовая палитра 256 цветов (8 бит/пиксель). Уловить разницу между этим файлом и оригиналом в BMP довольно сложно, как в той игре «Найди десять отличий».

Рис. 3. Файл frog_64colors.gif

frog_64colors.gif - 187 473 байта (рис. 3), сжатие в 7,67 раза с потерями, базовая палитра уплотнена до 64 цветов (6 бит/пиксель). А вот тут цвета уже блеклые, но вполне сходное с оригиналом изображение. Особенно это заметно, если посмотреть на глаз лягушонка.

JPEG

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

С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселями приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW.

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

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

Описание алгоритма сжатия JPEG довольно не простое, поэтому кто захочет, может ознакомиться с ним по ссылке http://el-izdanie.narod.ru/gl4/4-3.htm. Ну и для сравнения сожмем нашу исходную картинку с разным уровнем качества:

frog100%.jpg - 216 168 байт, сжатие в 6,65 раза, потери якобы 0%, т.е. 100%-е качество картинки, но даже на это рассчитывать я бы не стал. Поверьте, отличия есть, правда, на глаз абсолютно неотличимые.

frog60%.jpg - 85 910 байт, сжатие в 16,7 раза, т.е. качество картинки 60%, но картинка снова кажется одинаковой, хотя, если присмотреться к участкам с однородным фоном или мелким деталям, то заметны артефакты в виде смазанности или квадратных одноцветных сегментов.

frog20%.jpg - 36 426 байт, сжатие в 39,5 раз, качество картинки 20% от исходного изображения, но по-прежнему картинка еще способна обмануть неискушенный глаз, но на однородном фоне отчетливо видны одноцветные угловатые сегменты, а мелкие детали окончательно потеряли свои четкие очертания.

MPEG

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

Рис. 4. Исходные кадры видео

Рис. 5. Межкадровая разница без применения алгоритмов компенсации движения

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

Однако, из-за движения каких-либо объектов в кадре (или самой камеры) использование подобия соседних кадров было неполным. Технология компенсации движения позволяет находить похожие участки, даже если они сдвинуты относительно предыдущего кадра.

Компенсация движения (англ. Motion Compensation) - один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует сходство соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8).

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

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

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

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

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

Звук и музыка

Звук и музыка могут без потерь, либо с потерями храниться в формате WAV. Например, формат WAV (Windows PCM) не предусматривает сжатие и хранит звуковой сигнал в оригинале, если можно так выразиться.

Формат WAV (ACM Waveform), по сути, является контейнером и может хранить звук, сжатый по алгоритму MPEG layer 3, либо хранить музыку в формате MP3, хотя много и других форматов OGG, FLAC и д.р.

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