ГЛАВА 1 СТАТИСТИЧЕСКИЕ МЕТОДЫ

Статистические методы компрессии используют статистические свойства сжимаемых данных и присваивают всем символам коды с переменной длиной. Под «статистическими свойствами» обычно понимается вероятность (или, что то же самое, частота появления) каждого символа в потоке данных, однако этот термин может иметь иное, более сложное значение. Пару последовательных символов будем называть биграммой. Долгие наблюдения показали, что в типичном английском тексте некоторые биграммы, например, «ta», «he», «са», встречаются очень часто, а другие, например, «xa»,«hz», «qe», - редко. Поэтому разумный статистический метод может присваивать коды переменной длины многим биграммам (и даже триграммам), а не только индивидуальным символам.

1.1. Энтропия

Основы теории информации были заложены Клодом Шеноном в 1948 году в лаборатории Белла. Эта теория оказалась настоящим сюрпризом, поскольку все привыкли воспринимать информацию лишь качественно. Для наших целей сжатия данных нам необходимо освоить только одно теоретико-информационное понятие, а именно, энтропию. Под энтропией символа , имеющего вероятность , подразумевается количество информации, содержащейся в , которая равна - . Например, если вероятность  символа  равна 0.5, то его энтропия - .

Если символы некоторого алфавита с символами от  до  имеют вероятности от  до , то энтропия всего алфавита равна сумме . Если задана строка символов этого алфавита, то для нее энтропия определяется аналогично.

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

Продемонстрируем это на простом примере. Для последовательности символов «ABCDE» с вероятностями 0.5, 0.2, 0.1, 0.1 и 0.1, соответственно, вероятность строки «AAAAABBCDE» равна . Логарифм по основанию 2 этого числа . Тогда наименьшее в среднем число требуемых бит для кодирования этой строки равно - , то есть, 20. Кодер, достигающий этого сжатия называется энтропийным кодером.

Пример: Проанализируем энтропию алфавита, состоящего всего из двух символов  и  с вероятностями  и . Поскольку , то энтропия этого алфавита выражается числом . В табл. 1.1 приведены различные значения величин  и  вместе с соответствующей энтропией. Когда , необходим по крайней мере один бит для кодирования каждого символа. Это означает, что энтропия достигла своего максимума, избыточность равна нулю, и данные невозможно сжать. Однако, если вероятности символов сильно отличаются, то минимальное число требуемых бит на символ снижается. Мы, скорее всего, не сможем непосредственно предъявить метод сжатия, который использует 0.08 бит на символ, но мы точно знаем, что при  такой алгоритм теоретически возможен.

Табл. 1.1. Вероятности и энтропии двух символов.