huffman.md

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

Алгоритм Хаффмана - это алгоритм для построения префиксных кодов, который используется для сжатия данных. Он назван в честь Дэвида А. Хаффмана, который предложил его в 1952 году.

Основная идея алгоритма заключается в том, чтобы присвоить каждому символу строки код, который будет как можно короче, если этот символ часто встречается, и как можно длиннее, если этот символ редко встречается. Таким образом, мы можем сжать строку, используя меньше бит для хранения часто встречающихся символов.

Чтобы создать код Хаффмана для строки, нужно следующее:

1. Посчитайте частоту каждого символа в строке.

2. Создайте дерево кодирования, используя следующий процесс:

   1. Создайте листья дерева для каждого символа

   2. Выберите два узла с наименьшей частотой, создайте новый узел с частотой, равной сумме частот этих двух узлов, и сделайте эти два узла дочерними узлами этого нового узла.

   3. Повторяйте шаг 2, пока не останется один узел - корень дерева

3. Выберите два узла с наименьшей частотой, создайте новый узел с частотой, равной сумме частот этих двух узлов, и сделайте эти два узла дочерними узлами этого нового узла.

4. Повторяйте шаг 3, пока не останется один узел - корень дерева.

5. Для каждого символа вычислите его код, начиная с корня дерева и переходя к листу, соответствующему этому символу. Если вы переходите от корня к левому дочернему узлу, добавьте "0" к коду символа. Если вы переходите от корня к правому дочернему узлу, добавьте "1" к коду символа.

Например, для строки "abbabcbbaa" будут следующие частоты символов:

a: 5 раз

b: 5 раз

Дерево кодирования будет выглядеть следующим образом:

    *
   / \
  a   b
 / \ / \
a  b b  a

Итоговые коды для строки "abbabcbbaa" будут следующими:

a: 0

b: 1

Это означает, что строка "abbabcbbaa" может быть сжата в следующую форму:

0 0 1 1 0 1 1 0 1 0 0

Чтобы распаковать сжатую строку, нужно просто начать с корня дерева кодирования и следовать по дереву, добавляя символ к результирующей строке при достижении листа.

Например, чтобы распаковать сжатую строку "0 0 1 1 0 1 1 0 1 0 0", нужно следовать следующему пути:

1. Начинаем с корня дерева.
2. Поскольку первый символ - "0", мы переходим к левому дочернему узлу. Добавляем символ "a" к результирующей строке.
3. Поскольку второй символ - "0", мы переходим опять к левому дочернему узлу. Добавляем символ "a" к результирующей строке.
4. Поскольку третий символ - "1", мы переходим к правому дочернему узлу. Добавляем символ "b" к результирующей строке.
5. Поскольку четвертый символ - "1", мы переходим к правому дочернему узлу. Добавляем символ "b" к результирующей строке.
6. Поскольку пятый символ - "0", мы переходим к левому дочернему узлу. Добавляем символ "a" к результирующей строке.

и так далее

---

Вот пример реализации алгоритма Хаффмана на JavaScript:

function huffman(text) {
  // Строим таблицу частот символов
  const frequencyTable = {};
  for (const char of text) {
    if (frequencyTable[char]) {
      frequencyTable[char]++;
    } else {
      frequencyTable[char] = 1;
    }
  }

  // Строим дерево кодирования
  const nodes = [];
  for (const char in frequencyTable) {
    nodes.push({ char, frequency: frequencyTable[char] });
  }
  while (nodes.length > 1) {
    // Сортируем узлы по частоте
    nodes.sort((a, b) => a.frequency - b.frequency);

    // Создаем новый узел, являющийся суммой двух минимальных узлов
    const left = nodes.shift();
    const right = nodes.shift();
    const parent = {
      char: null,
      frequency: left.frequency + right.frequency,
      left,
      right,
    };
    nodes.push(parent);
  }

  // Генерируем коды для каждого символа
  const codes = {};
  function generateCodes(node, code) {
    if (node.char !== null) {
      codes[node.char] = code;
    } else {
      generateCodes(node.left, code + '0');
      generateCodes(node.right, code + '1');
    }
  }
  generateCodes(nodes[0], '');

  // Кодируем текст
  let encodedText = '';
  for (const char of text) {
    encodedText += codes[char];
  }

  return { encodedText, tree: nodes[0] };
}

Чтобы использовать эту реализацию, нужно вызвать функцию huffman с текстом, который нужно закодировать.

---

Чтобы сравнить два дерева в процентном соотношении, нужно сравнивать их узлы по очереди, начиная с корневых узлов. Если узлы равны (то есть содержат одинаковый символ и частоту его появления), то сравниваем их потомков. Если узлы различаются, то увеличиваем счетчик различий. После того, как оба дерева будут пройдены, вычисляем процент совпадения как (количество совпадающих узлов) / (общее количество узлов). Например:

function compareTrees(tree1, tree2) {
  let count = 0;
  let total = 0;

  function compareNodes(node1, node2) {
    total++;
    if (node1.char === node2.char && node1.frequency === node2.frequency) {
      count++;
      if (node1.left && node2.left) {
        compareNodes(node1.left, node2.left);
      }
      if (node1.right && node2.right) {
        compareNodes(node1.right, node2.right);
      }
    }
  }

  compareNodes(tree1, tree2);
  return (count / total) * 100;
}

const percentage = compareTrees(tree1, tree2);

Где tree1 и tree2 - объекты, представляющие деревья. Функция compareTrees вернет число.

---

Чтобы раскодировать текст, нужно будет сохранить построенное дерево и использовать его для поиска символа по его коду. Например:

function decode(encodedText, tree) {
  let decodedText = '';
  let node = tree;
  for (const char of encodedText) {
    if (char === '0') {
      node = node.left;
    } else {
      node = node.right;
    }
    if (node.char !== null) {
      decodedText += node.char;
      node = tree;
    }
  }
  return decodedText;
}

const decodedText = decode(encodedText, huffmanTree);

Где huffmanTree - это объект, возвращаемый функцией huffman в качестве второго аргумента.