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

Еще одна проблема, тесно связанная с моделями представления информации, – сжатие информации. При хранении и передаче данных по каналам связи объем информации является основным параметром.

Еще одна проблема, тесно связанная с моделями представления информации, – сжатие информации

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

Разработаны и применяются два типа алгоритмов сжатия: сжатие информации с изменением структуры данных (оно происходит без потери данных) и сжатие информации с частичной потерей данных. Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмена и Лемпеля-Зива). Алгоритмы второго типа не позволяют полностью восстановить оригинал и применяются для хранения графики или звука; для текстов, чисел или программ они неприменимы.

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

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

Инструменты