Write a program that takes any input text and produces both a frequency table an

Question

Write a program that takes any input text and produces both a frequency table and the corresponding Huffman code. Take approximately 360 words from any English document as your input text. Ignore all blanks, all punctuation marks, all special symbols. Create an input file with this input text. Construct the frequency table according to the input text read from the file, in the form:

symbol frequency

A .

.    .

.   .

m    .

.    .

.    .

7    .

Then, using the Huffman algorithm, construct the optimal prefix binary code for the table. Design your program to read the input from the input file "infile.dat". Your program must produce the output, in the file "outfile.dat", consisting of:

the frequency table for the source text,

the Huffman code for each letter and digit in the source code,

and the length of the coded message in terms of number of bits.

Explanation / Answer

Answer:

The functions for the code are given as below :

char decode(TreeNode root, char message[])
{
    char result = "";
    TreeNode node = root;
    for (int i = 0; i != message.size(); ++i)
    {
        if (message[i] == '0') {
            node = node->left;
        } else {
            assert(message[i] == '1');
            node = node->right;
        }
        if (node->is_leaf() == true)
        {
            result += node->letter;
            node = root;
        }
    }
    return result;
}

void HuffmanCodes(char given_data[], int frequency[], int size_taken)
{
    struct MinHeapNode *left, *right, *top;
   priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minimumHeap;
    for (int i = 0; i < size_taken; ++i)
        minimumHeap.push(new MinHeapNode(given_data[i], frequency[i]));
while (minimumHeap.size_taken() != 1)
    {
      
        left = minimumHeap.top();
        minimumHeap.pop();

        right = minimumHeap.top();
        minimumHeap.pop();
    top = new MinHeapNode('$', left->frequency + right->frequency);
        top->left = left;
        top->right = right;
        minimumHeap.push(top);
    }

  
    printCodes(minimumHeap.top(), "");
}

void Encode(const INode* node, const HuffCode& start, HuffCodeMap& outcomeofcode)
{
    if (const LeafNode* exist = dynamic_cast<const LeafNode*>(node))
    {
        outcomeofcode[exist ->c] = start;
    }
    else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))
    {
        HuffCode steady = start;
        steady.push_back(false);
        Encode(in->left, steady, outcomeofcode);

        HuffCode gain = start;
        gain.push_back(true);
        Encode(in->right, gain, outcomeofcode);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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