«Hello, World!» от мира сжатия данных. Канонический алгоритм сжатия данных Хаффмана
На данную тему была написана не одна сотня статей, но во всех, что видел, для построения двоичного дерева поиска использовались структуры по типу приоритетной очереди, хотя достаточно отсортировать массив частот в порядке убывания и отбрасывать последние две буквы из алфавита. В этой статье хотел представить реализацию данного алгоритма на языке C++.
Канонический алгоритм Хаффмана для сжатия можно разделить на следующие шаги:
Подсчёт частот каждой буквы в файле и составление алфавита.
Построение элементарного кода для каждой буквы алфавита.
Сжатие данных с помощью полученных элементарных кодов.
Процесс сжатия происходит за два чтения файла, сначала считываем файл для получения частот букв, потом считываем файл и заменяем букву алфавита на её элементарный код.
Ниже представлен код для подсчёта частот букв в файле. В качестве хранилища для частот использован вектор letter_count, по сути представляет из себя ассоциированный массив <буква, частота>, чтобы получить доступ к частоте буквы, достаточно обратиться по индексу, равному численному представлению буквы в кодировке.
void count_frequency(const std::string &filename, std::vector &letter_count)
{
std::ifstream file(filename, std::ios_base::binary);
uint8_t c;
while ( file.read((char* )&c, 1) )
letter_count[c]++;
file.close();
}
struct data_about_letter_vector
{
std::vector letter_vector;
uint64_t count;
};
void create_alphabet(std::vector &alphabet, const std::vector &letter_count)
{
size_t size = 0;
for (size_t i = 0; i < 256; i++)
if ( letter_count[i] ) {
alphabet[size].letter_vector.push_back(i);
alphabet[size].count = letter_count[i];
size++;
}
alphabet.resize(size);
}
void count_frequency_and_create_alphabet(const std::string &filename, std::vector &alphabet)
{
std::vector letter_count(256);
count_frequency(filename, letter_count);
create_alphabet(alphabet, letter_count);
} Далее приступаем к формированию элементарных кодов для каждой буквы алфавита.
Словесное описание алгоритма построения элементарных кодов.
bool compare(const data_about_letter_vector &left, const data_about_letter_vector &right)
{
return left.count > right.count;
}
void create_elementary_codes(std::vector &B, std::vector &shift, const std::string &filename)
{
std::vector alphabet(256);
count_frequency_and_create_alphabet(filename, alphabet);
size_t size = alphabet.size();
std::sort(alphabet.begin(), alphabet.end(), compare);
while ( size > 2 ) {
size_t pos0 = size - 2, pos1 = pos0 + 1;
for ( uint8_t a : alphabet[pos0].letter_vector )
shift[a]++;
for ( uint8_t a : alphabet[pos1].letter_vector ) {
B[a] = ( 1ULL << shift[a] ) | B[a];
shift[a]++;
}
data_about_letter_vector temp;
for ( uint8_t a : alphabet[pos0].letter_vector )
temp.letter_vector.push_back(a);
for ( uint8_t a : alphabet[pos1].letter_vector )
temp.letter_vector.push_back(a);
temp.count = alphabet[pos0].count + alphabet[pos1].count;
size -= 2;
alphabet.resize(size);
uint8_t pos_to_insert = size;
while ( pos_to_insert && ( alphabet[ pos_to_insert - 1 ].count < temp.count ) )
pos_to_insert--;
alphabet.insert(alphabet.begin() + pos_to_insert, temp);
size++;
}
if ( size == 1 )
shift[ alphabet[0].letter_vector[0] ]++;
else {
size_t pos0 = size - 2, pos1 = pos0 + 1;
for ( uint8_t a : alphabet[pos0].letter_vector )
shift[a]++;
for ( uint8_t a : alphabet[pos1].letter_vector ) {
B[a] = ( 1ULL << shift[a] ) | B[a];
shift[a]++;
}
}
} Элементарные коды сформированы, можно приступать к сжатию данных. Однако для разжатия данных, необходимо будет сохранить элементарные коды, в данной реализации они представляют из себя два вектора, один содержит элементарный код для букв алфавита (вектор B), другой длину этого самого элементарного кода (вектор shift). Помимо всего реализация имеет один изъян, последний байт может быть не до конца сформирован, из-за чего в процессе разжатия данные могут быть неправильно проинтерпретированы. Поэтому, если байт не был до конца сформирован, то просто пишу его длину в битах и его значение в отдельный файл данных, необходимых для разжатия.
void write_elementary_codes_into_file(const std::vector &B, const std::vector &shift, const uint8_t &length_of_last_byte, const uint8_t &last_byte)
{
std::ofstream out("data_for_decompress.bin", std::ios_base::binary);
out.write((char* )&length_of_last_byte, 1);
out.write((char* )&last_byte, 1);
out.write((char* )&( B[0] ), 2048);
out.write((char* )&( shift[0] ), 256);
out.close();
}
void compress_file(const std::vector &B, const std::vector &shift, const std::string &filename)
{
std::cout << "Начало сжатия\n";
uint8_t byte = 0, length = 0;
std::ofstream out("compressed_data.bin", std::ios_base::binary);
std::ifstream file(filename, std::ios_base::binary);
uint8_t c;
while ( file.read((char* )(&c), 1) ) {
uint64_t elementary_code = B[c];
uint8_t s = shift[c];
uint64_t mask = ( 1ULL << s ) - 1;
while ( s ) {
uint8_t need_bit_length = 8 - length;
if ( need_bit_length > s ) {
byte |= elementary_code << ( need_bit_length - s );
length += s;
s = 0;
}
else {
s -= need_bit_length;
byte |= elementary_code >> s;
mask >>= need_bit_length;
elementary_code &= mask;
out.write((char* )&byte, 1);
byte = 0;
length = 0;
}
}
}
out.close();
file.close();
write_elementary_codes_into_file(B, shift, length, byte);
} С сжатием закончили, далее разжатие. Для разжатия необходимо построение двоичного дерева поиска по записанным ранее в файл элементарным кодам.
Код для дерева был украден, но была модифицирована функция добавления элемента в дерево.
Поиск по двоичному дереву для декодирования элементарного кода в букву представляет из себя переход от корня дерева по его потомкам (1 — означает перейти к правому потомку, 0 — к левому) до тех пока не найдем лист, который содержит букву. way — это и есть элементарный код, элемент вектора B, way_length — это длина элементарного кода, элемент вектора shift.
class Tree_element
{
public:
bool data_exist;
uint8_t data;
Tree_element* left;
Tree_element* right;
Tree_element();
};
class Binary_tree
{
public:
Tree_element* root;
Binary_tree();
~Binary_tree();
void delete_tree(Tree_element* current);
void insert(const uint8_t &letter, const uint64_t &way, const uint8_t &way_length);
};
Tree_element::Tree_element()
{
data_exist = false;
left = nullptr;
right = nullptr;
}
Binary_tree::Binary_tree()
{
root = new Tree_element();
}
void Binary_tree::delete_tree(Tree_element* current)
{
if ( current != nullptr ) {
delete_tree(current->left);
delete_tree(current->right);
delete current;
}
}
Binary_tree::~Binary_tree()
{
delete_tree(root);
}
void Binary_tree::insert(const uint8_t &letter, const uint64_t &way, const uint8_t &way_length)
{
uint64_t mask = 1ULL << ( way_length - 1 );
Tree_element* current = root;
while ( mask ){
if ( way & mask ) {
if ( current->right != nullptr )
current = current->right;
else {
current->right = new Tree_element();
current = current->right;
}
}
else {
if ( current->left != nullptr )
current = current->left;
else {
current->left = new Tree_element();
current = current->left;
}
}
mask >>= 1;
}
current->data = letter;
current->data_exist = true;
}Чтение данных, необходимых для разжатия.
void read_data_for_decompress(std::vector &B, std::vector &shift, uint8_t &length_of_last_byte, uint8_t &last_byte)
{
std::ifstream file("data_for_decompress.bin", std::ios_base::binary);
file.read((char* )&length_of_last_byte, 1);
file.read((char* )&last_byte, 1);
file.read((char* )&( B[0] ), 2048);
file.read((char* )&( shift[0] ), 256);
file.close();
} Построение двоичного дерева поиска по элементарным кодам.
void create_binary_tree_of_elementary_codes(const std::vector &alphabet, const std::vector &B, const std::vector &shift, Binary_tree &tree)
{
size_t size = alphabet.size();
for (size_t i = 0; i < size; i++)
tree.insert(alphabet[i], B[ alphabet[i] ], shift[ alphabet[i] ]);
} Разжатие данных.
void decompress_data_from_file(Tree_element* const root, const std::string &filename, uint8_t &length_of_last_byte, const uint8_t &last_byte)
{
std::cout << "Начало разжатия\n";
std::ifstream reading("compressed_data.bin", std::ios_base::binary);
std::ofstream writing(filename, std::ios_base::binary);
Tree_element* current = root;
uint8_t byte = 0;
while ( reading.read((char* )&byte, 1) ) {
uint8_t mask = 1 << 7;
while ( mask ) {
do {
if ( byte & mask )
current = current->right;
else
current = current->left;
mask >>= 1;
} while ( mask && !current->data_exist );
if ( current->data_exist ) {
writing.write( (char* )&( current->data ), 1);
current = root;
}
}
}
uint8_t mask = 1 << 7;
while ( length_of_last_byte ) {
do {
if ( last_byte & mask )
current = current->right;
else
current = current->left;
mask >>= 1;
length_of_last_byte--;
} while ( !current->data_exist );
writing.write( (char* )&( current->data ), 1);
current = root;
}
reading.close();
writing.close();
}Плюсы реализации:
Канонический алгоритм Хаффмана для построения элементарных кодов.
Использование побитовых операций.
Нет необходимости хранить алфавит, алфавит можно восстановить по вектору shift, если длина элементарного кода для буквы равна нулю, то буквы нет в алфавите.
Минусы реализации:
Костыли для обработки несформировавшегося байта.
Куча библиотек, а именно <vector>, <string> и <algorithm>(отсюда взята сортировка).
Отсутствие возможности выбора размера буквы.
Большой размер файла необходимого для разжатия данных. 2 + 256×8 + 256 байт.
Интересной особенностью реализации является то, что она не требует построения двоичного дерева поиска для сжатия данных.
Характеристики канонического алгоритма Хаффмана.
Алгоритм Хаффмана прекрасно сжимает текстовые файлы, когда размер алфавита не очень большой и символы встречаются часто. С другими типами файлов ситуация хуже, поэтому использовать его для них неоптимально.
Полный код, разделённый на модули, можно посмотреть по ссылке
Написание статьи вдохновлено прочтением книги: Ватолин Д., Ратушняк А., Смирнов М., Юкин В. «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.» — М.: ДИАЛОГ-МИФИ, 2003. — 384 с
