6. Методы сжатия цифровой информации.

Характерной особенностью большинства «классиче­ских» типов информации, с которыми работают люди, является их избыточность.

Пример. В русском языке существуют слова, однозначно прочитываемые в случае «потери» некоторых букв. Например, С*НТ*БРЬ, МОС*_, Д*Р*ВО. Кроме того, имея текст на русском языке с «потерянными» буквами, человек, достаточно хорошо владеющий русским языком, может однозначно восстановить его. Например, вы без труда прочитаете предложение с пропущенными буквами «Дм*т*ий Ива*ов* Менд*ле*в — в*л*ки* рус*кий х****». Однако если это предложение будет читать иностранец, едва знающий русский язык и русскую историю, то он, скорее всего, не сможет его понять. Мы, носители русского языка, можем с легкостью восстановить окончания, пропущенные буквы в слогах, подобрать подходящие слова (из тех, что нам известны). А иностранцу просто не с чем сравнивать получаемую информацию. Таким образом, для носителя языка обычный связный текст на его родном языке содержит избыточную информацию — ее можно удалить, но смысл текста для него сохранится.

Пример. Одним из примеров проявления избыточности информации и ее сжатия является использование математических обозначений. Например, сумма чисел 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 записывается так:

2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 + 20 + 22 + + 24 + 26 + 28 + 30.

Нетрудно заметить, что эта сумма составлена из всех четных чисел от 2 до 30. Используя математическую нотацию, эту сумму можно записать намного короче:

Итак, введя новые обозначения, мы сумели сократить запись математического выражения, а значит, сжать информацию. Однако если первая форма записи понятна любому, кто учил азы математики, то вторая понятна только тем, кто знает, как следует интерпретировать эту запись.

Пример с суммой позволяет продемонстрировать еще одну особенность методов сжатия — степень сжатия входных данных принципиально зависит от самих сжимаемых данных. Так, чтобы воспользоваться обозначением суммы, надо найти формулу, выражающую складываемые числа через индекс суммирования. И хотя ка- кую-нибудь формулу можно вывести для любой конечной последовательности (например, с помощью интерполяционной формулы Лагранжа), но вот компактную формулу подобрать удается далеко не всегда! Пример «плохой» последовательности:

102 + 103 + 105 + 107 + 111 + 113 + 117 + 119 + + 123 + 129 + 131 + 137 + 141 + 143 + 147.

Каждое число в данном ряду получено прибавлением 100 к простому числу. Увы, общая формула для всех простых чисел до сих пор не найдена, равно как не доказано существование или отсутствие такой формулы (проблема «генератора простых чисел»). Впрочем, для конечного числа простых чисел или для простых чисел с особой структурой формулы-генераторы существуют.

Дадим формальное определение избыточности информации.

Определение 13. Кодирование информации является избыточным, если количество бит в полученном коде больше, чем это необходимо для однозначного декодирования исходной информации.

Степень избыточности зависит от типа информации: у видеоинформации она в несколько раз больше, чем у графической информации, а степень избыточности последней в несколько раз больше, чем текстовой информации. Вообще, степень избыточности естественной информации достаточно велика. Клод Шеннон, исследовав избыточность литературного английского языка, установил, что она составляет около 50%. Это означает, что если в английском тексте наугад стереть около половины букв, то по оставшимся буквам человек, знающий английский язык, почти наверняка сможет восстановить текст. Избыточность языка выполняет очень важную функцию — обеспечивает человеку надежность ее восприятия, особенно в неблагоприятных условиях (просмотр телепередач при наличии помех, чтение текстов в условиях недостаточной освещенности, разговор в вагоне метро и т. п.).

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

Первые теоретические разработки в области сжатия информации относятся к концу 1940-х годов, когда была опубликована статья К. Шеннона «Математическая теория коммуникаций».

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