Префіксні коди

Так звані “префікси” можуть бути отримані шляхом послідовного викреслення останнього знаку кодової комбінації.

Приклад:

Для кодової комбінації 11101101 префіксами будуть 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

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

Код називається префіксним , якщо жодна з його комбінацій не є префіксом іншої комбінації того ж коду.

Частина кодової комбінації, що доповнює префікс до самої комбінації, називається суфіксом.

Префіксні коди наглядно можуть бути представлені з допомогою кодових дерев.

Якщо жоден вузол кодового дерева не є вершиною даного коду, то він володіє властивістю префікса.

Вузли дерева, що не з’єднуються з іншими, звуться кінечними. Комбінації, що їм відповідають, є кодовими комбінаціями префіксного коду.

Код Хаффмана. Належить до оптимальних нерівномірних кодів. Ідея цих кодів полягає в тому, щоб найбільш ймовірним символам первинного алфавіту відповідали найкоротші комбінації символів вторинного алфавіту. Код Хаффмана є префіксним.

Для побудови коду Хаффмана треба попарно з’єднувати символи, що кодуються і мають найменші ймовірності (враховуючи новоутворені символи, що мають сумарну ймовірність пари, з якої були утворені) до того часу, поки ймовірність чергової пари не буде дорівнювати одиниці.

Якщо кожній верхній гілці присвоїти значення 0, а нижній 1, то отримаємо комбінації коду Хаффмана.

Нехай, наприклад джерело інформації задане кінечною схемою (табл.1.):

Табл. 1.

а1

а2

а2

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а15

а16

1/64

3/64

8/64

1/64

4/64

1/64

4/64

3/64

10/64

1/64

3/64

8/64

1/64

1/64

3/64

12/64

Алгоритм побудови коду Хаффмана такий:

• Символи первинного алфавіту записують у стовпчик у порядку зменшення їх ймовірностей;

• Два останніх символи об’єднують в один із сумарною ймовірністю;

• З отриманих ймовірностей формують новий стовпчик в порядку зменшення ймовірностей;

• Процес продовжується до отримання однієї ймовірності, що дорівнює 1.

Табл. 2.

Символи

Ймовірності

а16

12/64

12/64

12/64

12/64

12/64

12/64

12/64

12/64

12/64

12/64

15/64

16/64

21/64

27/64

37/64

1

a9

10/64

10/64

10/64

10/64

10/64

10/64

10/64

10/64

10/64

11/64

12/64

15/64

16/64

21/64

27/64

a12

8/64

8/64

8/64

8/64

8/64

8/64

8/64

8/64

8/64

10/64

11/64

12/64

15/64

16/64

a3

8/64

8/64

8/64

8/64

8/64

8/64

8/64

8/64

8/64

8/64

10/64

11/64

12/64

а5

4/64

4/64

4/64

4/64

4/64

5/64

6/64

7/64

8/64

8/64

8/64

10/64

а7

4/64

4/64

4/64

4/64

4/64

4/64

5/64

6/64

7/64

8/64

8/64

а2

3/64

3/64

3/64

3/64

4/64

4/64

4/64

5/64

6/64

7/64

а8

3/64

3/64

3/64

3/64

3/64

4/64

4/64

4/64

5/64

а11

3/64

3/64

3/64

3/64

3/64

3/64

4/64

4/64

а15

3/64

3/64

3/64

3/64

3/64

3/64

3/64

а1

1/64

2/64

2/64

2/64

3/64

3/64

а4

1/64

1/64

2/64

2/64

2/64

а6

1/64

1/64

1/64

2/64

а10

1/64

1/64

1/64

а13

1/64

1/64

а14

1/64

• Будують кодове дерево (мал. 1 ):

• з точки, що відповідає ймовірності 1, проводять дві гілки;

• гілці з більшою ймовірністю присвоюють значення 1, гілці з меншою ймовірністю присвоюють значення 0;

• процес продовжують, поки гілки не дійдуть до кожного символу;

• рухаючись по гілці згори донизу, записують код кожного символу.

Мал.1. Кодове дерево ( для спрощення в кружечках вказаний тільки чисельник відповідної ймовірності, оскільки знаменники однакові )

Отримані кодові комбінації показані в табл. 3.

Табл. 3.

Символи первинного алфавіту	Ймовірності символів	Коди Хаффмана
а1	1/64	101111
а2	3/64	11111
а3	8/64	100
а4	1/64	101110
а5	4/64	1010
а6	1/64	101101
а7	4/64	0101
а8	3/64	11110
а9	10/64	110
а10	1/64	101100
а11	3/64	11101
а12	8/64	011
а13	1/64	111000
а14	1/64	111001
а15	3/64	0100
а16	12/64	00