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

Повне пояснення

Коротке пояснення

Алгоритм Хаффмана генерує коди для символів, використовуючи бінарне дерево: частіші символи отримують короткі коди, рідкісні — довгі. Це дозволяє зменшити загальну кількість бітів, необхідних для представлення тексту.

Аналогія

Уявіть, що ви створюєте інструкції для пошуку предметів у бібліотеці: найпопулярніші книги отримують короткі, прості позначки (наприклад, «A»), а рідкісні — довші послідовності (наприклад, «ABCD»). Це економить місце на полицях.

Коли застосовувати

• При стисненні тексту, де частоти символів різняться (наприклад, англійський текст).
• Коли потрібна швидка декодування без додаткових метаданих.
• У системах, де обмежений простір пам’яті (мобільні пристрої).
• У форматах файлів, що підтримують власний код (наприклад, JPEG).
• Коли важлива швидкість передачі даних.

Кроки алгоритму

1. Підрахувати частоти кожного символу у вхідному тексті.
2. Створити пріоритетну чергу (min‑heap) з вузлів, кожен з яких містить символ і його частоту.
3. Повторно об’єднувати два вузли з найменшими частотами, створюючи новий вузол‑корінь.
4. Присвоїти лівому піддереву біт 0, правому — біт 1.
5. Повторювати кроки 3–4, доки не залишиться один вузол (корінь дерева).
6. Пройти дерево, збираючи коди для кожного символу.
7. Замінити символи у тексті їхніми кодами, отримавши стиснутий рядок.

Візуальна інтуїція (текстова)

Текст:  A B C D
Частоти: 5 2 1 1

Heap:
[ (C,1), (D,1), (B,2), (A,5) ]

Об’єднуємо C і D → X(2)
Heap: [ (X,2), (B,2), (A,5) ]

Об’єднуємо X і B → Y(4)
Heap: [ (Y,4), (A,5) ]

Об’єднуємо Y і A → корінь Z(9)
Коди: A=0, B=10, C=110, D=111

Складність

• Час: O(n log n), де n – кількість унікальних символів (підрахунок частот O(n), побудова дерева O(n log n)).
• Пам’ять: O(n) для зберігання частот і дерева.

Код (js)

// 1. Підрахунок частот символів
function countFrequencies(text) {
  const freq = new Map(); // зберігаємо частоти
  for (const ch of text) {
    freq.set(ch, (freq.get(ch) || 0) + 1); // збільшуємо лічильник
  }
  return freq;
}

// 2. Створення вузла дерева
class Node {
  constructor(freq, char = null, left = null, right = null) {
    this.freq = freq;   // частота
    this.char = char;   // символ (null для внутрішніх вузлів)
    this.left = left;
    this.right = right;
  }
}

// 3. Пріоритетна черга (min‑heap) для вузлів
class MinHeap {
  constructor() { this.heap = []; }
  // вставка вузла
  push(node) {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }
  // видалення вузла з найменшою частотою
  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown(0);
    }
    return min;
  }
  bubbleUp(idx) {
    const element = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (element.freq >= parent.freq) break;
      this.heap[idx] = parent; // переміщуємо батька вниз
      idx = parentIdx;
    }
    this.heap[idx] = element; // вставляємо елемент
  }
  bubbleDown(idx) {
    const length = this.heap.length;
    const element = this.heap[idx];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let swap = null;

      if (leftIdx < length) {
        const left = this.heap[leftIdx];
        if (left.freq < element.freq) swap = leftIdx;
      }

      if (rightIdx < length) {
        const right = this.heap[rightIdx];
        if ((swap === null && right.freq < element.freq) || (swap !== null && right.freq < this.heap[swap].freq)) {
          swap = rightIdx;
        }
      }

      if (swap === null) break;
      this.heap[idx] = this.heap[swap];
      idx = swap;
    }
    this.heap[idx] = element;
  }
}

// 4. Побудова дерева Хаффмана
function buildHuffmanTree(freqMap) {
  const heap = new MinHeap();
  // створюємо листові вузли
  for (const [ch, f] of freqMap.entries()) {
    heap.push(new Node(f, ch));
  }

  // об’єднуємо вузли до одного кореня
  while (heap.heap.length > 1) {
    const left = heap.pop();
    const right = heap.pop();
    const merged = new Node(left.freq + right.freq, null, left, right);
    heap.push(merged);
  }

  return heap.pop(); // корінь дерева
}

// 5. Генерація кодів для символів
function generateCodes(node, prefix = '', codes = {}) {
  if (!node) return;
  // якщо листовий вузол, зберігаємо код
  if (node.char !== null) {
    codes[node.char] = prefix;
    return;
  }
  generateCodes(node.left, prefix + '0', codes); // лівий біт 0
  generateCodes(node.right, prefix + '1', codes); // правий біт 1
}

// 6. Стиснення тексту
function huffmanEncode(text) {
  const freqMap = countFrequencies(text);
  const treeRoot = buildHuffmanTree(freqMap);
  const codes = {};
  generateCodes(treeRoot, '', codes);

  let encoded = '';
  for (const ch of text) {
    encoded += codes[ch];
  }

  return { encoded, codes };
}

// Тестовий приклад
const input = 'this is an example for huffman encoding';
const result = huffmanEncode(input);
console.log(result.encoded); // очікуваний результат: стиснений рядок
console.log(result.codes);   // очікуваний результат: об’єкт з кодами символів

Типові помилки і поради

1. Не враховувати пробіли – вони теж символи, їх частота важлива.
2. Використовувати об’єкт замість Map – при великій кількості символів це знижує швидкість.
3. Не об’єднувати вузли, коли в черзі лише один – це призведе до помилки.
4. Забувати про корінь дерева – без нього коди не будуть сформовані.
5. Не зберігати коди у вигляді рядків – використання масивів бітів зменшить пам’ять.

Перевір себе

1. Яка частота символу визначає його позицію у дереві Хаффмана?
2. Чому рідкісні символи отримують довші коди?