На данную тему была написана не одна сотня статей, но во всех, что видел, для построения двоичного дерева поиска использовались структуры по типу приоритетной очереди, хотя достаточно отсортировать массив частот в порядке убывания и отбрасывать последние две буквы с самыми маленькими частотами из алфавита, объединяя их в новую "псевдо-букву", но можно даже обойтись без постройки бинарного дерева поиска, чтобы сжать данные. В этой статье хотел представить реализацию данного алгоритма на языке C++.
Канонический алгоритм Хаффмана для сжатия можно разделить на следующие шаги:
Подсчёт частот каждой буквы в файле и составление алфавита.
Построение элементарного кода для каждой буквы алфавита.
Сжатие данных с помощью полученных элементарных кодов.
Процесс сжатия происходит за две процедуры чтения файла, сначала считываем файл для получения частот букв, потом считываем файл и заменяем букву алфавита на её элементарный код.
Ниже представлен код для подсчёта частот букв в файле. В качестве хранилища для частот использован вектор letter_count, по сути представляет из себя ассоциированный массив <буква, частота>, чтобы получить доступ к частоте буквы, достаточно обратиться по индексу, равному численному представлению буквы в кодировке.
void count_frequency(const std::string &filename, std::vector<uint64_t> &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<uint8_t> letter_vector;
uint64_t count;
};
void create_alphabet(std::vector<data_about_letter_vector> &alphabet, const std::vector<uint64_t> &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<data_about_letter_vector> &alphabet)
{
std::vector<uint64_t> 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<uint64_t> &B, std::vector<uint8_t> &shift, const std::string &filename)
{
std::vector<data_about_letter_vector> alphabet(256);
count_frequency_and_create_alphabet(filename, alphabet);
size_t size = alphabet.size();
std::sort(alphabet.begin(), alphabet.end(), compare);
std::vector<uint8_t> temp_array(256);
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]++;
}
size_t temp_array_size = 0;
for ( uint8_t a : alphabet[pos0].letter_vector )
temp_array[ temp_array_size++ ] = a;
for ( uint8_t a : alphabet[pos1].letter_vector )
temp_array[ temp_array_size++ ] = a;
uint64_t sum_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 < sum_count ) )
pos_to_insert--;
alphabet.insert(alphabet.begin() + pos_to_insert, data_about_letter_vector());
alphabet[pos_to_insert].count = sum_count;
alphabet[pos_to_insert].letter_vector.resize(temp_array_size);
for (size_t i = 0; i < temp_array_size; i++)
alphabet[pos_to_insert].letter_vector[i] = temp_array[i];
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<uint64_t> &B, const std::vector<uint8_t> &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<uint64_t> &B, const std::vector<uint8_t> &shift, const std::string &filename)
{
std::cout << "Начало сжатия\n";
uint8_t byte = 0, length = 0, c;
std::ofstream out("compressed_data.bin", std::ios_base::binary);
std::ifstream file(filename, std::ios_base::binary);
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 = NULL;
right = NULL;
}
Binary_tree::Binary_tree()
{
root = new Tree_element();
}
void Binary_tree::delete_tree(Tree_element* current)
{
if ( current ) {
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 )
current->right = new Tree_element();
current = current->right;
}
else {
if ( !current->left )
current->left = new Tree_element();
current = current->left;
}
mask >>= 1;
}
current->data = letter;
current->data_exist = true;
}Чтение данных, необходимых для разжатия.
void read_data_for_decompress(std::vector<uint64_t> &B, std::vector<uint8_t> &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(uint8_t &length_of_last_byte, uint8_t &last_byte, Binary_tree &tree)
{
std::vector<uint64_t> B(256);
std::vector<uint8_t> shift(256);
read_data_for_decompress(B, shift, length_of_last_byte, last_byte);
std::vector<uint8_t> alphabet(256);
size_t size = 0;
for (size_t i = 0; i < 256; i++)
if ( shift[i] )
alphabet[size++] = i;
size_t count = 0;
for (size_t i = 0; i < size; i++)
tree.insert(alphabet[i], B[ alphabet[i] ], shift[ alphabet[i] ]);
for (size_t i = 0; i < size; i++)
count += (size_t)( get_letter_by_way(B[ alphabet[i] ], shift[ alphabet[i] ], tree.root) == alphabet[i] );
if ( count != size ) {
std::cout << "Ошибка в создании двоичного дерева поиска.\n";
exit(2);
}
}Разжатие данных.
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 с
