Теоретические основы информатики кандидат технических наук, доцент Полупанов

данных и архивирование

принципы сжатия данных и основные классы алгоритмов сжатия;
рассмотреть алгоритмы сжатия

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

в среднем каждый элемент сообщения.
Н1

n2H2
При передаче одинакового количества информации сообщение тем длиннее, чем меньше его энтропия



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

алфавита, неопределенность , приходящаяся на один элемент, составляет Н0 =

log 32 = 5 бит
С учетом неравномерного появления различных букв алфавита H = 4,42 бит, а с учетом зависимости двухбуквенных сочетаний H’ = 3,52 бит, т.е. H’< H < H0

H’/H;
частная избыточность, зависящая от распределения r’’ = 1 -

H/ H0;
полная избыточность r0 = 1 - H’/ H0
Эти три величины связаны зависимостью r0 = r’ + r’’ - r’r’’
Избыточность русского языка (как и других европейских языков) превышает 50% (r0 = 1 - H’/ H0 = 1 - 3,52/5 = 0,30).

уменьшения их объёма. Применяется для более рационального использования устройств хранения

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

данных, или, точнее, модель избыточности. Иными словами, для сжатия данных

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

аудио, графики, документов представленных в цифровом виде, при использовании которого

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

при использовании которого распакованные данные отличаются от исходных, но степень

отличия не является существенной с точки зрения их дальнейшего использования. Этот тип компрессии часто применяется для сжатия аудио- и видеоданных, статических изображений, в Интернете, особенно в потоковой передаче данных, и цифровой телефонии
Существуют две основных схемы сжатия с потерями:
В трансформирующих кодеках фреймы изображений или звука трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными методами.
В предсказывающих кодеках предыдущие и/или последующие данные используются для того, чтобы предсказать текущий сэмпл изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется.

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

объёма исходных несжатых данных к объёму сжатых, то есть:
k =

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

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

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

более экономное расходование пространства
Действие средств архивации основано на использовании

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

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

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

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

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

В В В В L L L L L А

А А А А
В шестнадцатеричной системе
42 42 42 42 42 4С 4С 4С 4С 4С 41 41 41 41 41
Архиватор может представить этот файл в следующем виде (шестнадцатеричном):
01 05 42 06 05 4С 0А 05 41
Это значит: с первой позиции пять раз повторяется символ "В", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "А". Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.