DevDays
← Усі нотатки

Нотатка · Кодування

Код Хаффмана: як 160 біт перетворилися на 28

У Telegram:

Візьмемо повідомлення з двадцяти символів:

AAAAAAAAAAAAAABBBBCD

У звичайному текстовому файлі кожна латинська літера займає один байт — 8 біт. Отже, все повідомлення потребує 160 біт.

Але в нашому словнику є лише чотири символи: A, B, C і D. Нам не потрібна вся таблиця ASCII. Чотири символи можна позначити чотирма комбінаціями з двох бітів:

A = 00
B = 01
C = 10
D = 11

20 × 2 = 40 біт

Символи трапляються з різною частотою:

A — 14 разів, 70%
B —  4 рази, 20%
C —  1 раз,   5%
D —  1 раз,   5%

Тут і з’являється алгоритм Хаффмана. Він не вигадує короткі коди навмання, а щоразу об’єднує два найрідкісніші символи:

C 5% + D 5% = 10%
10% + B 20% = 30%
30% + A 70% = 100%

Так утворюється дерево. На кожному розгалуженні одному напрямку даємо 0, іншому — 1. Шлях від вершини дерева до символу стає його кодом:

A = 0
B = 10
C = 110
D = 111

Частий A опинився найближче до вершини й отримав один біт. До рідкісних C і D потрібно пройти три розгалуження, тому їхні коди довші.

Тут працює важливе правило: жоден код не повинен бути початком іншого. Інакше дані не вдасться однозначно прочитати.

Наприклад, такий словник був би поганим:

A = 0
B = 01
C = 1

Послідовність 01 можна прочитати як один символ B або як два символи A і C.

У правильному словнику все однозначно:

0 | 10 | 110 | 111
A | B  | C   | D

Рахуємо новий розмір:

A: 14 × 1 = 14 біт
B:  4 × 2 =  8 біт
C:  1 × 3 =  3 біти
D:  1 × 3 =  3 біти

Разом: 28 біт

Отримав 28 біт замість 40 — на 30% менше. Порівняно зі звичайним текстовим файлом на 160 біт економія становить 82,5%.

Формула Шеннона для такого розподілу дає приблизно 1,26 біта на символ, або близько 25 біт для всього повідомлення. Хаффман витратив 28, бо довжина кожного коду має бути цілою.

Для короткого повідомлення ще потрібно зберігати словник, і він може з’їсти всю економію. Але на мільярді символів різниця між двома й 1,4 біта на символ становить близько 75 мегабайтів. На трильйоні — вже 75 гігабайтів.

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

Ще нотатки