Вопрос или проблема
Я пытался реализовать алгоритм сжатия LZMW, модифицируя реализацию LZW:
main.cpp
#include <cstdint>
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
uint32_t write_pointer = 0;
uint32_t read_pointer = 0;
uint32_t dictionary_index;
const uint32_t BUFFER_SIZE = 65536;
char* buffer = new char[BUFFER_SIZE];
int32_t read_input_file(std::ifstream& fs_in, uint32_t length)
{
//Случай: чтение до середины буфера
if (write_pointer + length < BUFFER_SIZE)
{
fs_in.read(buffer + write_pointer, length);
int32_t bytes_read = fs_in.gcount();
write_pointer += bytes_read;
return length - bytes_read;
}
//Случай: чтение до конца буфера
if (write_pointer + length == BUFFER_SIZE)
{
fs_in.read(buffer + write_pointer, length);
int32_t bytes_read = fs_in.gcount();
write_pointer += bytes_read;
write_pointer -= (write_pointer >= BUFFER_SIZE) * BUFFER_SIZE;
return length - bytes_read;
}
//Случай: чтение с переходом за конец буфера
{
fs_in.read(buffer + write_pointer, BUFFER_SIZE - write_pointer);
int32_t bytes_read = fs_in.gcount();
write_pointer += bytes_read;
write_pointer -= (write_pointer >= BUFFER_SIZE) * BUFFER_SIZE;
if (write_pointer != 0)
return bytes_read;
fs_in.read(buffer, length - bytes_read);
int32_t bytes_read_2 = fs_in.gcount();
write_pointer += bytes_read_2;
write_pointer -= (write_pointer >= BUFFER_SIZE) * BUFFER_SIZE;
return length - (bytes_read + bytes_read_2);
}
}
char read_buffer()
{
char buf = buffer[read_pointer++];
read_pointer %= BUFFER_SIZE;
return buf;
}
void unread_buffer()
{
read_pointer += BUFFER_SIZE - 1;
read_pointer %= BUFFER_SIZE;
}
uint32_t buffer_bytes_available()
{
//Безопасно если (BUFFER_SIZE + write_pointer - read_pointer) < 2 * BUFFER_SIZE
return (BUFFER_SIZE + write_pointer - read_pointer) -
((BUFFER_SIZE + write_pointer - read_pointer) >= BUFFER_SIZE) * BUFFER_SIZE;
}
uint8_t bits_per_dictionary_id()
{
uint32_t index = dictionary_index;
uint32_t result = 1;
while (index >>= 1)
result++;
return result;
}
class Node
{
public:
uint32_t id;
std::string token;
Node(uint32_t id);
~Node();
};
Node::Node(uint32_t id)
{
this->id = id;
}
Node::~Node()
{
std::string().swap(token);
}
void compress_file(std::string file_in, std::string file_out)
{
std::ifstream fs_in(file_in, std::ifstream::binary);
std::ofstream fs_out(file_out, std::ofstream::binary);
bool input_file_end_reached = false;
bool last_index_to_write = false;
std::unordered_map<std::string, uint32_t> dictionary;
//Инициализация словаря
for (dictionary_index = 0; dictionary_index < 256; dictionary_index++)
dictionary.insert(std::pair<std::string, uint32_t>(string(1, static_cast<char>(dictionary_index)),
dictionary_index));
uint8_t data_out = 0;
int8_t data_out_position = 7;
//Чтение первого фрагмента файла
if (read_input_file(fs_in, BUFFER_SIZE - 1))
input_file_end_reached = true;
std::string previous_match = "";
while (buffer_bytes_available() > 0)
{
//Найти запись, которая еще не присутствует в словаре
std::string current_data;
int32_t index;
int32_t last_found_index = -1;
do
{
index = -1;
if (buffer_bytes_available() == 0)
{
last_index_to_write = true;
break;
}
current_data.push_back(read_buffer());
std::unordered_map<std::string, uint32_t>::iterator it = dictionary.find(current_data);
if (it != dictionary.end())
index = last_found_index = it->second;
} while (index != -1);
//Последний байт новой записи не кодируется last_found_index
if (buffer_bytes_available() > 0 && !last_index_to_write)
unread_buffer();
else
{
if (!last_index_to_write)
unread_buffer();
last_index_to_write = true;
}
//Записать выходные данные
for (int8_t i = bits_per_dictionary_id() - 1; i >= 0; i--)
{
data_out |= (((last_found_index >> i) & 0x01) << (data_out_position--));
if (data_out_position < 0)
{
fs_out << data_out;
data_out = 0;
data_out_position = 7;
}
}
//Этот код - тот, который я добавил
//Добавить новую запись в словарь
dictionary.insert(
std::pair<std::string, uint32_t>(previous_match + current_data, dictionary_index++));
previous_match = current_data;
//Код ниже - оригинальный
//Добавить новую запись в словарь
/*dictionary.insert(
std::pair<std::string, uint32_t>(current_data, dictionary_index++));*/
//Читать следующий фрагмент данных
if (!input_file_end_reached)
if (read_input_file(fs_in, BUFFER_SIZE - buffer_bytes_available() - 1))
input_file_end_reached = true;
}
//Если остались данные, записать их в выходной файл
if (data_out_position != 7)
fs_out << data_out;
}
void decompress_file(std::string file_in, std::string file_out)
{
std::ifstream fs_in(file_in, std::ifstream::binary);
std::ofstream fs_out(file_out, std::ofstream::binary);
std::vector<Node*> dictionary;
//Инициализация словаря
for (dictionary_index = 0; dictionary_index < 256; dictionary_index++)
{
Node* node = new Node(dictionary_index);
node->token.push_back(dictionary_index);
dictionary.push_back(node);
}
bool input_file_end_reached = false;
bool is_data_valid = true;
//Чтение первого фрагмента файла
if (read_input_file(fs_in, BUFFER_SIZE - 1))
input_file_end_reached = true;
uint8_t buf = read_buffer();
uint8_t bits_read = 0;
uint32_t data_read;
while (buffer_bytes_available() > 0 || bits_read < 8)
{
data_read = 0;
for (int8_t i = bits_per_dictionary_id() - 1; i >= 0; i--)
{
data_read <<= 1;
data_read |= ((buf >> (7 - bits_read)) & 0x01);
bits_read++;
if (bits_read == 8)
{
if (buffer_bytes_available() == 0)
{
if (i > 0)
is_data_valid = false;
break;
}
buf = read_buffer();
bits_read = 0;
}
}
if (!is_data_valid)
break;
//Пропустить в первом проходе цикла
if (dictionary_index > 256)
//Завершить предыдущую запись словаря
dictionary[dictionary_index - 1]->token.push_back(dictionary[data_read]->token[0]);
//Создать новую неполную запись словаря
Node* entry = new Node(dictionary_index++);
entry->token = dictionary[data_read]->token;
dictionary.push_back(entry);
//Записать данные, закодированные индексом
for (uint32_t i = 0; i < dictionary[data_read]->token.size(); i++)
fs_out << dictionary[data_read]->token[i];
//Читать следующий фрагмент данных
if (!input_file_end_reached)
if (read_input_file(fs_in, BUFFER_SIZE - buffer_bytes_available() - 1))
input_file_end_reached = true;
}
for (uint32_t i = 0; i < dictionary.size(); i++)
delete dictionary[i];
}
int main() {
compress_file("archive", "output");
decompress_file("output", "decompress");
return 0;
}
Единственное большое изменение по сравнению с оригинальным кодом LZW было внесено в функцию compress_file
: вместо того, чтобы просто добавлять current_data
в dictionary
, добавляется конкатенация previous_match
и current_data
, после чего current_data
присваивается как previous_match
. Я также изменил тип входных данных с vector<uint8_t>
на string
.
Проблема с моей реализацией – данные увеличиваются вместо сжатия, хотя оригинальные данные восстанавливаются без каких-либо потерь. Я протестировал это на нескольких наборах файлов, и сжатие увеличивает их размер примерно в 2,5-3 раза по сравнению с оригинальными данными:
canterbury: 2,810,994 bytes -> 7,205,628 bytes
large: 11,159,552 bytes -> 31,369,226 bytes
calgary: 3,251,759 bytes -> 8,415,799 bytes
Оригинальная реализация LZW фактически сжимает данные:
canterbury: 2,810,994 bytes -> 977,326 bytes
large: 11,159,552 bytes -> 3,507,560 bytes
calgary: 3,251,759 bytes -> 1,353,242 bytes
Есть идеи, что именно не так в коде, который я редактировал?
Ответ или решение
Код, который вы предоставили для реализации алгоритма сжатия LZMW, имеет несколько ключевых проблем, из-за которых данные после сжатия увеличиваются, а не уменьшаются. Давайте разберем ошибки и предложим пути их устранения.
1. Логика работы с предыдущими совпадениями
Ваша модификация алгоритма подразумевает добавление в словарь строки, представляющей собой конкатенацию previous_match
и current_data
. Эта логика может приводить к избыточным записям в словаре, особенно если данные имеют небольшие повторяющиеся последовательности. Вместо того чтобы эффективно сжимать данные, ваш метод может приводить к генерации большого количества уникальных символов, что приводит к увеличению размера выходных данных.
Решение:
Вернитесь к оригинальной логике LZW, где current_data
добавляется в словарь. Реализация LZW строится на принципе расширения существующего кода, основываясь на последних найденных совпадениях, а не на конкатенации строк.
2. Хранение и использование индексов словаря
В функции compress_file
, вы задействуете переменную previous_match
неправильно, что может привести к несоответствию между индексами записей в словаре и фактическим выводимым данным. Это также может быть причиной проблемы с перенаправлением потоков данных.
Решение:
Проверьте последовательность индексов в словаре. Убедитесь, что каждый созданный элемент действительно соответствует данным, которые вы обрабатываете, и что индексы указывают на корректные записи. Возможно, вам стоит завести отдельный буфер для хранения предыдущих совпадений, чтобы избежать путаницы.
3. Запись выходных данных
Код записи выходных данных также может быть источником проблем. Ваша реализация несет в себе несколько потенциальных источников ошибок, таких как недостающие биты или переполнение.
Решение:
Сосредоточьтесь на корректной передаче выходных данных в файл, идущих от индексов в словаре. Убедитесь, что все биты данных правильно упакованы и сбрасываются в выходной файл.
4. Инициализация и управление памятью
Убедитесь, что слова в словаре корректно освобождаются и не остаются в памяти, что может негативно отразиться на производительности. На данный момент у вас может происходить утечка памяти из-за неправильного управления объектами Node
.
Решение:
Добавьте корректные механизмы освобождения памяти для объектов, которые использовались в словаре, чтобы избежать утечек и ненужных затрат памяти.
Заключение
Резюмируя, ваш модифицированный алгоритм LZMW не выполняет свои функции оптимально из-за ключевых изменений в логике добавления строк в словарь и обработки данных на выходе. Сосредоточьтесь на использовании оригинального подхода к LZ, изучите его строение и попробуйте абстрагироваться от добавления кода, который может exacerbate проблему. С учетом указанного подхода и исправлений у вас есть возможность создать эффективный алгоритм сжатия, который действительно будет сжимать данные вместо их раздувания.