4.2. Теорема кодирования источников. Неравенство Крафта. Префиксный код.
Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника:
Для
любого дискретного источника без памяти
X
с конечным алфавитом и энтропией H(X)
существует D-ичный
префиксный код, в котором средняя длинна
кодового слова
,
удовлетворяет неравенству:
В префиксном коде никакое кодовое слово не является префиксом другого кодового слова. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д.
Из
теоремы Шеннона следует, что тем ближе
к энтропии источника, тем более эффективно
кодирование. В идеальном случае, когда
,
код называют эффективным.
Эффективность кода оценивается величиной:
.
Если средняя длина =min, то код является оптимальным.
Теорема кодирования источников доказывается с использованием неравенства Крафта:
Для существования однозначно декодируемого D-ичного кода, содержащего k кодовых слов с длинами n1,n2,…,nk, необходимо и достаточно, чтобы выполнялось неравенство Крафта:
4.3. Методы оптимального кодирования. Сжатие данных.
Процедуру оптимального кодирования часто называют сжатием данных.
Таким образом задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимального кодирования. На практике используют два вида сжатия (кодирования):
1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя.
2. Сжатие с потерями – устранение избыточности информации, которое приводит к безвозвратной потере некоторой доли информации, но это не является принципиальным для восстановления информации в интересах пользователя.
Сжатие без потерь наиболее применимо к числовым и текстовым данным. Применительно к вычислительной технике сжатие позволяет уменьшить количество бит, необходимых для хранения и передачи заданной информации, что дает возможность передавать сообщения более быстро и хранить более экономно. Программы-архиваторы различных форматов данных ZIP, ARJ и др. работают на принципах и методах сжатия данных.
Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов XX века) мало использовалась в компьютерной технике.
Методы (алгоритмы) сжатия данных без потерь можно разделить на:
1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др. Они базируются на априорной информации о статистике (вероятностях появления) букв алфавита. Это главный недостаток таких кодов, так как статистика символов заранее неизвестна и эффективному кодированию должен предшествовать частотный анализ (анализ частоты появления символов в сообщении).
2.Адаптивные методы. Например, модифицированное кодирование Хаффмана, арифметическое кодирование. Здесь распределение вероятностей символов вначале считается равномерным на заданном интервале, а потом оно меняется во времени по мере накопления статистики.
3.Динамические методы (алгоритмы). Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела-Зива. LZ77 …LZW.