1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Кодирование Хаффмана (часть 1 и 2)

Дата публикации 20 авг 2017 | Редактировалось 10 янв 2018
Кодирование Хаффмана. Часть 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].
[​IMG]
После многократного повторения изложенных действий выстраивается следующее дерево:
[​IMG]
По построенному дереву можно определить значение кодов [math]{b_1,b_2,...,b_n}[/math], осуществляя спуск от корня к соответствующему элементу [math]a_i[/math], при этом приписывая к получаемой последовательности при прохождении каждой ветки ноль или единицу (в зависимости от того, как именуется конкретная ветка). Таким образом таблица кодов выглядит следующим образом:
ibiLi(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. Таким образом, получаем следующий результат:
Данные12672262Длина кода
Исходные001010110111010010110 01024 бит
Кодированные011111100011101100119 бит
В результате кодирования мы выиграли 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Длина кода
Кодированные00110110000111000100011111127 бит
Исходные6223676261233 бит
В данном случае выигрыш составил 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++ это - язык программирования". Потом, когда стал его изучать, я всячески его хвалил: "он может то, может это, а вот это - вообще класс, это супер язык". Но помере набора опыта С++ стал для меня "просто языком программирования". Почувствуйте разницу между этими тремя утверждениями.
Скачать исходный код к статье

0 6.998
SadKo

SadKo
Владимир Садовников

Регистрация:
4 июн 2007
Публикаций:
8