§ Принцип компрессии
Очень много времени я пытался разобраться с этим кодом, но вот пришло время его понять и, когда я его понял, теперь смогу рассказать о том, что из себя представляет этот код, как его найти и насколько хорошо он сжимает.Идея кода Хаффмана заключается в том, чтобы кодировать более короткими последовательностями битов наиболее часто встречающиеся символы, а более длинными — те, что реже. Для того, чтобы составить код Хаффмана, потребуется знание того, с какой частотой встречает символ. Если такая частота у всех символов одинаковая, то код Хаффмана ничего не сожмет, вообще, так что применять этот код надо только там, где разность частот существенная.
Например в слове
ABBBBBBABAC буква А встречается 3 раза, буква C - 1 раз и буква B - аж 7 раз. Зададим такие последовательности:- B - 0
- A - 10
- C - 11
Теперь закодируем последовательность
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 элемент
По итогу, получится дерево, обходя которое, можно найти код Хаффмана. Понимаю, что текстом ничего неясно, так что буду сейчас это дело иллюстрировать на примере.
Есть первичный набор данных, уже отсортированный по частоте
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), итого, А кодируется как
- Теперь 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
Выигрыш, конечно, минимальный, всего лишь 17 бит, но и набор не совсем удачный. Однако, он все равно есть.
§ Код инициализации массива с данными
Итак, теперь я попробую создать код, который будет строить дерево Хаффмана, на Си.Архитектура такая, что каждый элемент (символ и частота), будут описаны в виде записи массива, в котором будут следующие поля:
- Участвует ли в поиске минимального значения (en)
- Символ (chr)
- Частота (freq)
- Индекс потомка слева - 0 (left)
- Индекс потомка справа - 1 (right)
- Родительский элемент (parent)
1struct element { 2 char en; 3 char chr; 4 int freq; 5 int left; 6 int right; 7 int parent; 8};Таблица с элементами будет выглядеть приблизительно так:
1struct element arr[512];Более чем 512 элементов не потребуется. В идеальном ровном случае, при постройке равномерного дерева, из 256 элементов получится 256+128+64+...+1=511.
| ID | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Символ | A | B | C | D |
| Частота | 3 | 25 | 1 | 4 |
1void elements_fill(int limit, char chars[], int freqs[]) { 2 3 for (int i = 0; i < limit; i++) { 4 5 arr[i].en = 1; 6 arr[i].chr = chars[i]; 7 arr[i].freq = freqs[i]; 8 arr[i].left = 0; 9 arr[i].right = 0; 10 } 11}Устанавливается en=1, который говорит, что эта ячейка доступна в данный момент, и потомкам ставится значение 0 и 0. Они все равно потом поменяются.
Следующая задача состоит в том, чтобы найти номер индекса с минимальным значением freq из всех ячеек, где en=1.
1int search_min(int limit) { 2 3 int min = 0, id = -1; 4 5 for (int i = 0; i < limit; i++) { 6 7 if (arr[i].en == 0) continue; 8 9 if (min > arr[i].freq || id < 0) { 10 min = arr[i].freq; 11 id = i; 12 } 13 } 14 15 return id; 16}В функции происходит инициализация min=0 и id=-1, где id - это найденный индекс. Если id будет равен -1, то это значит, что никаких значений не было найдено, что невозможно, поскольку даже если массив будет состоять из 1 элемента, то минимальное значение будет равно этому элементу.
Далее просматривается массив, исключая из поиска элементы с en=0.
- Если минимальное значение больше текущего, то установить новый min и id
- Или если это первый найденный элемент
1int main(int argc, char* argv[]) { 2 3 char c[] = {'A','B','C','D','E','F','G','H'}; 4 int f[] = {80, 1, 11, 17, 4, 2, 1, 1}; 5 6 int limit = 8; 7 elements_fill(limit, c, f); 8 9 return 0; 10}Здесь заполняются 8 элементов.
Как ранее говорилось, необходимо найти 2 минимальных элемента. Для этого надо:
- Найти наименьший элемент, запомнить его id
- Установить этому элементу en=0, чтобы вычеркнуть из поиска
- Найти следующий наименьший элемент, запомнить id
- Также, вычеркнуть из поиска, заменив en=0
1int a = search_min(limit); if (a >= 0) arr[a].en = 0; 2int b = search_min(limit); if (b >= 0) arr[b].en = 0;На всякий случай я поставил проверку a >= 0, b >= 0, а то мало ли что может быть, например, массив будет пустой.
После того, как были найдены два минимальных значения, надо добавить им родителя, который будет ссылаться а эти два элемента:
1arr[limit].en = 1; 2arr[limit].freq = arr[a].freq + arr[b].freq; 3arr[limit].left = a; 4arr[limit].right = b; 5arr[limit].parent = 0;Родительский элемент содержит в себе сумму частот наименьших элементов и ссылки на них. У каждого же минимального элемента должен быть указан их родительский:
1arr[a].parent = limit; 2arr[b].parent = limit;Здесь limit - это "высота очереди", и потому, после каждого добавления нового элемента, она увеличивается:
1limit++;Это — одна итерация, с помощью которой будет установлен новый родительский элемент для двух наименьших из оставшихся. Сами же эти два элемента вычеркиваются из списка и теперь в поиск добавляется родительский к ним элемент, который содержит ссылки и новую частоту.Нетрудно догадаться, что при добавлении +1 и удалении -2 элементов, количество итерации, которые надо совершить, равно limit-1. Например, если у нас было 3 элемента, то первая итерация удалит 2, добавит 1 элемент и это будет 2 оставшихся, вторая итерация удалит 2 и добавит 1, то есть, останется только 1 элемент — который и будет корнем всего дерева. Так что, функция составления дерева будет выглядеть теперь так:
1void heap(int limit) { 2 3 int max = limit; 4 5 // Поиск элементов, пока не будет найдено все 6 for (int n = 1; n < max; n++) { 7 // ... код поиска 2-х наименьших ... 8 } 9}Достаточно в функцию main добавить вызов функции
1heap(limit);Чтобы составить дерево.§ Печать кода Хаффмана
Теперь, составив дерево кода Хаффмана, можно найти и сами коды по указанным символам.1int print_code(int id) { 2 3 int max = 32; 4 int top = max; 5 int out[max]; 6 7 while (int parent = arr[id].parent) { 8 out[--top] = arr[parent].right == id; 9 id = parent; 10 } 11 12 for (int i = top; i < max; i++) printf("%c", out[i]?'1':'0'); 13 14 return max - top; 15}Как работает код? Мы выбираем id от 0 до n-1, после чего попадаем на одну из ячеек, у которой есть родитель.
- Берется родитель у ячейки
- В выходной массив out, который заполняется справа налево, записывается либо 0, если текущий ID у родительского элемента находится слева, либо 1, если справа. Это делается проверкой потомка у выбранного родителя
- Переставляется id на этого родителя и повторяется снова
Далее идет просто вывод последовательности "поворотов". Значением функции будет длина кода Хаффмана для выбранного символа.