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

Префіксний код в теорії кодування — код зі словом змінної довжини, що має таку властивість (виконання умови Фано): якщо в код входить слово a, то для будь-якого непорожнього рядка b слова ab в коді не існує. Хоча префіксний код складається зі слів різної довжини, ці слова можна записувати без розділового символу.

Наприклад, код, що складається з слів 0, 10 і 11, є префіксним, і повідомлення 01001101110 можна розбити на слова єдиним чином:

0 10 0 11 0 11 10 

Код, що складається з слів 0, 10, 11 і 100, префіксним не є, і те саме повідомлення можна трактувати декількома способами.

0 10 0 11 0 11 10 
0 100 11 0 11 10 

Визначення

Так звані «префікси» можуть бути отримані шляхом послідовного відкидання останнього знаку кодової комбінації. Наприклад, для кодової комбінації 11101101 префіксами будуть 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

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

Приклади

Будь-який код зі словом фіксованої довжини, очевидно, є префіксним. Розглянемо декілька нетривіальних прикладів.

• Телефонні номери в стаціонарних мережах.
• UTF-8.
• Код Хаффмана, що застосовується для стискування даних.
• Синтаксис Паскаля та інших мов з LL (1)-синтаксисом (якщо вважати символом лексему, а словом — оператор). Тому для визначення типу оператора транслятору Паскаля не доводиться повертати лічені символи в потік, або запам'ятовувати їх в стеку.

Код Морзе не є префіксним. У нього, крім крапки і тире, входить також символ-розділювач — пауза довжиною з тире.

Див. також

• Нерівність Крафта - Макміллана