Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Сжатие без потерь информации

В системах сжатия без потерь декодер восстанавливает данные источника абсолютно точно, таким образом, структура системы сжатия выглядит следующим образом:

Вектор данных X ® Кодер ® B ( X ) ® Декодер ® X

Вектор данных источника X , подлежащих сжатию, представляет собой последовательность X = ( x 1 , x 2 ,… xn ) конечной длины. Отсчеты xi - составляющие вектора X - выбраны из конечного алфавита данных A . При этом размер вектора данных n ограничен, но он может быть сколь угодно большим. Таким образом, источник на своем выходе формирует в качестве данных X последовательность длиной n из алфавита A .

Выход кодера - сжатые данные, соответствующие входному вектору X, - представим в виде двоичной последовательности B ( X ) = ( b 1 , b 2 ,… bk ), размер которой k зависит от X . Назовем B ( X ) кодовым словом, присвоенным вектору X кодером (или кодовым словом, в которое вектор X преобразован кодером). Поскольку система сжатия - неразрушающая, одинаковым векторам Xl = Xm должны соответствовать одинаковые кодовые слова B ( Xl ) = = B ( Xm ).

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

размер данных источника в битах             n log 2 ( dim A ) (12)

r =                                                                                   =  ,

размер сжатых данных в битах                             k

где    dim A - размер алфавита данных A .

Таким образом, коэффициент сжатия r = 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r , тем лучше работает система сжатия данных.

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

R = k / n                                             ( 13)

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