Мне нужно реализовать алгоритм LZW, но я обнаружил некоторые проблемы с декодирующей частью.
Я думаю, что код правильный, потому что он работает с примером, который я нашел где-то в Интернете: если я инициализирую свой словарь следующим образом
m_dictionary.push_back("a");
m_dictionary.push_back("b");
m_dictionary.push_back("d");
m_dictionary.push_back("n");
m_dictionary.push_back("_");
и мой входной файл содержит строку banana_bandana, я получаю следующие результаты:
compressed.txt: 1036045328
decompressed.txt: banana_bandana
Но если я инициализирую словарь всеми 255 символами ASCII, процесс декодирования с треском провалится. Я думаю, что проблема заключается в количестве битов, используемых в кодах, потому что, когда я собираюсь декодировать, я всегда читаю из входного файла char по char (8 бит) вместо правильного количества бит, я думаю.
Ниже приведен код моей реализации этого алгоритма:
template <class T>
size_t toUnsigned(T t) {
std::stringstream stream;
stream << t;
size_t x;
stream >> x;
return x;
}
bool LempelZivWelch::isInDictionary(const std::string& entry) {
return (std::find(m_dictionary.begin(), m_dictionary.end(), entry) != m_dictionary.end());
}
void LempelZivWelch::initializeDictionary() {
m_dictionary.clear();
for (int i = 0; i < 256; ++i)
m_dictionary.push_back(std::string(1, char(i)));
}
void LempelZivWelch::addEntry(std::string entry) {
m_dictionary.push_back(entry);
}
size_t LempelZivWelch::encode(char *data, size_t dataSize) {
initializeDictionary();
std::string s;
char c;
std::ofstream file;
file.open("compressed.txt", std::ios::out | std::ios::binary);
for (size_t i = 0; i < dataSize; ++i) {
c = data[i];
if(isInDictionary(s + c))
s = s + c;
else {
for (size_t j = 0; j < m_dictionary.size(); ++j)
if (m_dictionary[j] == s) {
file << j;
break;
}
addEntry(s + c);
s = c;
}
}
for (size_t j = 0; j < m_dictionary.size(); ++j)
if (m_dictionary[j] == s) {
file << j;
break;
}
file.close();
return dataSize;
}
size_t LempelZivWelch::decode(char *data, size_t dataSize) {
initializeDictionary();
std::string entry;
char c;
size_t previousCode, currentCode;
std::ofstream file;
file.open("decompressed.txt", std::ios::out | std::ios::binary);
previousCode = toUnsigned(data[0]);
file << m_dictionary[previousCode];
for (size_t i = 1; i < dataSize; ++i) {
currentCode = toUnsigned(data[i]);
entry = m_dictionary[currentCode];
file << entry;
c = entry[0];
addEntry(m_dictionary[previousCode] + c);
previousCode = currentCode;
}
file.close();
return dataSize;
}
И это функция, которая читает входные файлы:
void Compression::readFile(std::string filename) {
std::ifstream file;
file.open(filename.c_str(), std::ios::in | std::ios::binary | std::ios::ate);
if (!file.is_open())
exit(EXIT_FAILURE);
m_dataSize = file.tellg();
m_data = new char [m_dataSize];
file.seekg(0, std::ios::beg);
file.read(m_data, m_dataSize);
file.close();
}
Я предполагаю, что проблема декодирования заключается в чтении входного файла в виде массива chars и / или записи в сжатый файл char s как size_t.
Заранее спасибо!