霍夫曼编码单个字符而不查找 table

Question

我正在尝试实施 Huffman 编码，但无法弄清楚如何在不生成查找的情况下使用 trie 对字符进行编码 table。我不想做的是生成每个字符与其编码的位串的映射。我正在尝试编写一种方法，该方法接受霍夫曼特里树的根和一个字符并吐出正确的代码。

我编写了以下无法正常工作的代码。问题是，我不知道如何让它在得到正确的结果后停止。它在到达正确的叶节点后继续添加到代码中。

string lookup(HuffNode* root, char c, string prevCode, string direction){
  string currentCode = prevCode + direction;
  if(!root->isLeaf()){
    currentCode = lookup(root->getLeft(), c, currentCode, "0");
    currentCode = lookup(root->getRight(), c, currentCode, "1");
  }else{
    if(root->getChar() == c){
      return currentCode;
    }else{
      return prevCode;
    }
  }

  return currentCode;
}

string encodeChar(HuffNode* trie, char c){
  return lookup(trie, c, "", "");
}

从 trie 中获取字符编码的正确方法是什么？

Answer 1

每次要发出代码时都必须搜索一大块树，这将是非常低效的。实际上，您应该为每个符号制作 table 个代码。

无论如何，您需要做的是在通过引用传递的单个字符串中构建代码。不要 return 这个字符串。（当它在最初通过引用传递的字符串中完成时，它将在那里。）而是 return true 或 false 表示是否在叶子中找到该符号。然后当你在每个分支上调用 lookup() 时，看看它是否 return 是真的。如果是，则立即 return 为真。对于每个调用，将适当的位添加到字符串（0 或 1）。如果第二个分支 return 为假，则删除您添加的位，并且 return 为假。

如果找到符号，原始调用将 return 为真，并且字符串将具有代码。如果它 return 为假，则符号不在任何叶子中，字符串将为空。

霍夫曼编码单个字符而不查找 table

Huffman encode single character without lookup table

c

c++

algorithm

huffman-code