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

1. Принцип роботи

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

Етапи роботи алгоритму

1. Підрахунок частоти символів.

2. Побудова дерева Хаффмана.

3. Формування кодів Хаффмана.

4. Кодування повідомлення.

5. Декодування.

2. Приклад кодування

Припустимо, що маємо текст: 'ABRACADABRA'.

Обчислення частоти символів:

A - 5
B - 2
R - 2
C - 1
D – 1

Побудова дерева:

Об'єднуємо C (1) та D (1) → новий вузол CD (2).

Об'єднуємо CD (2) та B (2) → новий вузол BCD (4).

Об'єднуємо R (2) та A (5) → новий вузол RA (7).

Об'єднуємо BCD (4) та RA (7) → кореневий вузол (11).

Призначення кодів:

A - 1
B - 010
R - 00
C - 0110
D - 0111

Закодоване повідомлення:

A B R A C A D A B R A
1 010 00 1 0110 1 0111 1 010 00 1

3. Переваги та недоліки

✅ Переваги:

• Ефективне стиснення даних.
• Простий у реалізації.
• Використовує мінімальну кількість бітів для передачі інформації.

❌ Недоліки:

• Потребує додаткових даних для побудови дерева при декодуванні.
• Малоефективний для дуже коротких повідомлень.
• Не підходить для потокового стиснення.

4. Використання

- Стиснення файлів (ZIP, JPEG, MP3).

- Передача даних у телекомунікаціях.

- Оптимізація пам’яті в базах даних.

5. Стиснення зображень:

• Використовується в форматах JPEG для стиснення фотографій, що дозволяє зменшити обсяг файлів без значних втрат якості.

Відео стиснення:

• Застосовується в стандартах MPEG для стиснення відео, що робить передачу і зберігання відеоінформації більш ефективними.

Архіватори:

• Алгоритм Хаффмана є частиною багатьох програм для архівування даних, таких як PKZIP і LZH, що забезпечує ефективне стиснення файлів.

Передача даних:

• Використовується в протоколах передачі даних, таких як MNP5 і MNP7, для оптимізації обсягу переданих даних12.

Системи без втрат:

• Алгоритм Хаффмана застосовується в різних системах стиснення без втрат, що дозволяє відновлювати оригінальні дані без жодних втрат12.

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