Сжатие информации: как это делается

Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду.
Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать
сжатие в своей проге, то мы используем различные dll'ки, многие из которых платные.
Шареварность - это не единственное свойство программных компонентов, мешающих их нормальному
использованию. Если, например, сжимать waw или bmp-файл архиватором, то
он будет значительно уступать специальному методу для конкретного типа данных, т.е.
метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно.
В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.

Классификация методов сжатия

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

Теория

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

Методы сжатия делятся на статистические и словарные. Словарные методы заключаются в том,
чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая
занимает меньше места, чем сама подстрока. Классическим словарным методом является метод
Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь
модификациями LZ.

Статистическое кодирование заключается в том, чтобы кодировать каждый символ, но
использовать коды переменной длины. Примером таких методов служит метод Хаффмана
(Huffman). Обычно словарные и статистические методы комбинируются, поскольку у каждого свои
преимущества.

Отметим один момент, который почему-то неочевиден для некоторых "теоретиков".
Правило кодирования определяется вероятностной структурой данных, а значит, декомпрессор
должен до начала раскодирования уже знать её. Если же мы получаем её из статистики конкретного
сообщения (так оно сжимается лучше), то её придется передать явно или неявно вместе со сжатым
сообщением, и еще неизвестно, будет ли общий размер меньше.

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

H = -Sum(p[i] * log(p[i]))

где Sum - сумма по i, p[i] - вероятность i-го сообщения, log - логарифм по основанию 2.
Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.

Если кодировать каждый символ отдельно, то длина кода каждого сообщения должна быть
равна -log(p). Т.е., например, если вероятность символа 0.3, то его код должен иметь длину
1.73 бита, в то время, как реальные длины целые. Можно улучшить результаты, если не сводить
задачу к кодированию отдельных символов.

Арифметическое кодирование

Этот метод в корне отличается от всех рассмотренных ранее методов. Его главное
преимущество в том, что достигается теоретический предел сжатия. Рассмотрим этот метод подробно. Всё сообщение целиком представляется одним числом по следующему правилу. Число должно
находиться в интервале от 0 до 1. Этот интервал делится на части, пропорциональные вероятностям
значений первого символа. Выбирается часть, соответствующая символу и делится на части по
вероятностям значений второго символа и т.д. 

новая_нижняя_граница = нижняя_граница + ширина * S[i]
новая_ширина = ширина * p[i]

где p[i] - вероятность i-го символа, S[i] - сумма вероятностей символов с номерами
меньше i.

После обработки всего сообщения по этому алгоритму остается только записать любое
число из получившегося интервала. Количество битов, необходимое для записи этого числа,
примерно равно минус логарифму ширины интервала. Ширина интервала равна произведению
вероятностей символов, т.е. вероятности всего сообщения. Т.о., длина кода равна
-log(p), т.е. теоретическому пределу. На практике мы будем работать с переменными ограниченной длины,
и точность вычислений будет ограничена, а значит, сжатие будет все-таки немного хуже.

Реализация

Проект, прикрепленный к этой статье, компилируется на Visual Studio .NET.
Это реализация арифметического кодирования, сжимающая файлы, рассматривая байты как символы.
Содержимое файла рассматривается как марковский процесс 1-го порядка, т. е. распределение
вероятностей символов зависит от предыдущего символа. Класс CMarkovProcessDef обрабатывает
данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам
обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься
хорошо, а если попытаться сжать какой-нибудь бинарник, то размер "сжатого" файла будет больше
исходного. Для того, чтобы получить метод сжатия для своего типа данных, нужно заменить данные о
вероятностях символов. Кроме того, символ - это не обязательно байт несжатых данных. Например,
если есть столбец таблицы, где значения должны быть уникальными, то каждое значение - это
символ, а после того, как символ встречается, сбрасываем его вероятность в ноль. Нижняя граница и ширина интервала хранятся в целочисленных переменных dwBuf1 и dwBuf2.
Если после обработки очередного символа старшие байты границ окажутся равными
(заметим, что это не то же самое, что если старший байт ширины равен нулю), то
соответствующий байт окончательного результата будет равен этому значению, и его можно
записать в файл. Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам
понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно
найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2. При работе с целыми числами возникает проблема: мы представляем вероятности (дробные
числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны
особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении
делим число, умноженное на 2^32. Компилятор не может, умножитв DWORD на DWORD, поместить результат
в 64-битную переменную - это недостаток языка С++. Поэтому пришлось написать специальные процедуры
на ассемблере.

void CArithmCompressorDlg::OnBnClickedCompress()
{
CFileDialog dlg1(TRUE);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE, "compressed", 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, "*.compressed|*.compressed|All files|*.*||");
if (dlg2.DoModal() != IDOK) return;

file2.Write(&fs, 8); // Запишем размер исходного файла

// m_mpd - это объект класса CMarkovProcessDef 
m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах

// Здесь начинается сжатие
// Начальный интервал - от 0x00000000 до 0xFFFFFFFF
DWORD dwBuf1 = 0; // Нижняя граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временная переменная

while (file1.Read(&b, 1))
{
// Вычисляем новый интервал
if (b > 0) dww = MulHigh(m_mpd.GetDistribution(b-1), dwBuf2); else dww = 0;
/*
m_mpd.GetDistribution(b-1) - Это S[b], т. о.
p[b] - это m_mpd.GetDistribution(b) - m_mpd.GetDistribution(b-1)

Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.
*/
dwBuf1 += dww;
if (b < 255) dwBuf2 = MulHigh(m_mpd.GetDistribution(b), dwBuf2) - dww; else dwBuf2 -= dww; while (((dwBuf1 ^ (dwBuf1 + dwBuf2)) & 0xFF000000) == 0) // Если старший байт буфера определен
{
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем его
dwBuf1 = dwBuf1 << 8; // И сдвигаем буфер
dwBuf2 = dwBuf2 << 8;
}
/*
PushSymbol(b, 0) перемещает внутренний указатель на распределение для следующего символа
*/
m_mpd.PushSymbol(b, 0);
}
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем последний байт
// Вот и всё
// Закрываем файлы
file1.Close();
file2.Close();
}

if (file1.Read(&fs, 8) != 8) return; // Читаем длину извлекаемого файла

// Читаем первые 4 байта
// Нужно поместить байты в переменную не в том порядке, в каком они в файле,
// поэтому читаем их по отдельности
for (int j = 3; j >= 0; j--) if (file1.Read(((LPBYTE)&dwBuf3)+j, 1) == 0) ((LPBYTE)&dwBuf3)[j] = 0xFF;

// Поиск методом половинного деления
do
{
m = (l+h)/2;
if (h <= l) break;
if (m_mpd.GetDistribution(m) <= v) l = m+1; else h = m;
} while (true);

// Вычисляем новый интервал
if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0;
dwBuf1 += dww;
dwBuf3 -= dww;
if (m < 255) dwBuf2 = MulHigh(m_mpd.GetDistribution(m), dwBuf2) - dww; else dwBuf2 -= dww; file2.Write(&m, 1); // Пишем символ
m_mpd.PushSymbol(m, 0); 

while (((dwBuf1 ^ (dwBuf1 + dwBuf2)) & 0xFF000000) == 0) // Если старший байт буфера определен
{
dwBuf1 = dwBuf1 << 8; // сдвигаем буфер
dwBuf2 = dwBuf2 << 8;
dwBuf3 = dwBuf3 << 8;
if (file1.Read(&dwBuf3, 1) == 0) dwBuf3 |= 0xFF;
// Читаем следующий байт, если есть, иначе ставим 0xFF
}
}
// Закрываем файлы
file1.Close();
file2.Close();
}

DWORD CArithmCompressorDlg::MulHigh(DWORD dw1, DWORD dw2)
{
/*
Эта функция возвращает старшее двойное слово
произведения данных двойных слов
*/
DWORD r;
_asm
{
mov eax, dw1;
mul dw2;
mov r, edx;
}
return r;
}

DWORD CArithmCompressorDlg::DivLarge(DWORD hi, DWORD lo, DWORD dw)
{
/*
Эта функция делит 64-битное беззнаковое целое (hi;lo)
на 32-битное
*/
DWORD r;
_asm
{
mov eax, lo;
mov edx, hi;
div dw;
mov r, eax;
}
return r;
}

Исходники