Введение

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

Но чтобы говорить о сжатии информации необходимо сначала понять, за счет чего в принципе возможно сжатие конечных цифровых последовательностей? Чтобы показать принцип кодирования (сжатия) информации, который положен в основу всех современных кодеров сжатия без потерь, рассмотрим такой простой пример:

000011112222333555566666.

Теперь подряд идущие цифры заменим парой <эзначение, количество>, получим:

041424335465

и получаем сокращение исходной последовательности в 2 раза (24/12).

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

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

Рассмотрим более подробно, сначала, первый методы на примере кодирования по Хаффману.