ГЛАВА 1 СТАТИСТИЧЕСКИЕ МЕТОДЫСтатистические методы компрессии используют статистические свойства сжимаемых данных и присваивают всем символам коды с переменной длиной. Под «статистическими свойствами» обычно понимается вероятность (или, что то же самое, частота появления) каждого символа в потоке данных, однако этот термин может иметь иное, более сложное значение. Пару последовательных символов будем называть биграммой. Долгие наблюдения показали, что в типичном английском тексте некоторые биграммы, например, «ta», «he», «са», встречаются очень часто, а другие, например, «xa»,«hz», «qe», - редко. Поэтому разумный статистический метод может присваивать коды переменной длины многим биграммам (и даже триграммам), а не только индивидуальным символам. 1.1. ЭнтропияОсновы теории информации были заложены Клодом Шеноном в 1948 году в лаборатории Белла. Эта теория оказалась настоящим сюрпризом, поскольку все привыкли воспринимать информацию лишь качественно. Для наших целей сжатия данных нам необходимо освоить только одно теоретико-информационное понятие, а именно, энтропию. Под энтропией символа Если символы некоторого алфавита с символами от С помощью понятия энтропии теория информации показывает, как вычислять вероятности строк символов алфавита, и предсказывает ее наилучшее сжатие, то есть, наименьшее, в среднем, число бит, необходимое для представления этой строки символов. Продемонстрируем это на простом примере. Для последовательности символов «ABCDE» с вероятностями 0.5, 0.2, 0.1, 0.1 и 0.1, соответственно, вероятность строки «AAAAABBCDE» равна Пример: Проанализируем энтропию алфавита, состоящего всего из двух символов
Табл. 1.1. Вероятности и энтропии двух символов.
|