Конспект урока на тему "сжатие и архивирование данных". Введение

Слайд 3

Избыточность данных

• Большинство данных являются избыточными
• Избыточность улучшает восприятие и обработку информации
• При хранении избыточность уменьшают
• Наибольшая избыточность у видеоинформации, затем идет графическая, звуковая, и самая низкая избыточность у текстовой информации

Слайд 4

Методы сжатия

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

Слайд 5

С частичной потерей

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

Слайд 6

• Применяется для таких типов данных, для которых формальная утрата части содержания не приводит к потере потребительских свойств и обеспечивает высокую степень сжатия.
• Примеры:видео MPG, звук MP3, рисунки JPG.

Слайд 7

Без потери – «обратимый»

• Применяется к текстам, базам данных, и ко всем остальным вышеназванным типам.
• Пример: рисунки – GIF, TIF,PCX, видео - AVI, любой тип данных – ZIP, ARJ, RAR и др.

Слайд 8

Архивы

• Архив – файл, содержащий в себе один или несколько файлов в сжатом виде.
• Расширение архивного файла зависит от программы-архиватора.
• Архиватор – программы для создания и чтения архивов.Пример:WinRar, WinZip, WinArj.

Слайд 9

Архивы применяют с целью

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

Слайд 10

Возможности архиваторов

Слайд 11

Самораспаковывающийся

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

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

ЦЕЛЬ УРОКА:

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

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

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

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

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

ХОД УРОКА.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Всем, кто использует компьютерные программы сжатия информации, хорошо знакомы такие слова, как «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 бит в каждом или из любых других символов.

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

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

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

Лекция №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-качестве могут занимать десятки гигабайт.
Конечно, пользы от сжатия всего и вся не так много. Но все же существуют ситуации, в которых сжатие крайне полезно, если не необходимо.

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

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

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

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

Универсальные методы сжатия без потерь

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

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

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon"s source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики

Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента s i распределение вероятностей F примет некоторое значение F k , то есть для каждого элемента F= F k и H= H k .

Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей p k (s i) для всех элементов s i .

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

Где P k - вероятность нахождения источника в состоянии k.

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

Кодирование без памяти

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a 1 , a 2 ,… ,a n) словом , а число n - длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

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

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием .

Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a 1 <-> B 1
a 2 <-> B 2
…
a n <-> B n

Это соответствие называют схемой , и обозначают ∑.
В этом случае слова B 1 , B 2 ,…, B n называют элементарными кодами , а вид кодирования с их помощью - алфавитным кодированием . Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование . Теперь введем понятие префикс .

Пусть слово B имеет вид B=B"B"". Тогда B" называют началом, или префиксом слова B, а B"" - его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять - это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово B i не является префиксом слова B j .
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.

Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?
Оно происходит в три этапа.

1. Составляется алфавит Ψ символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
2. Каждому символу a i из алфавита Ψ ставится в соответствие некое слово B i из префиксного множества Ω.
3. Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.

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

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

В первую очередь при кодировании алгоритмом Хаффмана, нам нужно построить схему ∑. Делается это следующим образом:

1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
2. Два символа a j-1 и a j входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова B j-1 , и 1 в начало слова B j , которые будут впоследствии являться кодами символов a j-1 и a j соответственно.
3. Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов - { a 1 , a 2 , a 3 , a 4 }. Предположим также, что вероятности появления этих символов равны соответственно p 1 =0.5; p 2 =0.24; p 3 =0.15; p 4 =0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

1. Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p".
2. Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p"".
3. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
4. Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее:

Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

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

Пусть на входу у нас была строка из 1000 символов, в которой символ a 1 встречался 500 раз, a 2 - 240, a 3 - 150, и a 4 - 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

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

Заключение

Литература

• Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.
• Д. Сэломон. Сжатие данных, изображения и звука; ISBN 5-94836-027-Х; 2004г.