Алгоритм стиснення коду Хаффмана

Кодування Хаффмана (також відоме як кодування Хаффмана) – це алгоритм стиснення даних, який формує основну ідею стиснення файлів. У цьому пості розповідається про кодування з фіксованою і змінною довжиною, унікально декодовані коди, правила префіксів і побудову дерева Хаффмана.

Огляд

Ми вже знаємо, що кожен символ є послідовністю 0's і 1's і зберігається з використанням 8-біт. Це відомо як "кодування з фіксованою довжиною", оскільки кожен символ використовує однакову кількість фіксованих біт пам'яті.

Враховуючи текст, як зменшити кількість місця, яка потрібна для зберігання символу?

Ідея полягає в тому, щоб використовувати "кодування змінної довжини". Ми можемо використовувати той факт, що одні символи зустрічаються в тексті частіше, ніж інші для розробки алгоритму, який може представляти той же фрагмент тексту, використовуючи меншу кількість бітів. При кодуванні зі змінною довжиною ми присвоюємо символам змінну кількість бітів залежно від частоти в даному тексті. Таким чином, деякі символи можуть зрештою займати один біт, а деякі - два біти, деякі можуть бути закодовані з використанням трьох бітів і так далі. Проблема з кодуванням змінної довжини полягає у його декодуванні.

З огляду на послідовність бітів, як її однозначно декодувати?

Розглянемо рядок aabacdab. Воно має 8 символів у ньому та використовує 64-бітове сховище (з використанням кодування фіксованої довжини). Якщо взяти до уваги, що частота символів a, b, c і d знаходяться 4, 2, 1, 1, відповідно.Спробуємо уявити aabacdab використовуючи меншу кількість бітів, використовуючи той факт, що a зустрічається частіше, ніж b, а також зустрічається частіше, ніж c і d. Почнемо з випадкового присвоєння однобітового коду 0 до a , 2-бітний код 11 до b , і 3-бітний код 100 і 011 до персонажів c і d відповідно.

Отже, рядок aabacdab буде закодований у 00110100011011 (0|0|11|0|100|011|0|11) використовуючи наведені вище коди. Але справжня проблема полягає у розшифровці. Якщо ми спробуємо декодувати рядок 00110100011011, це призведе до неоднозначності, оскільки його можна декодувати,

0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
…
and so on

Щоб запобігти двозначності при декодуванні, ми забезпечимо відповідність нашого кодування "правилу префікса", що призведе до "кодів, що унікально декодуються". Правило префікса свідчить, що жоден код не є префіксом іншого коду. Під кодом ми маємо на увазі біти, які використовуються для певного символу. У наведеному вище прикладі 0 є префіксом 011 що порушує правило префікса. Якщо наші коди задовольняють префіксне правило, декодування буде однозначним (і навпаки).

Давайте знову розглянемо наведений вище приклад. На цей раз ми присвоюємо символам коди, які відповідають правилу префіксу. 'a', 'b', 'c', а також 'd'.

Використовуючи наведені вище коди, рядок aabacdab буде закодований 00100110111010 (0|0|10|0|110|111|0|10) . Тепер ми можемо однозначно декодувати 00100110111010 повернутися до нашого вихідного рядка aabacdab.

Тепер, коли ми розібралися з кодуванням змінної довжини та правилом префіксів, поговоримо про кодування Хаффмана.

Кодування Хаффмана

Техніка працює, створюючи бінарне дерево вузлів.Вузол може бути листовим або внутрішнім вузлом. Спочатку всі вузли є листовими вузлами, які містять сам персонаж, вагу (частоту появи) персонажа. Внутрішні вузли містять вагу символів та посилання на два дочірні вузли. За загальною угодою, біт 0 представляє наступний лівий дочірній елемент, і трохи 1 представляє наступний правильний дитина. Готове дерево має n листові вузли та n-1 внутрішні вузли. Рекомендується, щоб дерево Хаффмана відкидало символи, що не використовуються в тексті, щоб отримати найбільш оптимальну довжину коду.

Ми будемо використовувати пріоритетну чергу для побудови дерева Хаффмана, де вузол із найменшою частотою має найвищий пріоритет. Нижче наведено повні кроки:

1. Створіть кінцевий вузол для кожного символу та додайте їх у чергу пріоритетів.

2. Поки в queue більше одного вузла:

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

3. Вузол, що залишився, є кореневим вузлом, і дерево завершене.

Розглянемо деякий текст, що складається тільки з 'A', 'B', 'C', 'D', а також 'E' символів, а їх частота 15, 7, 6, 6, 5 відповідно. Наступні малюнки ілюструють кроки, за якими слідує алгоритм:

Шлях від кореня до будь-якого кінцевого вузла зберігає оптимальний код префікса (також званий кодом Хаффмана), що відповідає символу, пов'язаному з цим кінцевим вузлом.

Реалізація

Нижче наведено реалізацію алгоритму стиснення коду Хаффмана на C++, Java та Python:

Алгоритм Хаффмана

Один із перших алгоритмів ефективного кодування інформації був запропонований Хаффманом у 1952 р.Цей алгоритм став базою великої кількості програм стиснення інформації. Наприклад, кодування за Хаффманом використовується в програмах стиснення. ARJ, ZIP, RAR, в алгоритмі стиснення графічних зображень із втратами JPEG, а також вбудовано у сучасні факс-апарати. Ефективне кодування за Хаффманом полягає у поданні найбільш ймовірних (часто зустрічаються) букв двійковими кодами найменшої довжини, а менш ймовірних - кодами більшої довжини (якщо всі кодові слова меншої довжини вже вичерпані). Це робиться таким чином, щоб середня довжина коду на літеру вихідного повідомлення була мінімальною. До початку кодування повинні бути відомі ймовірності появи кожної літери, з яких складатиметься повідомлення. З цієї таблиці ймовірностей будується кодове дерево Хаффмана, з допомогою якого виробляється кодування букв.

Побудова кодового дерева Хаффмана

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

Лист дерева - Вузол, з якого нс виходить жодної дуги. У парс

вузлів дерева, з'єднаних між собою дугою, тог, з якого вона виходить, називається батьком, інший - дитиною.

Два вузли називаються братами, якщо мають одного й того ж батька.

Двійкове дерево - Дерево, у якого з усіх вузлів, крім листя, виходить рівно по дві дуги.

Дерево кодування Хаффмана – двійкове дерево, у якого кожен вузол має вага, і при цьому вага батька дорівнює сумарній вазі його дітей. Алгоритм побудови дерева кодування Хаффмана такий:

• 1. Літери вхідного алфавіту утворюють перелік вільних вузлів майбутнього дерева кодування.Кожен вузол у цьому списку має вагу, що дорівнює ймовірності появи відповідної літери в повідомленні.
• 2. Вибираються два вільні вузли дерева з найменшими вагами. Якщо є більше двох вільних вузлів з найменшою вагою, то можна брати будь-яку пару.
• 3. Створюється їхній батько з вагою, що дорівнює їх сумарній вазі.
• 4. Батько додається до списку вільних вузлів, а двоє дітей видаляються з цього списку.
• 5. Однією дузі, що виходить із вузла-батька, ставиться у відповідність біт 1, інший - 0.
• 6. Пункти 2, 3, 4, 5 повторюються доти, доки у списку вільних вузлів не залишиться лише один вузол. Цей вузол буде коренем дерева. Його вага виходить рівною одиниці - сумарної ймовірності всіх букв повідомлення.

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

Наприклад розглянемо побудову дерева кодування Хаффмана наведеного в табл. 10.1 алфавіту із восьми букв.

Побудову дерева починаємо зі списку листя (рис. 10.2) та виконуємо по кроках.

Мал. 10.2. Список вільних вузлів-листя

На першому кроці з листя дерева вибираються два з найменшою вагою - z₇ та zg. Вони приєднуються до вузла-батька, вага якого встановлюється в 0,04 + 0,02 = 0,06. Потім вузли z₇ і z₈ видаляються зі списку вільних. Вузол z₇ відповідає гілки 0 батька, вузол z₈ - Гілки 1. Дерево кодування після першого кроку наведено на рис. 10.3.

Мал. 10.3. Дерево кодування Хаффмана після першого кроку

На другому етапі «найлегшою» парою виявляється лист Zb та вільний вузол (г₇ + z₈). Для них створиться батько з вагою 0,16. Вузол Zb відповідає гілки 0 батька, вузол (г₇ + zg) - гілки 1. На цьому кроці дерево кодування наведено на рис.10.4.

Мал. 10.4. Дерево кодування Хаффмана після другого кроку

На третьому етапі найменші можливості мають zs, z*, Zj та вільний вузол (zb + Zi + z.g). Таким чином, на цьому кроці можна створити батька для z$ і (Zb + г₇ + г₈) з вагою 0,26, отримавши у своїй дерево кодування, представлене на рис. 10.5. Зверніть увагу, що у цій ситуації можливі кілька варіантів з'єднання вузлів із найменшими вагами. При цьому всі такі варіанти будуть правильними, хоча і можуть призвести до різних наборів кодів, які, втім, володітимуть однаковою ефективністю для заданого розподілу ймовірностей.

Мал. 10.5. Дерево кодування Хаффмана після третього кроку

На четвертому кроці «найлегшою» парою виявляється листя ц та 24- Дерево кодування Хаффмана наведено на рис. 10.6.

Мал. 10.6. Дерево кодування Хаффмана після четвертого кроку

Мал. 10.7. Дерево кодування Хаффмана після п'ятого кроку

Мал. 10.8. Дерево кодування Хаффмана після шостого кроку

На п'ятому кроці вибираємо вузли з найменшою вагою 0,22 і 0,20. Дерево кодування Хаффмана після п'ятого кроку наведено на рис. 10.7.

На шостому кроці залишається три вільні вузли з вагами 0,42, 0,32 і 0,26. Вибираємо найменші ваги 0,32 і 0,26. Дерево кодування Хаффмана після шостого кроку наведено на рис. 10.8.

На сьомому кроці залишається об'єднати дві вільні вершини, що залишилися, після чого отримуємо остаточне дерево кодування Хаффмана, наведене на рис. 10.9.

Мал. 10.9. Остаточне дерево кодування Хаффмана

З побудованого дерева букви представляються кодами, що відбивають шлях від кореневого вузла до листа, відповідного потрібної букве. У розглянутому прикладі літери вхідного алфавіту кодуються, як показано в табл. 10.2.

Мал. 10.10. Альтернативний варіант дерева кодування Хаффмана

Видно, що найімовірніші літери закодовані найкоротшими кодами, а найрідкісніші - кодами більшої довжини, причому коди побудовані таким чином, що жодна кодова комбінація нс збігається з початком довшої комбінації. Це дозволяє однозначно декодувати повідомлення без використання розділових символів.

Для заданих у табл. 10.1 можливостей можна побудувати й інші правильні варіанти кодового дерева Хаффмана. Одне з допустимих дерев наведено на рис. 10.10. Коди літер вхідного алфавіту для цього кодового дерева наведено у табл. 10.3.

З табл. 10.3 видно, що коди також вийшли префіксними, і вірогідним літерам відповідають найбільш короткі коди.

Код Хаффмана

Алгоритм Хаффмана - Адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений в 1952 аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні ним курсової роботи. В даний час використовується в багатьох програмах стиснення даних.

На відміну від алгоритму Шеннона-Фано, алгоритм Хаффмана залишається завжди оптимальним і для вторинних алфавітів m₂ з більш ніж двома символами.

Цей метод кодування складається з двох основних етапів:

1. Побудова оптимального кодового дерева.
2. Побудова відображення код символ на основі побудованого дерева.

Кодування Хаффмана

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

Класичний алгоритм Хаффмана на вході отримує таблицю частот народження символів у повідомленні. Далі виходячи з цієї таблиці будується дерево кодування Хаффмана (Н-дерево). [1]

1. Символи вхідного алфавіту утворюють перелік вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількості входжень символу в повідомлення, що стискається.
2. Вибираються два вільні вузли дерева з найменшими вагами.
3. Створюється їхній батько з вагою, що дорівнює їх сумарній вазі.
4. Батько додається до списку вільних вузлів, а два його нащадки видаляються з цього списку.
5. Однією дузі, що виходить із батька, ставиться у відповідність біт 1, інший - біт 0.
6. Кроки, починаючи з другого, повторюються доти, доки у списку вільних вузлів не залишиться лише один вільний вузол. Він і вважатиметься коренем дерева.

Допустимо, у нас є наступна таблиця частот:

Цей процес можна представити як побудову дерева, корінь якого - символ із сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з останнього кроку, n₀ нащадків - символи з попереднього кроку і т.д.

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

Для цієї таблиці символів коди Хаффмана будуть виглядати так.

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

У цьому загальна довжина повідомлення, що з наведених у таблиці символів, становитиме 87 біт (загалом 2,2308 біта на символ). З використанням рівномірного кодування загальна довжина повідомлення становила б 117 біт (рівно 3 біта на символ). Зауважимо, що ентропія джерела, незалежно породжує символи із зазначеними частотами становить ~2,1858 біта на символ, тобто. надмірність побудованого для такого джерела коду Хаффмана, яка розуміється, як відмінність середньої кількості біт на символ від ентропії, становить менше 0,05 біт на символ.

Класичний алгоритм Хаффмана має низку істотних недоліків. По-перше, для відновлення вмісту стисненого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стисненого повідомлення збільшується на довжину таблиці частот, яка повинна посилатися попереду даних, що може звести нанівець всі зусилля зі стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів за повідомленням: одного для побудови моделі повідомлення (таблиці частот та Н-дерева), іншого для власне кодування. По-друге, надмірність кодування звертається в нуль лише в тих випадках, коли ймовірності символів, що кодуються, є зворотними ступенями числа 2.По-третє, для джерела з ентропією, яка не перевищує 1 (наприклад, для двійкового джерела), безпосереднє застосування коду Хаффмана безглуздо.

Адаптивний стиск

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

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

Оновлення дерева під час читання чергового символу повідомлення складається з двох операцій.

Перша – збільшення ваги вузлів дерева. Спочатку збільшуємо вагу листа, що відповідає ліченому символу, на одиницю. Потім збільшуємо вагу батька, щоб привести його у відповідність до нових значень ваги нащадків. Цей процес триває доти, доки ми не дістанемося до кореня дерева. Середня кількість операцій збільшення ваги дорівнює середній кількості бітів, необхідних для того, щоб закодувати символ.

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

Щоб зберегти впорядкованість дерева кодування, алгоритм працює в такий спосіб. Нехай нова збільшена вага вузла дорівнює W+1. Тоді починаємо рухатися по списку у бік збільшення ваги, поки не знайдемо останній вузол з вагою W. Переставимо поточний і знайдений вузли між собою у списку, відновлюючи таким чином порядок у дереві (при цьому батьки кожного вузла теж зміняться). У цьому операція перестановки закінчується.

Після перестановки операція збільшення ваги вузлів продовжується далі. Наступний вузол, вага якого буде збільшено алгоритмом, - це новий батько вузла, збільшення ваги якого викликало перестановку.

Переповнення

У процесі роботи алгоритму стиснення вага вузлів у дереві кодування Хаффмана неухильно зростає. Перша проблема виникає тоді, коли вага кореня дерева починає перевершувати місткість осередку, в якому він зберігається. Як правило, це 16-бітове значення і, отже, не може бути більше, ніж 65535. Друга проблема, що заслуговує ще більшої уваги, може виникнути значно раніше, коли розмір найдовшого коду Хаффмана перевершує місткість комірки, яка використовується для того, щоб передати його у вихідний потік. Декодер все одно, який довжини код він декодує, оскільки він рухається зверху вниз по дереву кодування, вибираючи з вхідного потоку по одному біту. Кодер повинен починати від листа дерева і рухатися вгору до кореня, збираючи біти, які потрібно передати. Зазвичай це відбувається з змінної типу «ціле», і, коли довжина коду Хаффмана перевершує розмір типу «ціле» у бітах, настає переповнення.

Можна довести, що максимальну довжину код Хаффмана для повідомлень з тим самим вхідним алфавітом буде мати, якщо частоти символів утворює послідовність Фібоначчі.Повідомлення з частотами символів, рівними числам Фібоначчі до Fib (18), - це чудовий спосіб протестувати роботу програми стиснення Хаффману.

Масштабування ваг вузлів дерева Хаффмана

Зважаючи на сказане вище, алгоритм оновлення дерева Хаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти його на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно «масштабувати» вагу, зазвичай розділивши вагу листя на ціле число, наприклад, 2, а потім перерахувавши вагу всіх інших вузлів.

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

Правильно організоване дерево Хаффмана після масштабування може мати форму, що значно відрізняється від вихідної. Це тому, що масштабування призводить до втрати точності нашої статистики. Але зі збиранням нової статистики наслідки цих «помилок» практично сходять нанівець. Масштабування ваги – досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але оскільки необхідність у ній виникає відносно рідко, то з цим можна змиритися.

Виграш від масштабування

Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж масштабування відкладалося.Це можна пояснити тим, що поточні символи потоку, що стискається, більше «схожі» на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу «давніх» символів на статистику та збільшення впливу на неї «недавніх» символів. Це дуже складно виміряти кількісно, ​​але, в принципі, масштабування позитивно впливає на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиснення будь-яких типів інформації.

Застосування

Стиснення даних по Хаффману застосовується при стисканні фото- та відеозображень (JPEG, стандарти стиснення MPEG), в архіваторах (PKZIP, LZH та ін), протоколах передачі даних MNP5 і MNP7.

Примітки

Література

• Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Рівест, Кліффорд Штайн. Алгоритми: побудова та аналіз = Introduction to Algorithms. - 2-ге вид. - М.: Вільямс, 2006. - 1296 с. - ISBN 0-07-013151-1
• Д. Селомон. Стиснення даних, зображення та звуку. - М.: Техносфера, 2004. - 368 с. - 3000 прим. - ISBN 5-94836-027-X
• Ананій В. Левітін. Глава 9. Жадібні методи: Алгоритм Хаффмана // Алгоритми: введення у розробку та аналіз = Introduction to The Design and Analysis of Aigorithms. - М.: Вільямс, 2006. - С. 392-398. - ISBN 0-201-74395-7

Посилання

• Теорія кодування
• Стиснення даних
• Алгоритми стиску без втрат
• Завдання, що вирішуються жадібним алгоритмом

Wikimedia Foundation. 2010 .

Корисне

Дивитись що таке "Код Хаффмана" в інших словниках:

• код Хаффмана — Префіксний код, в якому довжина слова, що кодує, назад пропорційна зустрічальності кодованого елемента. [Е.С.Алексєєв, А.А.Мячов. Англо-російський тлумачний словник з системотехніки ЕОМ. Москва 1993] Тематики інформаційні технології загалом… … Довідник технічного перекладача
• Код Хаффмена — Алгоритм Хаффмана (англ. Huffman) — адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений 1952 року доктором Массачусетського технологічного інституту Девідом Хаффманом. В даний час ... Вікіпедія
• Код — Цей термін має й інші значення, див. Код (значення). Код правило (алгоритм) зіставлення кожному конкретному повідомленню строго певної комбінації символів (знаків) (або сигналів). Кодом також називається окрема… … Вікіпедія
• код з мінімальною надмірністю — Як правило, це означає код, побудований за процедурою Хаффмана; у загальному випадку "оптимальний" код з точки зору середньої довжини кодового слова, складність реалізації кодування не ... Довідник технічного перекладача
• Код Шеннона-Фано — Алгоритм Шеннона Фано один із перших алгоритмів стиснення, який вперше сформулювали американські вчені Шеннон та Фано. Даний метод стиснення має велику подібність до алгоритму Хаффмана, який з'явився на кілька років пізніше. Алгоритм… … Вікіпедія
• Кодування Хаффмана — Алгоритм Хаффмана (англ. Huffman) — адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений 1952 року доктором Массачусетського технологічного інституту Девідом Хаффманом. В даний час ... Вікіпедія
• Універсальний код (стиснення даних) — Універсальний код для цілих чисел у стисканні даних префіксний код, який перетворює позитивні цілі числа на двійкові слова, з додатковою властивістю: за будь-якого справжнього розподілу ймовірностей на цілих числах, доки поширення … … Вікіпедія
• Універсальний код — для цілих чисел у стисканні даних префіксний код, який перетворює позитивні цілі числа на двійкові слова, з додатковою властивістю: за будь-якого справжнього розподілу ймовірностей на цілих числах, доки розподіл монотонний… … Вікіпедія
• Префіксний код — Цю статтю слід вікіфікувати. Будь ласка, оформіть її згідно з правилами оформлення статей. Префіксний код у теорії кодування код зі словом змінної довжини, що має таке … Вікіпедія
• Експонентний код Голомба — порядку k – це універсальний код, параметризований цілим числом k. Для кодування невід'ємного числа в експоненційний код Голомбу порядку k можна використовувати наступний метод: Взяти число N у двійковому коді, без останніх k цифр.