Write a program to decipher messages encoded using a prefix code, given the enco

Question

Write a program to decipher messages encoded using a prefix code, given the encoding tree. Such codes are widely used in applications that compress data, including JPEG for images, MP3 for music, and DivX for video. using Huffman Trees (Prefix Binary Trees) c++

Explanation / Answer

#include #include #include #include // for CHAR_BIT #include #include const int UniqueSymbols = 1 f), left(c0), right(c1) {} ~InternalNode() { delete left; delete right; } }; class LeafNode : public INode { public: const char c; LeafNode(int f, char c) : INode(f), c(c) {} }; struct NodeCmp { bool operator()(const INode* lhs, const INode* rhs) const { return lhs->f > rhs->f; } }; INode* BuildTree(const int (&frequencies)[UniqueSymbols]) { std::priority_queue trees; for (int i = 0; i 1) { INode* childR = trees.top(); trees.pop(); INode* childL = trees.top(); trees.pop(); INode* parent = new InternalNode(childR, childL); trees.push(parent); } return trees.top(); } void GenerateCodes(const INode* node, const HuffCode& prefix, HuffCodeMap& outCodes) { if (const LeafNode* lf = dynamic_cast(node)) { outCodes[lf->c] = prefix; } else if (const InternalNode* in = dynamic_cast(node)) { HuffCode leftPrefix = prefix; leftPrefix.push_back(false); GenerateCodes(in->left, leftPrefix, outCodes); HuffCode rightPrefix = prefix; rightPrefix.push_back(true); GenerateCodes(in->right, rightPrefix, outCodes); } } int main() { // Build frequency table int frequencies[UniqueSymbols] = {0}; const char* ptr = SampleString; while (*ptr != '') ++frequencies[*ptr++]; INode* root = BuildTree(frequencies); HuffCodeMap codes; GenerateCodes(root, HuffCode(), codes); delete root; for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it) { std::cout second.end(), std::ostream_iterator(std::cout)); std::cout

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.