Універсальний код для цілих чисел в стисненні даних - префіксний код, який перетворює позитивні цілі числа в двійкові слова, з додатковим властивістю: при будь-якому істинному розподіл ймовірностей на цілих числах, поки розподіл - монотонно (тобто p (i) \ geq p (i +1) для будь-якого i ), Очікувані довжини двійкових слів знаходяться в межах постійного фактора очікуваних довжин, які оптимальний код призначив би для цього розподілу ймовірностей.

Універсальний код асимптотично оптимальний, якщо коефіцієнт між фактичними і оптимальними очікуваними довжинами пов'язує функція інформаційної ентропії коду, яка наближається до 1, так як ентропія наближається до нескінченності.

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

Універсальні коди включають в себе:

Деякі неуніверсальні коди:

Їх неуніверсальність проявляється в тому, що якщо будь-які з них використовувати, щоб закодувати розподіл Гауса-Кузьміна або дзета-розподіл з параметром s = 2, то очікувана довжина ключового слова нескінченний. Наприклад, використовуючи одномісне кодування на дзета-розподіл маємо наступну очікувану довжину


E (l) = \ frac {6} {\ pi ^ 2} \ sum_ {l = 1} ^ \ infty \ frac {1} {l} = \ infty. \,


Взаємозв'язок і практичне використання

Використання коду Хаффмана і арифметичного кодування (коли вони можуть використовуватися разом) дають кращий результат, ніж будь-який інший універсальний код.

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

Універсальні коди також корисні, коли код Хаффмана відпрацьовує не зовсім коректно. Наприклад, коли відправник знає ймовірності повідомлень, а одержувач немає, код Хаффмана вимагає передачі ймовірностей до одержувача. Використання універсального коду позбавляє від таких незручностей.

Кожен універсальний код дає власне "імпліцитне розподіл" ймовірностей p (i) = 2 - l (i), де l (i) - довжина i-го ключового слова та p (i) - ймовірність символу передачі. Якщо фактичні ймовірності повідомлення - q (i) і розбіжність Кульбака-Лейблера DKL (q | | p) мінімізує код з l (i), потім оптимальний код Хаффмана для цього безлічі повідомлень буде еквівалентний до цього коду. З тих пір, як універсальні коди стали працювати швидше, щоб кодувати і декодувати, ніж код Хаффмана, універсальний код був би кращий у випадках, де DKL (q | | p) досить маленький.

Для будь-якого геометричного розподілу кодування Голомба оптимально. З універсальними кодами, імпліцитне розподіл - приблизно енергетичний закон як наприклад 1 / n2. Для коду Фібоначчі, імпліцитне розподіл складає приблизно 1 / nq.