14.1. Алгоритм Хаффмана и оптимальное кэширование

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

Алгоритм Хаффмана (Huffman, 1952) — один из самых известных алгоритмов сжатия текста. Пусть дан текст, состоящий из символов алфавита $\Sigma$, который мы хотим закодировать как можно более короткой последовательностью бит.

Префиксные коды

Самый простой способ — кодировать каждый символ уникальной последовательностью из $k$ бит (будем называть такую последовательность кодовым словом (codeword)), где $2^{k} \geqslant|\Sigma|$ (чтобы такое кодирование вообще было возможно). Такой способ не всегда эффективен: например, пусть $\Sigma=\{a, b, c, d\}$, текст имеет длину 10000, но большая часть символов текста равна $a$ (скажем, $a$ встречается в тексте 7000 раз, а остальные символы по 1000 раз). Тогда вышеописанный способ кодирования потребует $20000$ бит. Если же кодовое слово символа $a$ будет равно $0$, символа $b$ — $10$, $c$ — $110$, $d$ — $111$, то суммарно потребуется лишь $7000 \cdot 1+1000 \cdot 2+1000 \cdot 3+1000 \cdot 3=15000$ бит.

Итак, иногда оказывается выгодным использовать кодовые слова разной длины для разных символов. Заметим, что при этом нельзя использовать одновременно кодовые слова, одно из которых является префиксом другого: в этом случае нельзя будет понять, где в закодированной последовательности бит заканчивается одно кодовое слово и начинается следующее.

Какой префиксный код будет оптимальным для данного текста $t$? Пусть $\operatorname{cnt}(t, a)$ — количество вхождений символа $a$ в текст (будем называть это количество частотой), $\operatorname{len}(C, a)$ — длина кодового слова символа $a$ в префиксном коде $C$. Тогда количество бит, которое понадобится для того, чтобы закодировать текст $t$ кодом $C$, равняется

Мы хотим найти префиксный код $C$, минимизирующий $L(C, t)$.

Связь с двоичными деревьями

Любому префиксному коду можно сопоставить двоичное дерево: кодовые слова будут соответствовать листьям дерева; для того, чтобы по листу получить кодовое слово, нужно пройти по пути из корня в этот лист и выписывать 0 при спуске в левого ребёнка, 1 — при спуске в правого.

В дереве оптимального префиксного кода ни у какой вершины не может быть ровно один ребёнок: такую вершину можно просто удалить, поставив её ребёнка на её место; при этом новое дерево будет всё ещё соответствовать префиксному коду, но длина некоторых кодовых слов уменьшится.

Префиксный код и соответствующее ему двоичное дерево

Жадный алгоритм

Пусть $C$ — такой оптимальный код, $a$ и $b$ — два самых редких символа в $t$; они находятся в листьях $v, u$ с общим родителем $w$. Введём новый символ $c$ и рассмотрим текст $t_{1}$, полученный из $t$ заменой всех вхождений $a$ и $b$ на $c$. Также рассмотрим префиксный код $C_{1}$, соответствующий дереву кода $C$, из которого удалили $v$ и $u$, а в ставшую листом вершину $w$ поместили символ $c$. Заметим, что $L(C, t)=L\left(C_{1}, t_{1}\right)+\operatorname{cnt}(t, a)+\operatorname{cnt}(t, b)$.

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

Реализация

Будем хранить символы в очереди с приоритетами: приоритет символа равен его частоте. Пока в очереди больше одного символа, будем доставать из очереди два символа $a, b$ с минимальными приоритетами $\operatorname{cnt}_{a}, \operatorname{cnt}_{b}$, и складывать в очередь новый символ $c$ с приоритетом $\operatorname{cnt}_{c}=\operatorname{cnt}_{a}+\operatorname{cnt}_{b}$. В этот момент будем подвешивать вершины, соответствующие символам $a$ и $b$, детьми к вершине, соответствующей символу $c$. В конце в очереди останется только один символ; вершина, соответствующая этому символу, будет корнем дерева оптимального префиксного кода. Получаем время работы $O(|\Sigma| \log |\Sigma|)$ (если считать, что частоты символов уже предподсчитаны).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import heapq

def huffman(cnt: list[int]):
    """
    cnt[i] — частота символа i (символы пронумерованы от 0 до n-1).
    Возвращает (root, left, right) — корень и массивы левых/правых детей.
    """
    n = len(cnt)
    freq = list(cnt) + [0] * (n - 1)
    left  = [-1] * (2 * n)
    right = [-1] * (2 * n)

    # (частота, id вершины)
    heap = [(cnt[i], i) for i in range(n)]
    heapq.heapify(heap)

    c = n  # id следующей внутренней вершины
    while len(heap) > 1:
        ca, a = heapq.heappop(heap)
        cb, b = heapq.heappop(heap)
        freq[c] = ca + cb
        left[c], right[c] = a, b
        heapq.heappush(heap, (freq[c], c))
        c += 1

    root = heap[0][1]
    return root, left, right

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <queue>
#include <vector>
using namespace std;

// cnt[i] — частота символа i (символы 0..n-1)
// Возвращает корень; left[v] и right[v] — дети вершины v (-1 если лист)
int huffman(vector<int> cnt,
            vector<int>& left, vector<int>& right) {
    int n = cnt.size();
    cnt.resize(2 * n, 0);
    left.assign(2 * n, -1);
    right.assign(2 * n, -1);

    using P = pair<int, int>;  // (частота, id)
    priority_queue<P, vector<P>, greater<P>> q;
    for (int i = 0; i < n; i++)
        q.push({cnt[i], i});

    int c = n;
    while (q.size() > 1) {
        auto [ca, a] = q.top(); q.pop();
        auto [cb, b] = q.top(); q.pop();
        cnt[c] = ca + cb;
        left[c] = a;  right[c] = b;
        q.push({cnt[c], c});
        c++;
    }
    return q.top().second;  // корень дерева
}

Оптимальное кэширование

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

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

Заметим, что по любому алгоритму можно построить его «ленивую» версию, которая записывает элемент в кэш только тогда, когда сразу после этого он будет запрошен. При этом она делает не больше операций записи, чем исходный алгоритм; количество операций записи для неё совпадает с количеством кэш-промахов.

Алгоритм Белади

Реализация

Для реализации алгоритма Белади нужно знать будущее: для каждого элемента $d_i$ необходимо заранее предподсчитать следующий индекс его использования. Это делает алгоритм неприменимым на практике, но полезным как теоретический эталон для сравнения.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def belady(requests: list[int], k: int) -> int:
    """
    requests: последовательность запросов d[0..m-1]
    k: размер кэша
    Возвращает число кэш-промахов.
    """
    m = len(requests)
    # Предподсчитываем следующее вхождение для каждой позиции
    future = [float('inf')] * m
    last: dict[int, int] = {}
    for i in range(m - 1, -1, -1):
        x = requests[i]
        if x in last:
            future[i] = last[x]
        last[x] = i

    cache: dict[int, float] = {}  # элемент → следующее использование
    misses = 0

    for i, x in enumerate(requests):
        if x in cache:
            cache[x] = future[i]
        else:
            misses += 1
            if len(cache) == k:
                # вытесняем элемент, который понадобится позже всех
                evict = max(cache, key=lambda e: cache[e])
                del cache[evict]
            cache[x] = future[i]

    return misses

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <map>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int belady(vector<int>& req, int k) {
    int m = req.size();

    // Предподсчитываем следующее вхождение для каждой позиции
    vector<int> fut(m, INT_MAX);
    map<int, int> last;
    for (int i = m - 1; i >= 0; i--) {
        if (last.count(req[i])) fut[i] = last[req[i]];
        last[req[i]] = i;
    }

    map<int, int> cache;  // элемент → следующее использование
    int misses = 0;

    for (int i = 0; i < m; i++) {
        int x = req[i];
        if (cache.count(x)) {
            cache[x] = fut[i];
        } else {
            misses++;
            if ((int)cache.size() == k) {
                // вытесняем элемент, который понадобится позже всех
                auto evict = max_element(cache.begin(), cache.end(),
                    [](auto& a, auto& b){ return a.second < b.second; });
                cache.erase(evict);
            }
            cache[x] = fut[i];
        }
    }
    return misses;
}