Определение

Алгоритм Хаффмана - это жадный алгоритм оптимального кодирования данных.

Каждый символ хранится в виде последовательности, состоящей из $0$ и $1$ , и занимает 8 бит памяти. Это называется кодированием фиксированной длины, потому что каждый символ занимает одинаковое количество битов.

Предположим, у нас есть текст. Как мы можем уменьшить количество памяти, требуемой для хранения одного символа?

Мы можем посчитать частоту каждого символа в тексте и, основываясь на этих данных, подбирать для каждого символа оптимальную последовательность битов.

Кодирование переменной длины - основная суть алгоритма Хаффмана.

Но, чтобы однозначно декодировать каждый символ, нужно соблюдать так называемое префиксное правило - каждый символ можно декодировать одним уникальным способом. Или по-другому - ни один код не является префиксом другого.

Принцип работы алгоритма

Кодирование Хаффмана основывается на создании бинарного дерева. Изначально все узлы являются листьями. Они представляют символ и его частоту. Также, при построении дерева, будут образовываться внутренние узлы, которые ссылаются на два узла наследников и содержат в себе их общую частоту. При обходе дерева бит $0$ - следование по левой ветви, $1$ - следование по правой ветви.

Описание алгоритма:

В очередь с приоритетами добавляем узел-лист, содержащий символ и его частоту
Пока в очереди больше одного листа, производим следующие операции:
1. Извлекаем из очереди два узла с наименьшей частотой (с высшим приоритетом)
2. Создаём новый узел - родитель двух извлечённых узлов. Он будет содержать в себе сумму частот его наследников.
3. Добавляем созданный узел в очередь
Последний узел в очереди - это корень дерева. Построение дерева окончено.

Графическое представление

Наши листья:

Создаём первый узел:

Второй узел:

Третий узел:

Финальный узел:

Результат работы алгоритма - дерево:

Коды для каждой из букв следующие: $A$ - 0, $B$ - 110, $C$ -100, $D$ - 101, $F$ - 111 Слово при кодировке алгоритмом Хаффмана: $FAD$ - 1110101.

Псевдокод

Функция построения дерева Хаффмана()
    ребра_дерева <- пустой_список
    свободные_узлы <- Приоритетная_очередь
    добавляем все узлы_листья в свободные узлы
    
    пока размер свободных_узлов > 1
        узел_1 <- извлекаем узел из очереди
        узел_2 <- извлекаем узел из очереди
        узел_родитель <- (частота узла_1 + частота узла_2,
                          данные узла_1 + данные узла_2)
                          
        добавляем в очередь узел_родитель

        добавляем ребро(данные_узла_родителя, 
                        данные_узла_1) в рёбра_дерева
                        
        добавляем ребро(данные_узла_родителя, 
                        данные_узла_2) в рёбра_дерева

Реализация на Python

Аннотация:
HaffmanTree - основной класс, представляющий дерево Хаффмана.
init - инициализатор класса, принимает словарь символов и их частот, строит дерево Хаффмана и определяет корень дерева.
letters - словарь символов и их частот.
_letters - внутреннее хранение словаря символов и их частот.
_tree - дерево Хаффмана, представленное в виде списка смежности.
_root - корень дерева Хаффмана.
_build_tree_haffman - метод для построения дерева Хаффмана.
edges_tree - список ребер дерева.
free_nodes - приоритетная очередь для узлов дерева.
encode_processing - метод для кодирования строки с использованием дерева Хаффмана.
word - строка, которую необходимо закодировать.
code - результат кодирования.
visited - список посещенных узлов.
start - начальный узел для поиска.
queue - очередь для поиска в ширину.
decode_processing - метод для декодирования строки, закодированной с использованием дерева Хаффмана.
row - строка, которую необходимо декодировать.
count - текущая позиция в строке.
result - результат декодирования.
letter - текущий узел дерева при декодировании.
get_all_codes - метод для получения всех кодов символов, используемых в дереве Хаффмана.
codes - словарь кодов для всех символов.

class HaffmanTree:  
    def __init__(self, letters: dict):  
        self._letters = letters  
        self._tree = self._build_tree_haffman()  
        self._root = self._get_root(self._tree)  

    def _build_tree_haffman(self):  
        edges_tree = list()  
        free_nodes = PriorityQueue()  
        for data, frequency in self._letters.items():  
            free_nodes.put((frequency, data))  
        while free_nodes.qsize() > 1:  
            left = free_nodes.get()  
            right = free_nodes.get()  
            parent = (left[0] + right[0], left[1] + right[1])  
            free_nodes.put(parent)  
            edges_tree.append(Edge(parent[1], left[1]))  
            edges_tree.append(Edge(parent[1], right[1]))  
        return self._tree_adjacency_list(edges_tree)  

    def encode_processing(self, word):  
        code, visited = str(), list()  
        start = self._root  
        queue = deque()  
        for letter in word:  
            queue.append(start)  
            while queue:  
                node = queue.popleft()  
                if node not in visited:  
                    code += self._encoding(node, letter, 
                                           self._tree)  
                    if node == letter:  
                        queue.clear(), visited.clear()  
                    else:  
                        queue += self._tree[node]  
                        visited.append(node)  
        return code  

    def decode_processing(self, row):  
        count, result = 0, str()  
        letter = self._root  
        while count < len(row):  
            digit = row[count]  
            if digit == '0':  
                letter = self._tree[letter][0]  
            else:  
                letter = self._tree[letter][1]  
            if len(letter) == 1:  
                result += letter  
                letter = self._root  
            count += 1  
        return result  

    def get_all_codes(self):  
        codes = dict()  
        for letter in self._letters:  
            codes[letter] = self.encode_processing(letter)  
        return codes

Олимпиадная реализация на С++

Аннотация:
HaffmanTree - основной класс, представляющий дерево Хаффмана.
HaffmanTree - конструктор класса, принимает вектор пар частот и символов, строит дерево Хаффмана и определяет корень дерева.
dict_letters - вектор пар, содержащий частоты и соответствующие символы.
encode - метод для кодирования строки с использованием дерева Хаффмана.
word - строка, которую необходимо закодировать.
code - результат кодирования.
visited - множество посещенных узлов.
start - начальный узел для поиска.
q - очередь для поиска в ширину.
decode - метод для декодирования строки, закодированной с использованием дерева Хаффмана.
row - строка, которую необходимо декодировать.
cnt - текущая позиция в строке.
res - результат декодирования.
let - текущий узел дерева при декодировании.
get_all_codes - метод для получения всех кодов символов, используемых в дереве Хаффмана.
codes - карта, содержащая коды для всех символов.
build_tree - метод для построения дерева Хаффмана.
edges - вектор ребер дерева.
pq - приоритетная очередь для узлов дерева.
letters - вектор пар, содержащий частоты и соответствующие символы.
tree - дерево Хаффмана, представленное в виде списка смежности.
root - корень дерева Хаффмана.
code - закодированная строка.
visited - множество посещенных узлов.
start - начальный узел для поиска.
q - очередь для поиска в ширину.
row - строка, которую необходимо декодировать.
cnt - текущая позиция в строке.
res - результат декодирования.
let - текущий узел дерева при декодировании.
codes - карта, содержащая коды для всех символов.
edges - вектор ребер дерева.
pq - приоритетная очередь узлов дерева.

typedef map<string, vector<string>> msvs;
typedef string str;
typedef pair<int, str> pis;

class HaffmanTree {
public:
  HaffmanTree(vector<pis> dict_letters) {
    letters = dict_letters;
    tree = build_tree();
    root = get_root(tree);
  }

  str encode(str word) {
    str code;
    set<str> visited;
    str start = root;
    deque<str> q;
    for (char letter : word) {
      q.push_back(start);
      while (!q.empty()) {
        str n = q.front();
        q.pop_front();
        if (visited.count(n) == 0) {
          code += encoding(n, letter, tree);
          if (n.size() == 1 and n.find(letter) != str::npos) {
            visited.clear();
            q.clear();
          }
          else {
            if (!tree[n].empty()) {
              q.push_back(tree[n][0]);
              q.push_back(tree[n][1]);
            }
            visited.insert(n);
          }
        }
      }
    }
    return code;
  }

  str decode(str row) {
    int cnt = 0;
    str res;
    str let = root;
    while (cnt < row.size()) {
      char digit = row[cnt];
      if (digit == '0') {
        let = tree[let][0];
      }
      else {
        let = tree[let][1];
      }
      if (let.size() == 1) {
        res += let;
        let = root;
      }
      cnt += 1;
    }
    return res;
  }

  map<str, str> get_all_codes() {
    map<str, str> codes;
    for (auto letter : letters) {
      codes[letter.second] = encode(letter.second);
    }
    return codes;
  }

private:
  vector<pis> letters;
  msvs tree;
  str root;

  msvs build_tree() {
    vector<Edge> edges;
    priority_queue<pis, vector<pis>, greater<pis>> pq;
    for (pis node : letters) {
      pq.push(node);
    }
    while (pq.size() > 1) {
      pis n1 = pq.top();
      pq.pop();

      pis n2 = pq.top();
      pq.pop();

      pis parent = { n1.first + n2.first, n1.second + n2.second };
      pq.push(parent);

      edges.push_back(Edge(parent.second, n1.second));
      edges.push_back(Edge(parent.second, n2.second));
    }
    return adj_list(edges);
  }

Продуктовая реализация на C++

Аннотация:
HaffmanTree - основной класс, представляющий дерево Хаффмана.
HaffmanTree - конструктор класса, принимает вектор пар частот и символов, строит дерево Хаффмана и определяет корень дерева.
dict_letters - вектор пар, содержащий частоты и соответствующие символы.
encode_processing - метод для кодирования строки с использованием дерева Хаффмана.
word - строка, которую необходимо закодировать.
code - результат кодирования.
visited - множество посещенных узлов.
start - начальный узел для поиска.
queue - очередь для поиска в ширину.
decode_processing - метод для декодирования строки, закодированной с использованием дерева Хаффмана.
row - строка, которую необходимо декодировать.
count - текущая позиция в строке.
result - результат декодирования.
letter - текущий узел дерева при декодировании.
get_all_codes - метод для получения всех кодов символов, используемых в дереве Хаффмана.
codes - карта, содержащая коды для всех символов.
build_haffman_tree - метод для построения дерева Хаффмана.
edges_tree - вектор ребер дерева.
free_nodes - приоритетная очередь для узлов дерева.

class HaffmanTree {
public:
    HaffmanTree(vector<pair<int, string>> dict_letters) {
        letters = dict_letters;
        tree = build_haffman_tree();
        root = get_root(tree);
    }

    string encode_processing(string word) {
        string code;
        set<string> visited;
        string start = root;
        deque<string> queue;
        for (char letter : word) {
            queue.push_back(start);
            while (!queue.empty()) {
                string node = queue.front();
                queue.pop_front();
                if (visited.count(node) == 0) {
                    code += encoding(node, letter, tree);
                    if (node.size() == 1 
                            and node.find(letter) != string::npos){
                        visited.clear();
                        queue.clear();
                    }
                    else {
                        if (!tree[node].empty()){
                            queue.push_back(tree[node][0]);
                            queue.push_back(tree[node][1]);
                        }
                        visited.insert(node);
                    }
                }
            }
        }
        return code;
    }

    string decode_processing(string row) {
        int count = 0;
        string result;
        string letter = root;
        while (count < row.size()) {
            char digit = row[count];
            if (digit == '0') {
                letter = tree[letter][0];
            }
            else {
                letter = tree[letter][1];
            }
            if (letter.size() == 1) {
                result += letter;
                letter = root;
            }
            count += 1;
        }
        return result;
    }

    map<string, string> get_all_codes() {
        map<string, string> codes;
        for (auto letter : letters) {
            codes[letter.second] = 
                encode_processing(letter.second);
        }
        return codes;
    }

private:
    vector<pair<int, string>> letters;
    map<string, vector<string>> tree;

    map<string, vector<string>> build_haffman_tree() {
        vector<Edge> edges_tree;
        priority_queue<pair<int, string>, 
                       vector<pair<int, string>>, 
                       greater<pair<int, string>>> free_nodes;
        for (pair<int, string> node : letters) {
            free_nodes.push(node);
        }
        while (free_nodes.size() > 1) {
            pair<int, string> node_1 = free_nodes.top();
            free_nodes.pop();
            pair<int, string> node_2 = free_nodes.top();
            free_nodes.pop();
            pair<int, string> parent = {node_1.first+node_2.first,
                                      node_1.second+node_2.second};
            free_nodes.push(parent);
            
            edges_tree.push_back(Edge(parent.second, 
                                      node_1.second));
            edges_tree.push_back(Edge(parent.second, 
                                      node_2.second));
        }
        return tree_adjacency_list(edges_tree);
    }
};

OpenEd