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

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

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

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

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

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

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

_{r =                                                                                   =  ,}

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

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

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

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

R = k / n                                             ( 13)

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