Кодирование Хаффмана. Часть 1.
Вступление
Здравствуй, дорогой читатель! В данной статье будет рассмотрен один из способов сжатия данных. Этот способ является достаточно широко распространённым и заслуживает определённого внимания. Данный материал рассчитан по объёму на три статьи, первая из которых будет посвящена алгоритму сжатия, вторая - программной реализации алгоритма, а третья ― декомпрессии. Алгоритм сжатия будет написан на языке C++, алгоритм декомпрессии ― на языке Assembler.
Однако, перед тем, как приступить к самому алгоритму, следует включить в статью немного теории.
Немного теории
Компрессия (сжатие) ― способ уменьшения объёма данных с целью дальнейшей их передачи и хранения.
Декомпрессия ― это способ восстановления сжатых данных в исходные.
Компрессия и декомпрессия могут быть как без потери качества (когда передаваемая/хранимая информация в сжатом виде после декомпрессии абсолютно идентична исходной), так и с потерей качества (когда данные после декомпрессии отличаются от оригинальных). Например, текстовые документы, базы данных, программы могут быть сжаты только способом без потери качества, в то время как картинки, видеоролики и аудиофайлы сжимаются именно за счёт потери качества исходных данных (характерный пример алгоритмов ― JPEG, MPEG, ADPCM), при порой незаметной потере качества даже при сжатии 1:4 или 1:10.
Выделяются основные виды упаковки:

• Десятичная упаковка предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и так далее. При подобном подходе уже ощущается сжатие минимум 1:2.
• Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
• Символьное подавление - способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
• Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). При таком подходе коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому ― с наибольшей.

Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хаффмана, последний из которых мы и будем рассматривать.
Конкретнее об алгоритме
Как уже известно из предыдущего подраздела, алгоритм Хафмана основан на статистическом кодировании. Разберёмся поподробнее в его реализации.
Пусть имеется источник данных, который передаёт символы [math](a_1, a_2, ..., a_n)[/math] с разной степенью вероятности, то есть каждому [math]a_i[/math] соответствует своя вероятность (или частота) [math]P_i(a_i)[/math], при чём существует хотя бы одна пара [math]a_i[/math] и [math]a_j[/math] ,[math]i\ne j[/math], такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] не равны. Таким образом образуется набор частот [math]{P_1(a_1), P_2(a_2),...,P_n(a_n)}[/math], при чём [math]\displaystyle \sum_{i=1}^{n} P_i(a_i)=1[/math], так как передатчик не передаёт больше никаких символов кроме как [math]{a_1,a_2,...,a_n}[/math].
Наша задача ― подобрать такие кодовые символы [math]{b_1, b_2,...,b_n}[/math] с длинами [math]{L_1(b_1),L_2(b_2),...,L_n(b_n)}[/math], чтобы средняя длина кодового символа не превышала средней длины исходного символа. При этом нужно учитывать условие, что если [math]P_i(a_i)>P_j(a_j)[/math] и [math]i\ne j[/math], то [math]L_i(b_i)\le L_j(b_j)[/math].
Хафман предложил строить дерево, в котором узлы с наибольшей вероятностью наименее удалены от корня. Отсюда и вытекает сам способ построения дерева:
1. Выбрать два символа [math]a_i[/math] и [math]a_j[/math], [math]i\ne j[/math], такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] из всего списка [math]{P_1(a_1),P_2,...,P_n(a_n)}[/math] являются минимальными.
2. Свести ветки дерева от этих двух элементов в одну точку с вероятностью [math]P=P_i(a_i)+P_j(a_j)[/math], пометив одну ветку нулём, а другую ― единицей (по собственному усмотрению).
3. Повторить пункт 1 с учётом новой точки вместо [math]a_i[/math] и [math]a_j[/math], если количество получившихся точек больше единицы. В противном случае мы достигли корня дерева.
Теперь попробуем воспользоваться полученной теорией и закодировать информацию, передаваемую источником, на примере семи символов.
Разберём подробно первый цикл. На рисунке изображена таблица, в которой каждому символу [math]a_i[/math] соответствует своя вероятность (частота) [math]P_i(a_i)[/math]. Согласно пункту 1 мы выбираем два символа из таблицы с наименьшей вероятностью. В нашем случае это [math]a_1[/math] и [math]a_4[/math]. Согласно пункту 2 сводим ветки дерева от [math]a_1[/math] и [math]a_4[/math] в одну точку и помечаем ветку, ведущую к [math]a_1[/math], единицей, а ветку, ведущую к [math]a_4[/math],― нулём. Над новой точкой приписываем её вероятность (в данном случае ― 0.03) В дальнейшем действия повторяются уже с учётом новой точки и без учёта [math]a_1[/math] и [math]a_4[/math].

​

После многократного повторения изложенных действий выстраивается следующее дерево:

​

По построенному дереву можно определить значение кодов [math]{b_1,b_2,...,b_n}[/math], осуществляя спуск от корня к соответствующему элементу [math]a_i[/math], при этом приписывая к получаемой последовательности при прохождении каждой ветки ноль или единицу (в зависимости от того, как именуется конкретная ветка). Таким образом таблица кодов выглядит следующим образом:

i	bi	Li(bi)
1	011111	6
2	1	1
3	0110	4
4	011110	6
5	010	3
6	00	2
7	01110	5

Теперь попробуем закодировать последовательность из символов.
Пусть символу [math]a_i[/math] соответствует (в качестве примера) число [math]i[/math]. Пусть имеется последовательность 12672262. Нужно получить результирующий двоичный код.
Для кодирования можно использовать уже имеющуюся таблицу кодовых символов [math]b_i[/math] при учёте, что [math]b_i[/math] соответствует символу [math]a_i[/math]. В таком случае код для цифры 1 будет представлять собой последовательность 011111, для цифры 2 ― 1, а для цифры 6 ― 00. Таким образом, получаем следующий результат:

Данные	1	2	6	7	2	2	6	2	Длина кода
Исходные	001	010	110	111	010	010	110	010	24 бит
Кодированные	011111	1	00	01110	1	1	00	1	19 бит

В результате кодирования мы выиграли 5 бит и записали последовательность 19 битами вместо 24.
Однако это не даёт полной оценки сжатия данных. Вернёмся к математике и оценим степень сжатия кода. Для этого понадобится энтропийная оценка.
Энтропия ― мера неопределённости ситуации (случайной величины) с конечным или с чётным числом исходов. Математически энтропия формулируется как сумма произведений вероятностей различных состояний системы на логарифмы этих вероятностей, взятых с обратным знаком:

[math]H(X)=-\displaystyle \sum_{i=1}^{n}P_i\cdot log_d (P_i)[/math].​

Где [math]X[/math] ― дискретная случайная величина (в нашем случае ― кодовый символ), а [math]d[/math] ― произвольное основание, большее единицы. Выбор основания равносилен выбору определённой единицы измерения энтропии. Так как мы имеем дело с двоичными цифрами, то в качестве основания рационально выбрать [math]d=2[/math].
Таким образом, энтропию для нашего случая можно представить в виде:

[math]H(b)=-\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot log_2 (P_i(a_i))[/math].​

Энтропия обладает замечательным свойством: она равна минимальной допустимой средней длине кодового символа [math]\overline{L_{min}}[/math] в битах. Сама же средняя длина кодового символа вычисляется по формуле

[math]\overline{L(b)}=\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot L_i(b_i)[/math].​

Подставляя значения в формулы [math]H(b)[/math] и [math]\overline{L(b)}[/math], получаем следующий результат: [math]H(b)=2,048[/math], [math]\overline{L(b)}=2,100[/math].
Величины [math]H(b)[/math] и [math]\overline{L(b)}[/math] очень близки, что говорит о реальном выигрыше в выборе алгоритма. Теперь сравним среднюю длину исходного символа и среднюю длину кодового символа через отношение:

[math]\frac{\overline{L_{src}}}{L(b)}=\frac{3}{2,1}=1,429[/math].​

Таким образом, мы получили сжатие в соотношении 1:1,429, что очень неплохо.
И напоследок, решим последнюю задачу: дешифровка последовательности битов.
Пусть для нашей ситуации имеется последовательность битов:

001101100001110001000111111​

Необходимо определить исходный код, то есть декодировать эту последовательность.
Конечно, в такой ситуации можно воспользоваться таблицей кодов, но это достаточно неудобно, так как длина кодовых символов непостоянна. Гораздо удобнее осуществить спуск по дереву (начиная с корня) по следующему правилу:
1. Исходная точка ― корень дерева.
2. Прочитать новый бит. Если он ноль, то пройти по ветке, помеченной нулём, в противном случае ― единицей.
3. Если точка, в которую мы попали, конечная, то мы определили кодовый символ, который следует записать и вернуться к пункту 1. В противном случае следует повторить пункт 2.
Рассмотрим пример декодирования первого символа. Мы находимся в точке с вероятностью 1,00 (корень дерева), считываем первый бит последовательности и отправляемся по ветке, помеченной нулём, в точку с вероятностью 0,60. Так как эта точка не является конечной в дереве, то считываем следующий бит, который тоже равен нулю, и отправляемся по ветке, помеченной нулём, в точку [math]a_6[/math], которая является конечной. Мы дешифровали символ ― это число 6. Записываем его и возвращаемся в исходное состояние (перемещаемся в корень).
Таким образом декодированная последовательность принимает вид.

Данные	001101100001110001000111111											Длина кода
Кодированные	00	1	1	0110	00	01110	00	1	00	011111	1	27 бит
Исходные	6	2	2	3	6	7	6	2	6	1	2	33 бит

В данном случае выигрыш составил 6 бит при достаточно небольшой длине последовательности.
Вывод напрашивается сам собой: алгоритм прост. Однако следует сделать замечание: данный алгоритм хорош для сжатия текстовой информации (действительно, реально мы используем при набивке текста примерно 60 символов из доступных 256, то есть вероятность встретить иные символы близка к нулю), но достаточно плох для сжатия программ (так как в программе все символы практически равновероятны). Так что эффективность алгоритма очень сильно зависит от типа сжимаемых данных.
Постскриптум
В этой статье мы рассмотрели алгоритм кодирования по методу Хаффмана, который базируется на неравномерном кодировании. Он позволяет уменьшить размер передаваемых или хранимых данных. Алгоритм прост для понимания и может давать реальный выигрыш. Кроме этого, он обладает ещё одним замечательным свойством: возможность кодировать и декодировать информацию "на лету" при условии того, что вероятности кодовых слов правильно определены. Хотя существует модификация алгоритма, позволяющая изменять структуру дерева в реальном времени.
В следующей части статьи мы рассмотрим байт-ориентированное сжатие файлов с использованием алгоритма Хаффмана, реализованное на C++.
Кодирование Хаффмана. Часть 2
Вступление
В прошлой части мы рассмотрели алгоритм кодирования, описали его математическую модель, произвели кодирование и декодирование на конкретном примере, рассчитали среднюю длину кодового слова, а также определили коэффициент сжатия. Кроме этого, были сделаны выводы о преимуществах и недостатках данного алгоритма.
Однако, помимо этого неразрешёнными остались ещё два вопроса: реализация программы, сжимающей файл данных, и программы, распаковывающей сжатый файл. Первому вопросу и посвящена настоящая статья. Поэтому следует заняться проектированием.
Проектирование
Первым делом необходимо посчитать частоты вхождения символов в файл. Для этого опишем следующую структуру:

Код (C++):

1. // Структура для подсчёта частоты символа
2. typedef struct TFreq
3. {
4.   int  ch;
5.   TTable  *table;
6.   DWORD  freq;
7. } TFreq;

Эта структура будет описывать каждый символ из 256. ch ― сам ASCII-символ, freq ― количество вхождений символа в файл. Поле table ― указатель на структуру:

Код (C++):

1. // Описатель узла
2. typedef struct TTable
3. {
4.   int ch;
5.   TTable  *left;
6.   TTable  *right;
7. } TTable;

Как видно, TTable ― это описатель узла с разветвлением по нулю и единице. При помощи этих структур в дальнейшем и будет осуществляться построение дерева компрессии. Теперь объявим для каждого символа свою частоту и свой узел:

Код (C++):

1. TFreq  Freq[256];

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

Код (C++):

1. // Описатель кодового символа
2. typedef struct TOpcode
3. {
4.   DWORD  opcode;
5.   DWORD  len;
6. } TOpcode;

Здесь opcode ― кодовая комбинация символа, а len - её длина (в битах). И объявим таблицу из 256 таких структур:

Код (C++):

1. TOpcode  Opcodes[256];

Зная кодируемый символ, можно определить его кодовое слово по таблице. Теперь перейдём непосредственно к подсчёту частот символов (и не только).
Подсчёт частот символов
В принципе, это действие не составляет труда. Достаточно открыть файл и подсчитать в нём число символов, заполнив соответствующие структуры. Посмотрим реализацию этого действия.
Для этого объявим глобальные дескрипторы файлов:

Код (C++):

1. FILE *in, *out, *assemb;

in ― файл, из которого осуществляется чтение несжатых данных.
out ― файл, в который осуществляется запись сжатых данных.
assemb ― файл, в который будет сохранено дерево в удобном для распаковки виде. Так как распаковщик будет написан на ассемблере, то вполне рационально дерево сделать частью распаковщика, то есть представить его в виде инструкций на Ассемблере.
Первым делом необходимо проинициализировать все структуры нулевыми значениями:

Код (C++):

1. // Подсчёт частот символов
2. int CountFrequency(void)
3. {
4.   int i;  // переменная цикла
5.   int count=0;   // вторая переменная цикла
6.   DWORD TotalCount=0; // размер файла.
7.   // Инициализация структур
8.   for (i=0; i<256; i++)
9.   {
10.        Freq[i].freq=0;
11.        Freq[i].table=0;
12.        Freq[i].ch=i;
13.   }

После этого мы подсчитываем число вхождений символа в файл и размер файла (конечно, не самым идеальным способом, но в примере нужна наглядность):

Код (C++):

1.    // Подсчёт частот символов (по-символьно)
2.   while (!feof(in)) // пока не достигнут конец файла
3.   {
4.   i=fgetc(in);
5.   if (i!=EOF) // если не конец файла
6.     {
7.         Freq[i].freq++; // частота ++
8.         TotalCount++; // размер ++
9.      }
10.   }

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

Код (C++):

1.   // "Сообщаем" распаковщику размер файла
2.   fprintf(assemb, "coded_file_size:\n dd %8lxh\n\n", TotalCount);

После этого все используемые символы смещаются в начало массива, а неиспользуемые затираются (путём перестановок).

Код (C++):

1.   // смещаем все неиспользуемые символы в конец
2.   i=0;
3.   count=256;
4.   while (i<count) // пока не достигли конца
5.   {
6.              if (Freq[i].freq==0) // если частота 0
7.              Freq[i]=Freq[--count]; // то копируем запись из конца
8.              else
9.              i++; // всё ОК - двигаемся дальше.
10.   }

И только после такой "сортировки" выделяется память под узлы (для некоторой экономии).

Код (C++):

1.   // Выделяем память под узлы
2.   for (i=0; i<count; i++)
3.   {
4.            Freq[i].table=new TTable; // создаём узел
5.            Freq[i].table->left=0; // без соединений
6.            Freq[i].table->right=0; // без соединений
7.            Freq[i].table->ch=Freq.ch; // копируем символ
8.            Freq[i].freq=Freq.freq; // и частоту
9.   }
10.   return count;
11. }

Таким образом, мы написали функцию первоначальной иницализации системы, или, если смотреть на алгоритм в первой части статьи, "записали используемые символы в столбик и приписали к ним вероятности", а также для каждого символа создали "отправную точку" ― узел ― и проинициализировали её. В поля left и right записали нули. Таким образом, если узел будет в дереве последним, то это будет легко увидеть по left и right, равным нулю.
Создание дерева
Итак, в предыдущем разделе мы "записали используемые символы в столбик и приписали к ним вероятности". На самом деле, мы приписали к ним не вероятности, а числители дроби (то есть количество вхождений символов в файл). Теперь надо построить дерево. Но для того, чтобы это сделать, необходимо найти минимальный элемент в списке. Для этого вводим функцию, в которую передаём два параметра ― количество элементов в списке и элемент, который следует исключить (потому что искать будем парами, и будет очень неприятно, если мы от функции дважды получим один и тот же элемент):

Код (C++):

1. // поиск узла с наименьшей вероятностью.
2. int FindLeast(int count, int index)
3. {
4.   int i;
5.   DWORD min=(index==0) ? 1 : 0; // элемент, который считаем
6.   // минимальным
7.   for (i=1; i<count; i++) // цикл по массиву
8.   {
9.   if (i!=index) // если элемент не исключён
10.   if (Freq[i].freq<Freq[min].freq) // сравниваем
11.   min=i; // меньше минимума - запоминаем
12.   }
13.   return min; // возвращаем индекс минимума
14. }

Поиск реализован несложно: сначала выбираем "минимальный" элемент массива. Если исключаемый элемент ― 0, то берём в качестве минимума первый элемент, в противном случае минимумом считаем нулевой. По мере прохождения по массиву сравниваем текущий элемент с "минимальным", и если он окажется меньше, то его помечаем как минимальный.
Теперь, собственно говоря, сама функция построения дерева:

Код (C++):

1. // Функция построения дерева
2. void PreInit(int count)
3. {
4.   int ind1, ind2; // индексы элементов
5.   TTable *table; // указатель на "новый узел"
6.   while (count>1) // цикл, пока не достигли корня
7.   {
8.   ind1=FindLeast(count,-1); // первый узел
9.   ind2=FindLeast(count,ind1); // второй узел
10.   table=new TTable; // создаём новый узел
11.   table->ch=-1; // не конечный
12.   table->left=Freq[ind1].table; // 0 - узел 1
13.   table->right=Freq[ind2].table; // 1 - узел 2
14.   Freq[ind1].ch=-1; // модифицируем запись о
15.   Freq[ind1].freq+=Freq[ind2].freq; // частоте для символа
16.   Freq[ind1].table=table; // и пишем новый узел
17.   if (ind2!=(--count)) // если ind2 не последний
18.   Freq[ind2]=Freq[count]; // то на его место
19.   // помещаем последний в массиве
20.   }
21. }

Таблица кодовых символов
Итак, дерево в памяти мы построили: попарно брали два узла, создавали новый узел, в который записывали на них указатели, после чего второй узел удаляли из списка, а вместо первого узла писали новый с разветвлением.
Теперь возникает ещё одна проблема: кодировать по дереву неудобно, потому что необходимо точно знать, по какому пути находится тот или иной символ. Однако проблема решается довольно просто: создаётся ещё одна таблица ― таблица кодовых символов ― в неё и записываются битовые комбинации всех используемых символов. Для этого достаточно однократно рекурсивно обойти дерево. Заодно, чтобы повторно его не обходить, можно в функцию обхода добавить генерацию ассемблерного файла для дальнейшего декодирования сжатых данных (см. раздел "Проектирование").
Собственно, сама функция не сложна. Она должна приписывать к кодовой комбинации 0 или 1, если узел не конечный, в противном случае добавить кодовый символ в таблицу. Помимо всего этого, сгенерировать ассемблерный файл. Рассмотрим эту функцию:

Код (C++):

1. // Функция рекурсивного обхода дерева
2. void RecurseMake(TTable *tbl, DWORD opcode, int len)
3. {
4.   fprintf(assemb,"opcode%08lx_%04x:\n",opcode,len); // метку в файл
5.   if (tbl->ch!=-1) // узел конечный
6.   {
7.   BYTE mod=32-len;
8.   Opcodes[tbl->ch].opcode=(opcode>>mod); // сохраняем код
9.   Opcodes[tbl->ch].len=len; // и его длину (в битах)
10.   // и создаём соответствующую метку
11.   fprintf(assemb," db %03xh,0ffh,0ffh,0ffh\n\n",tbl->ch);
12.   }
13.   else // узел не конечный
14.   {
15.   opcode>>=1; // освобождаем место под новый бит
16.   len++; // увеличиваем длину кодового слова
17.   // делаем ссылки на метки символов
18.   fprintf(assemb," dw opcode%08lx_%04x\n",opcode,len);
19.   fprintf(assemb," dw opcode%08lx_%04x\n\n",opcode|0x80000000,len);
20.   // Рекурсивный вызов
21.   RecurseMake(tbl->left,opcode,len);
22.   RecurseMake(tbl->right,opcode|0x80000000,len);
23.   }
24.   // удаляем узел (он уже не нужен)
25.   delete tbl;
26. }

Помимо всего прочего, после прохождения узла функция удаляет его (освобождает указатель). Теперь разберёмся, что за параметры передаются в функцию.

• tbl ― узел, который надо обойти.
• opcode ― текущее кодовое слово. Старший бит должен быть всегда свободен.
• len ― длина кодового слова.

В принципе, функция не сложнее "классического факториала" и не должна вызывать трудностей.
Битовый вывод
Вот мы и добрались до не самой приятной части нашего архиватора, а именно ― до вывода кодовых символов в файл. Проблема состоит в том, что кодовые символы имеют неравномерную длину и вывод приходится осуществлять побитовый. В этом поможет функция PutCode. Но для начала объявим две переменные ― счётчик битов в байте и выводимый байт:

Код (C++):

1. // Счётчик битов
2. int OutBits;
3. // Выводимый символ
4. BYTE OutChar;

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

Код (C++):

1. // Сохранить код
2. void PutCode(int ch)
3. {
4.   int len;
5.   int outcode;
6.   // получаем длину кодового слова и само кодовое слово
7.   outcode=Opcodes[ch].opcode; // кодовое слово
8.   len=Opcodes[ch].len; // длина (в битах)
9.   while (len>0) // выводим по-битно
10.   {
11.   // Цикл пока переменная OutBits занята не полностью
12.   while ((OutBits<8) && (len>0))
13.   {
14.   OutChar>>=1; // освобождаем место
15.   OutChar|=((outcode&1)<<7); // и в него помещаем бит
16.   outcode>>=1; // следующий бит кода
17.   len--; // уменьшаем длину
18.   OutBits++; // количество битов выросло
19.   }
20.   // если используются все 8 бит, то сохраняем их в файл
21.   if (OutBits==8)
22.   {
23.   fputc(OutChar,out); // сохраняем в файл
24.   OutBits=0; // обнуляем
25.   OutChar=0; // параметры
26.   }
27.   }
28. }

Помимо этого, нужно организовать что-то вроде "fflush", то есть после вывода последнего кодового слова OutChar не поместится в выходной файл, так как OutBits!=8. Отсюда появляется ещё одна небольшая функция:

Код (C++):

1. // "Очистка" буфера битов
2. void EndPut(void)
3. {
4.   // Если в буфере есть биты
5.   if (OutBits!=0)
6.   {
7.   OutChar>>=8-OutBits; // сдвигаем
8.   fputc(OutChar,out); // и сохраняем в файле
9.   }
10. }

Вызываем помощников
Все рассмотренные ранее функции не являются основными. Но с их помощью можно проиллюстрировать простой порядок действий:
1. Выписать все элементы в столбик и приписать вероятности.
2. Построить дерево по полученному столбику.
3. Записать кодовую таблицу символов.
4. По кодовой таблице закодировать исходные данные.
Собственно говоря, вот и функция, которая выполняет эти действия:

Код (C++):

1. // Создание сжатого файла
2. void MakeFile(void)
3. {
4.   int count;
5.   int ch;
6.   // выписать все элементы в столбик и приписать вероятности
7.   count=CountFrequency();
8.   // построить дерево
9.   PreInit(count);
10.   // записать кодовую таблицу символов
11.   RecurseMake(Freq[0].table,0,0);
12.   // закодировать по кодовой таблице исходные данные
13.   fseek(in,0,SEEK_SET);
14.   OutChar=0;
15.   OutBits=0;
16.   while ((ch=fgetc(in))!=EOF)
17.   PutCode(ch);
18.   EndPut(); // "очистить буфер"
19. }

Мейн
Всё, все функции готовы. Осталось только реализовать функцию main. Необходимо определить, какие она должна получить аргументы. А всё очень просто ― имя исходного файла, имя закодированного файла, а также имя файла, в который будет помещена таблица. Лично я всю операцию по открытию/закрытию файлов решил возложить на main. И вот как это выглядит:

Код (C++):

1. #include <stdio.h>
2. // Определение типов данных
3. #ifdef __MSDOS__
4.   typedef unsigned char BYTE;
5.   typedef unsigned int WORD;
6.   typedef unsigned long DWORD;
7. #else
8.   typedef unsigned char BYTE;
9.   typedef unsigned short WORD;
10.   typedef unsigned int DWORD;
11. #endif
12. // Ахтунг! Главная функция!
13. void main(int argc, char *argv[])
14. {
15.   if (argc==4)
16.   {
17.   // поочереди открываем/закрываем файлы
18.   if ((in=fopen(argv[1],"rb+"))!=0)
19.   {
20.   if ((out=fopen(argv[2],"wb+"))!=0)
21.   {
22.   if ((assemb=fopen(argv[3],"wb+"))!=0)
23.   {
24.   // дошли до момента, когда можно делать код
25.   MakeFile();
26.   fclose(assemb);
27.   printf("Compressed successful\n");
28.   }
29.   else
30.   printf("Can't open assembler table file %s\n",
31.   argv[3]);
32.   fclose(out);
33.   }
34.   else
35.   printf("Can't create file %s\n",argv[2]);
36.   fclose(in);
37.   }
38.   else
39.   printf("Can't open file %s\n",argv[1]);
40.   }
41.   else
42.   printf("Usage: XARCH source output asm-file");
43. }

Постскриптум
Вот и эта статья подошла к своему логическому завершению. В принципе, здесь представлен вполне рабочий код. Однако стоит заметить, что этот код не всегда способен работать. Например, если частоты символов обладают следующей закономерностью: 0.5, 0.25, 0.125, 0.0625, то есть у каждого символа вероятность его появления обратнопропорциональна степени двойки. В таком случае максимальная длина символа составит 255 бит, что никак не поместится в переменную типа DWORD. Поэтому для таких особых случаев придётся немного поднапрячься и усложнить генерацию кодовой таблицы.
Да, чуть не забыл. Провёл бенчмарк, сжав эту статью. Получил отношение 1:1.41, что довольно-таки неплохо.
P.P.S.
Позволю себе немного пофилософствовать. Сначала я не знал C++ и говорил: "C++ это - язык программирования". Потом, когда стал его изучать, я всячески его хвалил: "он может то, может это, а вот это - вообще класс, это супер язык". Но помере набора опыта С++ стал для меня "просто языком программирования". Почувствуйте разницу между этими тремя утверждениями.
Скачать исходный код к статье