c++ - Lempel-Ziv-Welch 算法的解码问题

Question

我必须实现 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，我得到以下结果:

压缩.txt:1036045328

decompressed.txt:banana_bandana

但是如果我用所有 255 个 ASCII 字符初始化字典，解码过程就会失败。我认为问题出在代码中使用的位数，因为当我要解码时，我总是从输入文件中逐个字符(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 写入压缩文件作为 size_t 。

提前致谢!

Answer 1

看起来您正在将字典索引输出为 ASCII 编码数字。你打算如何从 12,3 或 1,23 中分辨出序列 1,2,3。您需要使用 9 位(10、11 或其他)数字或某种无前缀代码(如霍夫曼编码)以明确的方式对数据进行编码。