Дерево Хаффмана

Відносно простий метод стиснення даних виконується шляхом створення так званих дерев Хаффмана для файлу, після чого дерево використовується для стиснення та розпаковки даних. Зазвичай використовують бінарні дерева Хаффмана (тобто кожен вузол — або лист, або має точнісінько два підвузли). Проте, можна будувати і дерева Хаффмана із довільною кількістю піддерев (наприклад, трійкові, або загальніше — $N$-арні дерева).

Дерево Хаффмана для файлу з $Z$ різними символами має $Z$ листків. Шлях від кореня до листка, який позначає певний символ, визначає його кодування; кожен крок шляху задає символ коду (який може бути $0$, $1$, ..., N-1). Розташовуючи часті символи ближче до кореня, а рідкісні — далі, досягається кращий ступінь стиснення. Точніше, дерево буде деревом Хаффмана лише якщо кодуванням використовується мінімальна кількість $N$-арних символів для кодування всього файлу.

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

Нижче на рисунку зображено приклад трійкового дерева Хаффмана. Символи 'a' та 'e' кодуються одним трійковим символом; менш часті символи 's' та 'p' — двома; а найрідкісніші 'x', 'q' і 'y' — трьома трійковими символами кожен.

Очевидно, якщо згодом потрібно декодувати послідовність $N$-арних символів, важливо знати, яке дерево використано для стиснення. Це можна зробити кількома способами. У цій задачі використовується такий метод: перед даними розміщується заголовок, що містить коди $Z$ символів у лексикографічному порядку.

Знаючи число вхідних символів $Z$, арність дерева $N$ і заголовок, відновіть відображення символів у закодовані рядки.