3.2  Елементи теорії префіксних множин

 

Префіксною множиною S називається скінченна множина двійкових слів, в якій жодна з послідовностей не є префіксом (початком) ніякої іншої.

Якщо S={w1, w2, …, wk} – префіксна множина, то можна визначити вектор (S)=(L1, L2, …, Lk), що складається із значень довжин відповідних префіксних послідовностей у неспадному порядку. Цей вектор називається вектором Крафта, для якого виконується нерівність Крафта:

 

.                                  (2.1)

 

Для вектора Крафта справедливе таке твердження: якщо S - префіксна множина, то (S) - вектор Крафта.

Якщо нерівність (2.1) переходить в строгу рівність, то такий код називається компактним і має найменшу серед кодів з даним алфавітом довжину, тобто є оптимальним.

Приклади префіксних множин і відповідних їм векторів Крафта: S1={0, 10, 11} (S1)=(1, 2, 2); S2={0, 10, 110, 111} (S2)=(1, 2, 3, 3); S3={0, 10, 110, 1110, 1111} (S3)=(1, 2, 3, 4, 4); S4={0, 10, 1100, 1101, 1110, 1111} (S4)={1, 2, 4, 4, 4, 4};  S5={0, 10, 1100, 1101, 1110, 11110, 11111} (S5)=(1, 2, 4, 4, 4, 5, 5); S6={0, 10, 1100, 1101, 1110, 11110, 111110, 111111} (S6)=(1, 2, 4, 4, 4, 5, 6, 6).

Припустимо, використовується код без пам'яті для стиснення вектора даних x=(x1, x2, …, xn) з алфавітом А об'ємом k символів.

Позначимо через F=(F1, F2, …, Fk) вектор частот символів алфавіту А в повідомленні X.

Кодування повідомлення кодом без пам'яті здійснюється у такий спосіб:

складається список символів алфавіту A: a1, a2, …, ak у порядку спадання їх частот появи в X;

кожному символу аj призначається кодове слово wj з префіксної множини S двійкових послідовностей, для якої вектор Крафта (S)=(L1, L2, …, Lk);

виходом кодера є об'єднання в одну послідовність усіх отриманих кодових слів.

Тоді довжина кодової послідовності на виході кодера джерела інформації становить

 

L(X)=LF=L1F1+ L2F2+…+ LkFk.                         (2.2)

 

Оптимальним є префіксний код, для якого добуток LF мінімальний: LF min.