Избыточность информации: коэффиценты сжатия и избыточности.Сжатие информации.

Вариант №17.

№1.Избыточность информации: коэффиценты сжатия и избыточности.Сжатие информации. 

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

Количественное определение

Информационное содержание одного сообщения в потоке, в наиболее общем случае, определяется как:

Обозначим как R логарифм числа символов в алфавите сообщений:

R = log  | M |

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

D = R − r

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

Сжатие информации

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

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

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

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

• преобразование сжатия;
• преобразование расжатия.
• Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.
• Все методы сжатия делятся на два основных класса
• без потерь,
• с потерями.
• Кардинальное различие между ними в том, что сжатие без потерь обеспечивает возможность точного восстановления исходного сообщения. Сжатие с потерями же позволяет получить только некоторое приближение исходного сообщения, то есть отличающееся от исходного, но в пределах некоторых заранее определённых погрешностей. Эти погрешности должны определяться другой моделью — моделью приёмника, определяющей, какие данные и с какой точностью представленные важны для получателя, а какие допустимо выбросить.
• Характеристики алгоритмов сжатия и применимость
• Коэффициент сжатия
• Коэффициент сжатия — основная характеристика алгоритма сжатия, выражающая основное прикладное качество. Она определяется как отношение размера несжатых данных к сжатым, то есть:
• k = S_o/Sc,
• где k — коэффициент сжатия, S_{o — размер несжатых данных, а Sc — размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:}
• если k = 1, то алгоритм не производит сжатия, то есть получает выходное сообщение размером, равным входному;
• если k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.
• Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон-Е:бит составляет ровно 2^{n. Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.}
• Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, u-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:
• среднее (обычно по некоторому тестовому набора данных);
• максимальное (случай наилучшего сжатия);
• минимальное (случай наихудшего сжатия);
• или каким либо другим. Коэффициент сжатия с потерями при этом сильно зависит от допустимой погрешности сжатия или его качества, которое обычно выступает как параметр алгоритма.
• Допустимость потерь
• Основным критерием различия между алгоритмами сжатия является описанное выше наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их можно применять на данных любого типа, в то время как применение сжатия потерь должно быть обосновано. Некоторые виды данных не приемлят каких бы то ни было потерь:
• символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.;
• жизненно важные данные, изменения в которых могут привести к критическим ошибкам: например, получаемые с медицинской измерительной техники или контрольных приборов летательных, космических аппаратов и т. п.
• данные, многократно подвергаемые сжатию и расжатию: рабочие графические, звуковые, видеофайлы.
• Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC, позволяет в большинстве случаев сжать звук в 1,5—2,5 раза, в то время как алгоритм с потерями Vorbis, в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.
• Системные требования алгоритмов
• Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых исполняются:
• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.
• В целом, эти требования зависят от сложности и «интеллектуальности» алгоритма. По общей тенденции, чем лучше и универсальнее алгоритм, тем большие требования с машине он предъявляет. Однако в специфических случаях простые и компактные алгоритмы могут работать лучше. Системные требования определяют их потребительские качества: чем менее требователен алгоритм, тем на более простой, а следовательно, компактной, надёжной и дешёвой системе он может работать.
• Так как алгоритмы сжатия и разжатия работают в паре, то имеет значение также соотношение системных требований к ним. Нередко можно усложнив один алгоритм можно значительно упростить другой. Таким образом мы можем иметь три варианта:
• Алгоритм сжатия гораздо требовательнее к ресурсам, нежели алгоритм расжатия.
• Это наиболее распространённое соотношение, и оно применимо в основном в случаях, когда однократно сжатые данные будут использоваться многократно. В качетсве примера можно привести цифровые аудио и видеопроигрыватели.
• Алгоритмы сжатия и расжатия имеют примерно равные требования.
• Наиболее приемлемый вариант для линии связи, когда сжатие и расжатие происходит однократно на двух её концах. Например, это могут быть телефония.
• Алгоритм сжатия существенно менее требователен, чем алгоритм разжатия.
• Довольно экзотический случай. Может применяться в случаях, когда передатчиком является ультрапортативное устройство, где объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков, или это могут быть данные распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.