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

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

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

Алгоритмы сжатия данных:

1. Коэффициент избыточности сообщения A

r = (Imax – I)/Imax.

I – количество информации в сообщении A. Imax – максимально возможное количество информации в сообщении той же длины, что и сообщение A.

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

К = n/q

n – число минимально необходимых символов для передачи сообщения.

q – число символов в сообщении, сжатом данным алгоритмом.

Алгоритмы сжатия:

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

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