§ Принцип компрессии

Очень много времени я пытался разобраться с этим кодом, но вот пришло время его понять и, когда я его понял, теперь смогу рассказать о том, что из себя представляет этот код, как его найти и насколько хорошо он сжимает.
Идея кода Хаффмана заключается в том, чтобы кодировать более короткими последовательностями битов наиболее часто встречающиеся символы, а более длинными — те, что реже. Для того, чтобы составить код Хаффмана, потребуется знание того, с какой частотой встречает символ. Если такая частота у всех символов одинаковая, то код Хаффмана ничего не сожмет, вообще, так что применять этот код надо только там, где разность частот существенная.
Например в слове ABBBBBBABAC буква А встречается 3 раза, буква C - 1 раз и буква B - аж 7 раз. Зададим такие последовательности:
  • B - 0
  • A - 10
  • C - 11
Код Хаффмана - префиксный, это значит, что любой код не является префиксом другого кода, и потому однозначно кодируется все его коды. Например код 0 не является префиксом к 10 и 11, как и 10 и 11 не могут быть префиксами 0.
Теперь закодируем последовательность ABBBBBBABAC в биты:
A  B B B B B B A  B A  C
10 0 0 0 0 0 0 10 0 10 11
Тем самым образом, всего потребовалось 15 бит, или 1*7 (B) + 2*1 (C) + 2*3 (A) = 15 бит.
Если бы на каждый символ выделялось по 2 бита, то общее количество бит составило бы (7+1+3)*2 = 22 бита. Как видим, есть компрессия!

§ Формирование кода

Для того, чтобы сформировать код Хаффмана, необходимо создать дерево, которое делается следующим алгоритмом.
  • Сортируется массив по частоте встречи символов
  • Выбираются 2 самых наименьших по частоте
  • Суммируются их частоты
  • Из массива удаляются 2 наименьших, вместо него устанавливается новый, но этот элемент имеет два потомка
  • Повторяется до тех пор, пока не останется 1 элемент
Этот самый элемент будет иметь два потомка. Допустим, левый потомок это 0, правый это 1.
По итогу, получится дерево, обходя которое, можно найти код Хаффмана. Понимаю, что текстом ничего неясно, так что буду сейчас это дело иллюстрировать на примере.
Есть первичный набор данных, уже отсортированный по частоте
 A  B C D E F G
14 10 7 3 2 2 1
То есть, A встречается 25 раз, B - 10 раз и так далее.
Наименьшее из них будет F и G. Складываем 2+1 и получается новое число 3
 A  B C D E F G
14 10 7 3 2 2 1
            \ /
             3
Теперь уже нельзя учитывать F и G, ищем наименьшее из оставшихся. Здесь получается первая неопределенность. Наименьшим будет число 2 и 3, но какой из 3 выбрать? Я выберу тот, который находится левее, то есть, выберу D и E:
 A  B C D E F G
14 10 7 3 2 2 1
        \ / \ /
         5   3
Складываем 3+2 и получаем 5, и соответственно, выкидывается D и E из проверки. Теперь у нас остался набор 25,10,7,5 и 3. Наименьшими двумя будут числа 5 и 3.
 A  B C D E F G
14 10 7 3 2 2 1
        \ / \ /
         5   3
          \ /
           8
Складываем 5+3=8, итого, остались числа 25,10,7,8. Опять, наименьшее из них будет 7 и 8.
 A  B C D E F G
14 10 7 3 2 2 1
      \ \ / \ /
       \ 5   3
        \ \ /
         \ 8
          \/
          15
Собственно, 7+8=15. Остались только 14,10 и 15. Здесь же наименьшими будут 10 и 14:
 A  B C D E F G
14 10 7 3 2 2 1
 \  / \ \ / \ /
  \/   \ 5   3
  24    \ \ /
         \ 8
          \/
          15
И на этом получается, что все, остались 24 и 15, их и соединяем общим и единственным родителем:
 A  B C D E F G
14 10 7 3 2 2 1
 \  / \ \ / \ /
  \/   \ 5   3
  24    \ \ /
   \     \ 8
    \     \/
     \    15
      \  /
       39
Этот родитель будет содержать общее число букв, как можно это заметить.
Итак, дерево было построено. А как теперь найти код каждого символа? Это просто. Нужно, идя от корня, поворачивать либо налево (пишем 0), либо направо (пишем 1), и тем самым образом, дойти до нужного символа.
  • Начнем с А. Чтобы достичь А из корня, нужно сначала повернуть налево (0), потом снова налево (0), итого, А кодируется как
00.
  • Теперь B. Поворачиваем налево, а потом направо, код 01
  • Буква С, теперь идем направо, потом сразу налево, код 10
  • D, направо, направо, налево, налево, код 1100
  • E, аналогично, 1101
  • F, 1110
  • G, 1111
Все! Коды Хаффмана были составлены.
Давайте проверим, будет ли сжато сообщение. Всего 7 символов.
  • Буква А встречается 14 раз, но кодируется 2 битами = 2*14 = 28
  • Буква B встречается 10 раз, но кодируется 2 битами = 10*2 = 20
  • Буква D встречается 7 раз, кодируется 4 битами = 7*4 = 28
  • Буква E встречается 3 раза, кодируется 4 битами = 3*4 = 12
  • Буква F встречается 2 раза, кодируется 4 битами = 2*4 = 8
  • Буква G встречается 1 раз, кодируется 4 битами = 1*4 = 4
Итого, ровно 100 бит. Теперь, если каждую букву кодировать по 3 бита, то 3*39=117 бит.
Выигрыш, конечно, минимальный, всего лишь 17 бит, но и набор не совсем удачный. Однако, он все равно есть.

§ Код инициализации массива с данными

Итак, теперь я попробую создать код, который будет строить дерево Хаффмана, на Си.
Архитектура такая, что каждый элемент (символ и частота), будут описаны в виде записи массива, в котором будут следующие поля:
  • Участвует ли в поиске минимального значения (en)
  • Символ (chr)
  • Частота (freq)
  • Индекс потомка слева - 0 (left)
  • Индекс потомка справа - 1 (right)
  • Родительский элемент (parent)
Выходит, что для того, чтобы обойти таблицу, потребуется связный список. То есть, каждый элемент имеет указатель на следующий элемент. Номер элемента начинаем с 1, чтобы нулевой индекс обозначал конец последовательности.
struct element {
    char en;
    char chr;
    int  freq;
    int  left;
    int  right;
    int  parent;
};
Таблица с элементами будет выглядеть приблизительно так:
struct element arr[512];
Более чем 512 элементов не потребуется. В идеальном ровном случае, при постройке равномерного дерева, из 256 элементов получится 256+128+64+...+1=511.
ID1234
СимволABCD
Частота32514
Вначале заполняется таблица так как есть, с входящими значениями частоты и символами. Напишем функцию для заполнения данными.
void elements_fill(int limit, char chars[], int freqs[]) {

    for (int i = 0; i < limit; i++) {

        arr[i].en    = 1;
        arr[i].chr   = chars[i];
        arr[i].freq  = freqs[i];
        arr[i].left  = 0;
        arr[i].right = 0;
    }
}
Устанавливается en=1, который говорит, что эта ячейка доступна в данный момент, и потомкам ставится значение 0 и 0. Они все равно потом поменяются.
Следующая задача состоит в том, чтобы найти номер индекса с минимальным значением freq из всех ячеек, где en=1.
int search_min(int limit) {

    int min = 0, id = -1;

    for (int i = 0; i < limit; i++) {

        if (arr[i].en == 0) continue;

        if (min > arr[i].freq || id < 0) {
            min = arr[i].freq;
            id  = i;
        }
    }

    return id;
}
В функции происходит инициализация min=0 и id=-1, где id - это найденный индекс. Если id будет равен -1, то это значит, что никаких значений не было найдено, что невозможно, поскольку даже если массив будет состоять из 1 элемента, то минимальное значение будет равно этому элементу.
Далее просматривается массив, исключая из поиска элементы с en=0.
  • Если минимальное значение больше текущего, то установить новый min и id
  • Или если это первый найденный элемент
Сам код функции main будет выглядеть так:
int main(int argc, char* argv[]) {

    char c[] = {'A','B','C','D','E','F','G','H'};
    int  f[] = {80,  1, 11, 17,  4,  2,  1,  1};

    int limit = 8;
    elements_fill(limit, c, f);

    return 0;
}
Здесь заполняются 8 элементов.
Как ранее говорилось, необходимо найти 2 минимальных элемента. Для этого надо:
  • Найти наименьший элемент, запомнить его id
  • Установить этому элементу en=0, чтобы вычеркнуть из поиска
  • Найти следующий наименьший элемент, запомнить id
  • Также, вычеркнуть из поиска, заменив en=0
int a = search_min(limit); if (a >= 0) arr[a].en = 0;
int b = search_min(limit); if (b >= 0) arr[b].en = 0;
На всякий случай я поставил проверку a >= 0, b >= 0, а то мало ли что может быть, например, массив будет пустой.
После того, как были найдены два минимальных значения, надо добавить им родителя, который будет ссылаться а эти два элемента:
arr[limit].en     = 1;
arr[limit].freq   = arr[a].freq + arr[b].freq;
arr[limit].left   = a;
arr[limit].right  = b;
arr[limit].parent = 0;
Родительский элемент содержит в себе сумму частот наименьших элементов и ссылки на них. У каждого же минимального элемента должен быть указан их родительский:
arr[a].parent = limit;
arr[b].parent = limit;
Здесь limit - это "высота очереди", и потому, после каждого добавления нового элемента, она увеличивается:
limit++;
Это — одна итерация, с помощью которой будет установлен новый родительский элемент для двух наименьших из оставшихся. Сами же эти два элемента вычеркиваются из списка и теперь в поиск добавляется родительский к ним элемент, который содержит ссылки и новую частоту.
Нетрудно догадаться, что при добавлении +1 и удалении -2 элементов, количество итерации, которые надо совершить, равно limit-1. Например, если у нас было 3 элемента, то первая итерация удалит 2, добавит 1 элемент и это будет 2 оставшихся, вторая итерация удалит 2 и добавит 1, то есть, останется только 1 элемент — который и будет корнем всего дерева. Так что, функция составления дерева будет выглядеть теперь так:
void heap(int limit) {

    int max = limit;

    // Поиск элементов, пока не будет найдено все
    for (int n = 1; n < max; n++) {
         // ... код поиска 2-х наименьших ...
    }
}
Достаточно в функцию main добавить вызов функции
heap(limit);
Чтобы составить дерево.

§ Печать кода Хаффмана

Теперь, составив дерево кода Хаффмана, можно найти и сами коды по указанным символам.
int print_code(int id) {

    int max = 32;
    int top = max;
    int out[max];

    while (int parent = arr[id].parent) {
        out[--top] = arr[parent].right == id;
        id = parent;
    }

    for (int i = top; i < max; i++) printf("%c", out[i]?'1':'0');

    return max - top;
}
Как работает код? Мы выбираем id от 0 до n-1, после чего попадаем на одну из ячеек, у которой есть родитель.
  • Берется родитель у ячейки
  • В выходной массив out, который заполняется справа налево, записывается либо 0, если текущий ID у родительского элемента находится слева, либо 1, если справа. Это делается проверкой потомка у выбранного родителя
  • Переставляется id на этого родителя и повторяется снова
Тем самым образом получится просмотреть дерева от крайнего листа к корню.
Далее идет просто вывод последовательности "поворотов". Значением функции будет длина кода Хаффмана для выбранного символа.
17 мая, 2022
© 2007-2022 Ужас в том, что Чичерина кусает женьшенем