§ 5. Методы свертывания информации

Определения и обозначения

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

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

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

Коэффициент сжатия — отношение объёма исходного сообщения к объёму сжатого: K = Vисх / Vсж. Чем больше K, тем сильнее уменьшен файл. При K = 1 объём не изменился, а значение меньше единицы означает, что служебные сведения сделали запись больше.

Как это устроено

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

При кодировании повторяющихся последовательностей программа ищет серии одинаковых элементов и заменяет каждую компактным описанием, например символом и длиной серии. Для строки AAAAA можно записать A5, если формат записи заранее определён. Метод особенно эффективен при длинных сериях, поскольку одно описание заменяет много одинаковых символов. Если серии короткие, числа и разделители могут съесть выгоду.

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

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

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

Сравнение методов свертывания информации

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

Разбор задач

Задача 1. Кодирование повторов

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

1. Разделим строку на серии: AAAAAA, BBB, CC и AAAA.
2. Заменим серии описаниями A6, B3, C2 и A4.
3. В исходной строке 15 символов, в записи A6B3C2A4 — 8 символов. Поэтому K = 15 / 8 = 1,875.

Ответ: свернутая запись — A6B3C2A4, коэффициент сжатия равен 1,875. В реальном файле нужно было бы дополнительно учесть формат чисел и разделители.

Задача 2. Частотное кодирование

Пусть сообщение имеет частоты: A — 8, B — 4, C — 2, D — 1. Требуется составить таблицу частот, назначить короткие коды и показать, почему сообщение можно декодировать.

1. Расположим символы по убыванию частоты: A, B, C, D.
2. Назначим им коды 0, 10, 110 и 111. Частому A достался самый короткий код.
3. Проверим однозначность: ни один из кодов 0, 10, 110, 111 не является началом другого кода. Значит, поток можно читать слева направо, выделяя код при его распознавании.

Ответ: таблица может иметь вид A — 0, B — 10, C — 110, D — 111. Принцип сжатия состоит в том, что многочисленные появления A занимают по одному биту, а редкие символы получают более длинные записи.

Задача 3. Выбор способа

Нужно выбрать метод для текстового документа, фотографии и музыкальной записи. Главный вопрос — можно ли изменить данные и всё равно сохранить их назначение.

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

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

Типичные ошибки

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

Не учитывают служебную информацию. Таблица кодов, словарь и длины серий тоже занимают место, поэтому простое сравнение записанных символов бывает неверным. При вычислении коэффициента включайте в объём весь сжатый файл.

Короткие коды дают редким символам. Тогда частые символы занимают много места и главное преимущество метода теряется. Сначала составьте таблицу частот и убедитесь, что средняя длина кодов уменьшилась.

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

Связь с другими темами

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

Дальше методы свертывания помогут понять работу архиваторов и форматов ZIP, PNG, JPEG, MP3 и MPEG. Одни из них сохраняют данные точно, другие используют особенности восприятия человека.

Тема связана с вероятностными методами, алгоритмами кодирования, передачей данных по сетям и оценкой эффективности алгоритмов. Везде приходится сопоставлять объём, скорость, качество и надёжность восстановления.

Что запомнить

• Свертывание уменьшает объём представления информации за счёт устранения избыточности.
• Избыточность возникает из-за повторов, закономерностей и неравномерной частоты символов.
• Сжатие без потерь позволяет точно восстановить исходные данные.
• Сжатие с потерями уменьшает объём сильнее, но изменяет исходную информацию.
• Часто встречающимся символам обычно выгодно назначать более короткие коды.
• Коэффициент сжатия сравнивает объёмы исходного и сжатого сообщения: K = Vисх / Vсж.
• Выбор метода зависит от типа данных и требований к точности восстановления.