Алгоритм Хаффмана. Сжатие данных на JavaScript

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

Алгоритм Хаффмана в JavaScript реализуется следующим образом:

1. Создание частотной таблицы:

function buildFrequencyTable(str) {
  const frequencyTable = {};
  for (const char of str) {
    if (!frequencyTable[char]) {
      frequencyTable[char] = 0;
    }
    frequencyTable[char]++;
  }
  return frequencyTable;
}

Эта функция получает строку в качестве входных данных и создает частотную таблицу, где ключи являются символами, а значения – их количество в строке.

2. Создание дерева кодирования:

function buildEncodingTree(frequencyTable) {
  const priorityQueue = new PriorityQueue();
  for (const char in frequencyTable) {
    priorityQueue.enqueue(char, frequencyTable[char]);
  }
  while (priorityQueue.size() > 1) {
    const left = priorityQueue.dequeue();
    const right = priorityQueue.dequeue();
    const parent = new TreeNode(null, left.frequency + right.frequency);
    parent.left = left.node;
    parent.right = right.node;
    priorityQueue.enqueue(parent, parent.frequency);
  }
  return priorityQueue.dequeue().node;
}

Эта функция получает частотную таблицу и создает дерево кодирования с помощью приоритетной очереди. Для каждого символа в таблице частоты создается узел дерева и добавляется в очередь с приоритетом, равным часте его вхождения в текст. После этого, в каждой итерации узлы с наименьшими приоритетами вынимаются из очереди и объединяются в один узел, у которого частота является суммой частот узлов-родителей. Это повторяется, пока в очереди не останется только один узел, который и является корнем дерева кодирования.

3. Кодирование:

function buildEncodingMap(encodingTree, encodingMap = {}, prefix = '') {
  if (!encodingTree.left && !encodingTree.right) {
    encodingMap[encodingTree.value] = prefix;
  } else {
    buildEncodingMap(encodingTree.left, encodingMap, prefix + '0');
    buildEncodingMap(encodingTree.right, encodingMap, prefix + '1');
  }
  return encodingMap;
}

Эта функция получает дерево кодирования и создает таблицу кодирования, где ключи являются символами, а значения – соответствующие им битовые последовательности. Это делается с помощью рекурсивного обхода дерева. Каждый узел, который является листом, добавляется в таблицу кодирования. Если узел не является листом, функция рекурсивно вызывается для его потомков, добавляя к префиксу “0” для левого потомка и “1” для правого.

4. Декодирование:

function decode(encodedMessage, encodingTree) {
  let currentNode = encodingTree;
  let decodedMessage = '';

  for (let i = 0; i < encodedMessage.length; i++) {
    if (encodedMessage[i] === '0') {
      currentNode = currentNode.left;
    } else {
      currentNode = currentNode.right;
    }

    if (!currentNode.left && !currentNode.right) {
      decodedMessage += currentNode.value;
      currentNode = encodingTree;
    }
  }

  return decodedMessage;
}

Эта функция получает закодированное сообщение и дерево кодирования. Затем она использует дерево кодирования для декодирования закодированного сообщения. Для этого она проходит по дереву, используя значения “0” или “1” в закодированном сообщении для определения, в какой узел должен перейти. Когда узел является листом, это означает, что мы достигли символа, который должен быть добавлен в декодированное сообщение. После этго текущий узел возвращается к корню дерева, и декодирование продолжается.

Весь код:

const Node = function(value, frequency) {
  this.value = value;
  this.frequency = frequency;
  this.left = null;
  this.right = null;
};

function createEncodingTree(frequencies) {
  let nodes = [];
  for (let value in frequencies) {
    nodes.push(new Node(value, frequencies[value]));
  }

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.frequency - b.frequency);

    let left = nodes.shift();
    let right = nodes.shift();

    let parent = new Node(null, left.frequency + right.frequency);
    parent.left = left;
    parent.right = right;

    nodes.push(parent);
  }

  return nodes[0];
}

function encode(message, encodingTree) {
  let encoding = {};
  buildEncoding(encodingTree, '', encoding);

  let encodedMessage = '';
  for (let i = 0; i < message.length; i++) {
    encodedMessage += encoding[message[i]];
  }

  return encodedMessage;
}

function buildEncoding(node, prefix, encoding) {
  if (!node.left && !node.right) {
    encoding[node.value] = prefix;
    return;
  }

  buildEncoding(node.left, prefix + '0', encoding);
  buildEncoding(node.right, prefix + '1', encoding);
}

function decode(encodedMessage, encodingTree) {
  let currentNode = encodingTree;
  let decodedMessage = '';

  for (let i = 0; i < encodedMessage.length; i++) {
    if (encodedMessage[i] === '0') {
      currentNode = currentNode.left;
    } else {
      currentNode = currentNode.right;
    }

    if (!currentNode.left && !currentNode.right) {
      decodedMessage += currentNode.value;
      currentNode = encodingTree;
    }
  }

  return decodedMessage;
}

Этот код реализует весь алгоритм Хаффмана. Первым шагом является создание узлов с частотами символов в сообщении. Затем они сортируются и объединяются в дерево. Окончательный результат – это таблица кодов для каждого символа, которые состоят из нулей и единиц, указывающих путь от корня дерева до узла с соответствующим символом. Сообщение может быть сжато, используя эту таблицу кодов для кодирования каждого символа.

Важно отметить, что алгоритм Хаффмана является одним из базовых алгоритмов для понимания технологии кодирования Хаффмана, которая используется в широком спектре приложений, таких как передача данных по сети, сжатие аудио и видео файлов, и многое другое.

Другие похожие алгоритмы: алгоритм Шеннона-Фано, алгоритм Лемпеля-Зива.