Избыточность данных

Два лица избыточности

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

Формально избыточность измеряют относительно энтропии источника: R = 1 − H/H_max, где H — фактическая энтропия, а H_max — максимально возможная при том же алфавите. Ноль означает, что каждый символ непредсказуем и сокращать нечего; значение 0,7 говорит, что семь десятых объёма не несут новой информации. Строгое определение меры дано в термине энтропия информации.

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

Сколько избыточности в реальных данных

Естественный язык избыточен в разы. Русский или английский текст несёт около 1–1,5 бита на букву против примерно 4,7 бита теоретического максимума для алфавита в 32 символа; избыточность оценивается в 70–75%. Отсюда два наблюдения. Первое: текстовые файлы уверенно сжимаются в три-четыре раза без потерь. Второе: человек читает фразу с выпавшими буквами и разбирает речь в шумном помещении именно за счёт этой избыточности — язык устроен помехоустойчиво, задолго до всякой теории кодирования.

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

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

Избыточность, которую добавляют намеренно

Шкала стоимости выглядит наглядно, если выстроить механизмы по доле проверочных данных:

• Контрольная цифра в товарном номере — один разряд из тринадцати, около 8%. Обнаруживает одиночную ошибку набора, не исправляет ничего.
• Бит чётности на байт — 12,5%. Обнаружение одиночной ошибки, слепота к двойной.
• CRC-32 на кадр в полторы тысячи байт — около 0,3%. Гарантированное обнаружение пакетов искажений, но без восстановления.
• Коды Рида — Соломона в QR — от 7% при уровне L до 30% при уровне H. Полное восстановление данных под грязью, царапиной или логотипом.
• Зеркалирование дисков — 100%. Полная копия ради мгновенного продолжения работы при отказе носителя.

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

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

Порядок операций: сначала сжать, потом защитить

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

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

В содержимом QR-кода эта логика видна на бытовом уровне. Сначала сокращают сам адрес — короткая ссылка убирает избыточность длинного адреса с параметрами. Затем выбирают уровень коррекции под условия размещения. Результат — символ меньшей версии с крупными модулями, который читается быстрее и с большего расстояния, чем длинный адрес при том же уровне защиты. Проверить, как меняется плотность символа, можно в генераторе QR-кодов.

Частые вопросы

Избыточность — это всегда плохо?

Нет, знак зависит от назначения. Паразитная избыточность увеличивает объём и стоимость хранения, и её убирают сжатием. Рассчитанная избыточность — единственный способ пережить искажения в канале без повторной передачи: на ней держатся QR-коды, память ECC, оптические диски и связь. Плохой является не избыточность как таковая, а несоответствие её доли реальным рискам — как избыток, так и недостаток.

Сколько избыточности в QR-коде?

От 7 до 30% кодовых слов символа в зависимости от выбранного уровня коррекции: L даёт примерно 7%, M — 15%, Q — 25%, H — 30%. Проценты считаются от общего числа кодовых слов, а не от площади рисунка, поэтому уровень H не означает, что можно закрасить треть символа: часть площади занята служебными зонами, повреждение которых критично независимо от уровня.

Почему нельзя сначала добавить коррекцию, а потом сжать?

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

Как избыточность связана с энтропией?

Напрямую: R = 1 − H/H_max, где H — энтропия источника, то есть среднее количество информации на символ, а H_max — максимум для того же алфавита при равновероятных символах. Чем предсказуемее данные, тем ниже энтропия и выше избыточность. Энтропия задаёт нижнюю границу сжатия без потерь: ниже неё сжать нельзя ни одним алгоритмом.

Зачем в документах дублируют сумму прописью?

Это избыточность, рассчитанная на человеческий канал. Цифровая запись уязвима к одиночной правке: приписанный ноль меняет сумму в десять раз и не бросается в глаза. Запись прописью использует другой алфавит и другую структуру, поэтому две записи расходятся при любой правке одной из них. Механизм тот же, что у контрольной цифры, только проверку выполняет не декодер, а читатель.