Вероятностная модель.
Это понятие очень важно при разработке статистических методов сжатия данных. Зачастую, алгоритм компрессии состоит из двух частей, вероятностной модели и непосредственно компрессора. Перед тем как приступить к сжатию очередного объекта (бита, байта, пиксела и т.п.), активируется вероятностная модель и вычисляется вероятность этого объекта. Эта вероятность и сам объект сообщаются компрессору, который использует полученную информацию при сжатии. Чем выше вероятность, тем лучше сжатие. Приведем пример простой модели для черно-белого изображения.

Каждый пиксел такого изображения - это один единственный бит. Предположим, что алгоритм уже прочитал и сжал 1000 пикселов и читает 1001-ый пиксел. Какова вероятность того, что пиксел будет черным? Модель может просто сосчитать число черных пикселов в уже прочитанном массиве данных. Если черных пикселов было 350, то модель приписывает 1001-ому пикселу вероятность 350/1000=0.35 быть черным. Эта вероятность вместе с пикселом (черным или белым) передаются компрессору. Главным моментом является то, что декодер может также легко вычислить вероятность 1001-ого пиксела. Слово алфавит означает множество символов в сжимаемых данных. Алфавит может состоять из двух символов, 0 и 1, из 128 символов ASCII, из 256 байтов по 8 бит в каждом или из любых других символов.

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

Те же, которые сжимаются плохо, являются случайными, а значит, неинтересными и неважными для нас. Мы не будем их сжимать, пересылать или хранить. Чудесные дни перед свадьбой сродни живому вступлению к скучной книге. — Уилсон Мизнер.