Question

C++ Data Structures:

Use Huffman coding to encode text in given file (Pride_and_Prejudice.txt).

TO_DO:

Define a struct for Huffman tree node. This struct contains links to left/right child nodes, a character, and its frequency.Define a function for file reading operation. This function should take in a filename (string type) as parameter and return a proper data structure object that contains characters and their frequencies that will be used to generate Huffman tree nodes.The construction of Huffman tree requires taking two nodes with smallest frequencies. Select a proper data structure to support this operation. Note this data structure object could be different to the object from step 2.

Design a function that takes in the root of Huffman coding tree, prints, and returns the encoding scheme in a data structure object.Design a function that takes in the encoding scheme and filename (string type), output encoded content (bit-string) to a file named pride.huff

Pride_and_Prejudice.txt:

Chapter 1

It is a truth universally acknowledged, that a single man in possession of a good fortune, must be in want of a wife. However little known the feelings or views of such a man may be on his first entering a neighbourhood, this truth is so well fixed in the minds of the surrounding families, that he is considered the rightful property of some one or other of their daughters. “My dear Mr. Bennet,” said his lady to him one day, “have you heard that Netherfield Park is let at last?” Mr. Bennet replied that he had not. “But it is,” returned she; “for Mrs. Long has just been here, and she told me all about it.” Mr. Bennet made no answer. “Do you not want to know who has taken it?” cried his wife impatiently. “You want to tell me, and I have no objection to hearing it.” This was invitation enough. “Why, my dear, you must know, Mrs. Long says that Netherfield is taken by a young man of large fortune from the north of England; that he came down on Monday in a chaise and four to see the place, and was so much delighted with it, that he agreed with Mr. Morris immediately; that he is to take possession before Michaelmas, and some of his servants are to be in the house by the end of next week.” “What is his name?” “Bingley.” “Is he married or single?” “Oh! Single, my dear, to be sure! A single man of large fortune; four or five thousand a year. What a fine thing for our girls!” “How so? How can it affect them?” “My dear Mr. Bennet,” replied his wife, “how can you be so tiresome! You must know that I am thinking of his marrying one of them.” “Is that his design in settling here?” “Design! Nonsense, how can you talk so! But it is very likely that he may fall in love with one of them, and therefore you must visit him as soon as he comes.” “I see no occasion for that. You and the girls may go, or you may send them by themselves, which perhaps will be still better, for as you are as handsome as any of them, Mr. Bingley may like you the best of the party.” “My dear, you flatter me. I certainly have had my share of beauty, but I do not pretend to be anything extraordinary now. When a woman has five grown-up daughters, she ought to give over thinking of her own beauty.” “In such cases, a woman has not often much beauty to think of.” “But, my dear, you must indeed go and see Mr. Bingley when he comes into the neighbourhood.” “It is more than I engage for, I assure you.” “But consider your daughters. Only think what an establishment it would be for one of them. Sir William and Lady Lucas are determined to go, merely on that account, for in general, you know, they visit no newcomers. Indeed you must go, for it will be impossible for us to visit him if you do not.” “You are over-scrupulous, surely. I dare say Mr. Bingley will be very glad to see you; and I will send a few lines by you to assure him of my hearty consent to his marrying whichever he chooses of the girls; though I must throw in a good word for my little Lizzy.” “I desire you will do no such thing. Lizzy is not a bit better than the others; and I am sure she is not half so handsome as Jane, nor half so good-humoured as Lydia. But you are always giving her the preference.” “They have none of them much to recommend them,” replied he; “they are all silly and ignorant like other girls; but Lizzy has something more of quickness than her sisters.” “Mr. Bennet, how can you abuse your own children in such a way? You take delight in vexing me. You have no compassion for my poor nerves.” “You mistake me, my dear. I have a high respect for your nerves. They are my old friends. I have heard you mention them with consideration these last twenty years at least.” “Ah, you do not know what I suffer.” “But I hope you will get over it, and live to see many young men of four thousand a year come into the neighbourhood.” “It will be no use to us, if twenty such should come, since you will not visit them.” “Depend upon it, my dear, that when there are twenty, I will visit them all.” Mr. Bennet was so odd a mixture of quick parts, sarcastic humour, reserve, and caprice, that the experience of three-and-twenty years had been insufficient to make his wife understand his character. Her mind was less difficult to develop. She was a woman of mean understanding, little information, and uncertain temper. When she was discontented, she fancied herself nervous. The business of her life was to get her daughters married; its solace was visiting and news. Chapter 2 Mr. Bennet was among the earliest of those who waited on Mr. Bingley. He had always intended to visit him, though to the last always assuring his wife that he should not go; and till the evening after the visit was paid she had no knowledge of it. It was then disclosed in the following manner. Observing his second daughter employed in trimming a hat, he suddenly addressed her with: “I hope Mr. Bingley will like it, Lizzy.” “We are not in a way to know what Mr. Bingley likes,” said her mother resentfully, “since we are not to visit.” “But you forget, mamma,” said Elizabeth, “that we shall meet him at the assemblies, and that Mrs. Long promised to introduce him.” “I do not believe Mrs. Long will do any such thing. She has two nieces of her own. She is a selfish, hypocritical woman, and I have no opinion of her.” “No more have I,” said Mr. Bennet; “and I am glad to find that you do not depend on her serving you.” Mrs. Bennet deigned not to make any reply, but, unable to contain herself, began scolding one of her daughters. “Don’t keep coughing so, Kitty, for Heaven’s sake! Have a little compassion on my nerves. You tear them to pieces.” “Kitty has no discretion in her coughs,” said her father; “she times them ill.” “I do not cough for my own amusement,” replied Kitty fretfully. “When is your next ball to be, Lizzy?” “To-morrow fortnight.” “Aye, so it is,” cried her mother, “and Mrs. Long does not come back till the day before; so it will be impossible for her to introduce him, for she will not know him herself.” “Then, my dear, you may have the advantage of your friend, and introduce Mr. Bingley to her.” “Impossible, Mr. Bennet, impossible, when I am not acquainted with him myself; how can you be so teasing?” “I honour your circumspection. A fortnight’s acquaintance is certainly very little. One cannot know what a man really is by the end of a fortnight. But if we do not venture somebody else will; and after all, Mrs. Long and her nieces must stand their chance; and, therefore, as she will think it an act of kindness, if you decline the office, I will take it on myself.” The girls stared at their father. Mrs. Bennet said only, “Nonsense, nonsense!” “What can be the meaning of that emphatic exclamation?” cried he. “Do you consider the forms of introduction, and the stress that is laid on them, as nonsense? I cannot quite agree with you there. What say you, Mary? For you are a young lady of deep reflection, I know, and read great books and make extracts.” Mary wished to say something sensible, but knew not how. “While Mary is adjusting her ideas,” he continued, “let us return to Mr. Bingley.” “I am sick of Mr. Bingley,” cried his wife. “I am sorry to hear that; but why did not you tell me that before? If I had known as much this morning I certainly would not have called on him. It is very unlucky; but as I have actually paid the visit, we cannot escape the acquaintance now.” The astonishment of the ladies was just what he wished; that of Mrs. Bennet perhaps surpassing the rest; though, when the first tumult of joy was over, she began to declare that it was what she had expected all the while. “How good it was in you, my dear Mr. Bennet! But I knew I should persuade you at last. I was sure you loved your girls too well to neglect such an acquaintance. Well, how pleased I am! and it is such a good joke, too, that you should have gone this morning and never said a word about it till now.” “Now, Kitty, you may cough as much as you choose,” said Mr. Bennet; and, as he spoke, he left the room, fatigued with the raptures of his wife. “What an excellent father you have, girls!” said she, when the door was shut. “I do not know how you will ever make him amends for his kindness; or me, either, for that matter. At our time of life it is not so pleasant, I can tell you, to be making new acquaintances every day; but for your sakes, we would do anything. Lydia, my love, though you are the youngest, I dare say Mr. Bingley will dance with you at the next ball.” “Oh!” said Lydia stoutly, “I am not afraid; for though I am the youngest, I’m the tallest.” The rest of the evening was spent in conjecturing how soon he would return Mr. Bennet’s visit, and determining when they should ask him to dinner. Chapter 3 Not all that Mrs. Bennet, however, with the assistance of her five daughters, could ask on the subject, was sufficient to draw from her husband any satisfactory description of Mr. Bingley. They attacked him in various ways—with barefaced questions, ingenious suppositions, and distant surmises; but he eluded the skill of them all, and they were at last obliged to accept the second-hand intelligence of their neighbour, Lady Lucas. Her report was highly favourable. Sir William had been delighted with him. He was quite young, wonderfully handsome, extremely agreeable, and, to crown the whole, he meant to be at the next assembly with a large party. Nothing could be more delightful! To be fond of dancing was a certain step towards falling in love; and very lively hopes of Mr. Bingley’s heart were entertained. “If I can but see one of my daughters happily settled at Netherfield,” said Mrs. Bennet to her husband, “and all the others equally well married, I shall have nothing to wish for.” In a few days Mr. Bingley returned Mr. Bennet’s visit, and sat about ten minutes with him in his library. He had entertained hopes of being admitted to a sight of the young ladies, of whose beauty he had heard much; but he saw only the father. The ladies were somewhat more fortunate, for they had the advantage of ascertaining from an upper window that he wore a blue coat, and rode a black horse. An invitation to dinner was soon afterwards dispatched; and already had Mrs. Bennet planned the courses that were to do credit to her housekeeping, when an answer arrived which deferred it all. Mr. Bingley was obliged to be in town the following day, and, consequently, unable to accept the honour of their invitation, etc. Mrs. Bennet was quite disconcerted. She could not imagine what business he could have in town so soon after his arrival in Hertfordshire; and she began to fear that he might be always flying about from one place to another, and never settled at Netherfield as he ought to be. Lady Lucas quieted her fears a little by starting the idea of his being gone to London only to get a large party for the ball; and a report soon followed that Mr. Bingley was to bring twelve ladies and seven gentlemen with him to the assembly. The girls grieved over such a number of ladies, but were comforted the day before the ball by hearing, that instead of twelve he brought only six with him from London—his five sisters and a cousin. And when the party entered the assembly room it consisted of only five altogether—Mr. Bingley, his two sisters, the husband of the eldest, and another young man. Mr. Bingley was good-looking and gentlemanlike; he had a pleasant countenance, and easy, unaffected manners. His sisters were fine women, with an air of decided fashion. His brother-in-law, Mr. Hurst, merely looked the gentleman; but his friend Mr. Darcy soon drew the attention of the room by his fine, tall person, handsome features, noble mien, and the report which was in general circulation within five minutes after his entrance, of his having ten thousand a year. The gentlemen pronounced him to be a fine figure of a man, the ladies declared he was much handsomer than Mr. Bingley, and he was looked at with great admiration for about half the evening, till his manners gave a disgust which turned the tide of his popularity; for he was discovered to be proud; to be above his company, and above being pleased; and not all his large estate in Derbyshire could then save him from having a most forbidding, disagreeable countenance, and being unworthy to be compared with his friend. Mr. Bingley had soon made himself acquainted with all the principal people in the room; he was lively and unreserved, danced every dance, was angry that the ball closed so early, and talked of giving one himself at Netherfield. Such amiable qualities must speak for themselves. What a contrast between him and his friend! Mr. Darcy danced only once with Mrs. Hurst and once with Miss Bingley, declined being introduced to any other lady, and spent the rest of the evening in walking about the room, speaking occasionally to one of his own party. His character was decided. He was the proudest, most disagreeable man in the world, and everybody hoped that he would never come there again. Amongst the most violent against him was Mrs. Bennet, whose dislike of his general behaviour was sharpened into particular resentment by his having slighted one of her daughters. Elizabeth Bennet had been obliged, by the scarcity of gentlemen, to sit down for two dances; and during part of that time, Mr. Darcy had been standing near enough for her to hear a conversation between him and Mr. Bingley, who came from the dance for a few minutes, to press his friend to join it. “Come, Darcy,” said he, “I must have you dance. I hate to see you standing about by yourself in this stupid manner. You had much better dance.” “I certainly shall not. You know how I detest it, unless I am particularly acquainted with my partner. At such an assembly as this it would be insupportable. Your sisters are engaged, and there is not another woman in the room whom it would not be a punishment to me to stand up with.” “I would not be so fastidious as you are,” cried Mr. Bingley, “for a kingdom! Upon my honour, I never met with so many pleasant girls in my life as I have this evening; and there are several of them you see uncommonly pretty.” “You are dancing with the only handsome girl in the room,” said Mr. Darcy, looking at the eldest Miss Bennet. “Oh! She is the most beautiful creature I ever beheld! But there is one of her sisters sitting down just behind you, who is very pretty, and I dare say very agreeable. Do let me ask my partner to introduce you.” “Which do you mean?” and turning round he looked for a moment at Elizabeth, till catching her eye, he withdrew his own and coldly said: “She is tolerable, but not handsome enough to tempt me; I am in no humour at present to give consequence to young ladies who are slighted by other men. You had better return to your partner and enjoy her smiles, for you are wasting your time with me.” Mr. Bingley followed his advice. Mr. Darcy walked off; and Elizabeth remained with no very cordial feelings toward him. She told the story, however, with great spirit among her friends; for she had a lively, playful disposition, which delighted in anything ridiculous. The evening altogether passed off pleasantly to the whole family. Mrs. Bennet had seen her eldest daughter much admired by the Netherfield party. Mr. Bingley had danced with her twice, and she had been distinguished by his sisters. Jane was as much gratified by this as her mother could be, though in a quieter way. Elizabeth felt Jane’s pleasure. Mary had heard herself mentioned to Miss Bingley as the most accomplished girl in the neighbourhood; and Catherine and Lydia had been fortunate enough never to be without partners, which was all that they had yet learnt to care for at a ball. They returned, therefore, in good spirits to Longbourn, the village where they lived, and of which they were the principal inhabitants. They found Mr. Bennet still up. With a book he was regardless of time; and on the present occasion he had a good deal of curiosity as to the event of an evening which had raised such splendid expectations. He had rather hoped that his wife’s views on the stranger would be disappointed; but he soon found out that he had a different story to hear. “Oh, my dear Mr. Bennet,” as she entered the room, “we have had a most delightful evening, a most excellent ball. I wish you had been there. Jane was so admired, nothing could be like it. Everybody said how well she looked; and Mr. Bingley thought her quite beautiful, and danced with her twice! Only think of that, my dear; he actually danced with her twice! and she was the only creature in the room that he asked a second time. First of all, he asked Miss Lucas. I was so vexed to see him stand up with her! But, however, he did not admire her at all; indeed, nobody can, you know; and he seemed quite struck with Jane as she was going down the dance. So he inquired who she was, and got introduced, and asked her for the two next. Then the two third he danced with Miss King, and the two fourth with Maria Lucas, and the two fifth with Jane again, and the two sixth with Lizzy, and the Boulanger—” “If he had had any compassion for me,” cried her husband impatiently, “he would not have danced half so much! For God’s sake, say no more of his partners. Oh that he had sprained his ankle in the first dance!” “Oh! my dear, I am quite delighted with him. He is so excessively handsome! And his sisters are charming women. I never in my life saw anything more elegant than their dresses. I dare say the lace upon Mrs. Hurst’s gown—” Here she was interrupted again. Mr. Bennet protested against any description of finery. She was therefore obliged to seek another branch of the subject, and related, with much bitterness of spirit and some exaggeration, the shocking rudeness of Mr. Darcy. “But I can assure you,” she added, “that Lizzy does not lose much by not suiting his fancy; for he is a most disagreeable, horrid man, not at all worth pleasing. So high and so conceited that there was no enduring him! He walked here, and he walked there, fancying himself so very great! Not handsome enough to dance with! I wish you had been there, my dear, to have given him one of your set-downs. I quite detest the man.”

Answer 1

Summary :

As part of the solution provided Notes , Code and output.

Notes :

The approach followed is as following .

Defined two structures freqNode which is basically a linked list of huffNodes sorted in desc order

huffNode is the structure which holds the data , freq and left & right nodes linkes .

In the readFile() , the input text file is read and frequencies of all alphabets are counted in a integer array whose index is alphabets ( a = 0 , b = 1 etc ).

This above frequency array is passed to constructHuff() which returns the huffman code tree .

Inside the constructHuff()

i) a linked list of freqNodes is constructed from the freq array which is in descending order .

ii) iterating thru the linked list created in freqNodes :

    a) remove first two nodes from the sorted list and create a fresh node with freq = sum of both the nodes and add the first and 2nd nodes as child nodes to this node . please note there are two nodes . one is huffNode which holds the sum of frequencies and links to the huffNodes and the freqNode which holds a pointer to the huffNode and link to next freqNode.

b) Now insert the freqNode created from above(a) new freqNode into the sorted list .

iii) repeat step(i) &(ii) above till only single element remains .

Next for printing the code , implemented a recursive printCode() which takes the head nodes , code and length and modifies the code and len recursively to print the code whenever leaf node is found.

######################## Code ####################

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

struct huffNode
{
   char dat ;
   int freq ;
   struct huffNode *left ;
   struct huffNode *right ;
};
struct freqNode
{
   huffNode* nodePtr ;
   struct freqNode* link;
};

/* This function reads the file and constructs a linked list of frequencies of characters and returns */

freqNode* readFile(string flname, int freq[] )
{
  
   // Initialize array to store the frequencies index with ascii code
   //int freq[26];
  
   // initialize them with 0s
   for(int i=0 ; i < 26 ; i++ )
       freq[i] = 0;
  
   // open the file
   ifstream file (flname);
   string line0;
   int indx ;
   if(file.is_open())
   {
       while( !file.eof() )
       {
           // get each line and iterate thru each character and if its alpha bet count the frequecy .
           getline(file, line0);
           //cout << " Read : " << line0 << "\n";
           if ( line0.size() > 0 )
           {
               for ( int i =0 ; i < line0.size() ; i++ )
                   if ( isalpha( line0.at(i)) )
                   {   indx = line0.at(i) - 'a' ;
                       if ( isupper(line0.at(i)) )
                               indx = line0.at(i) - 'A' ;
                               //indx = 26 + line0.at(i) - 'a' ;
                       freq[indx] += 1;
                   }
           }      
       }

   }
   file.close();
  
}

void deleteHuff(huffNode* head)
{
   if ( head != NULL )
   {
       deleteHuff(head->left);
       deleteHuff(head->right);
       delete head;
   }
}

huffNode* construcHuff( int freq[])
{  
  
   freqNode * headFreqNodes = new freqNode();
   headFreqNodes->nodePtr = new huffNode();
   headFreqNodes->nodePtr->dat = (char) ( 65 ) ;
   headFreqNodes->nodePtr->freq = freq[0];
   freqNode *tmpNode;
   freqNode *prevNode;
   freqNode *nNode;
   for( int i = 1 ; i < 26 ; i++ )
   {
           tmpNode = headFreqNodes ;
           prevNode = NULL;
           bool flag = false ;
           while ( tmpNode != NULL )
           {
               if ( tmpNode->nodePtr->freq > freq[i] )
                   break;
               prevNode = tmpNode ;
               tmpNode = tmpNode->link;
           }
           nNode = new freqNode();
           nNode->nodePtr = new huffNode();
          
           nNode->nodePtr->dat = (char) (65 + i);
           nNode->nodePtr->freq = freq[i];
           nNode->nodePtr->right = NULL;
           nNode->nodePtr->left = NULL;
           if ( prevNode != NULL )
           {
               prevNode->link = nNode ;
               nNode->link = tmpNode ;
           } else {
               nNode->link = headFreqNodes;
               headFreqNodes = nNode;
           }
   }
  
  
   huffNode* huffcode = NULL;
   freqNode* huffNodeList = NULL;
   freqNode* tmp1;
   freqNode* tmp2;
   while ( headFreqNodes->link != NULL )
   {
           tmp1 = headFreqNodes ;
           if ( headFreqNodes->link == NULL )
               break;
           tmp2 = headFreqNodes->link;
          
           headFreqNodes = tmp2->link ;
           huffNode *tHuffNode = new huffNode() ;
           tHuffNode->freq = tmp1->nodePtr->freq + tmp2->nodePtr->freq;
           tHuffNode->dat = '.';
           if ( tmp1->nodePtr->freq < tmp2->nodePtr->freq )
           {
               tHuffNode->left = tmp1->nodePtr ;
               tHuffNode->right = tmp2->nodePtr;
           }
           else
           {
               tHuffNode->left = tmp2->nodePtr ;
               tHuffNode->right = tmp1->nodePtr;
           }
           delete tmp1;
           delete tmp2 ;
          
          
          

           tmpNode = huffNodeList ;
           prevNode = NULL;
          
           while ( tmpNode != NULL )
           {
               if ( tmpNode->nodePtr->freq > tHuffNode->freq )
                   break;
               prevNode = tmpNode ;
               tmpNode = tmpNode->link;
           }
           nNode = new freqNode();
           nNode->nodePtr = tHuffNode;
          
           if ( prevNode != NULL )
           {
               prevNode->link = nNode ;
               nNode->link = tmpNode ;
           } else {
               nNode->link = headFreqNodes;
               headFreqNodes = nNode;
           }
  
  
          
          
  
   }
   huffNode *tmp = headFreqNodes->nodePtr;
   delete headFreqNodes;
   return tmp;
}

// This method just prints the frequencies of each nodes
void preOrder(huffNode* head )
{
  
   if ( head == NULL )
       return ;
   else
   {
       if ( head->dat == '.' )
       {
           cout << " left " << head->left->dat << " ( " << head->left->freq << ") " <<" right " << head->right->dat << " ( " << head->right->freq << ")\n";
       }
       preOrder(head->left);
       preOrder(head->right);
   }

  
}
// This method prints the code for each letter
void printCode(huffNode* head , int code[] , int& len )
{
   if ( head != NULL )
   {
       //cout << " " << head->dat ;
       if (( head->left == NULL ) & ( head->right == NULL ) )
       {
           cout << " Char -> " << head->dat << " -> " ;
           for( int i=0 ; i < len ; i++ )
               cout << code[i] ;
           cout <<"\n";
       } else {
           //int x = len ;
           code[len] = 0 ;
           len++;
           printCode( head->left, code , len );
           len--;
           //len = x;
           code[len] = 1 ;
           len++ ;
           printCode( head->right, code , len);
           len--;
           //len = x-2;
       }
   }
  
}

int main()
{
   int frqs[26] ;
   int code[50];
   int len = 0 ;
   readFile("pj.txt",frqs);
  
   //for( int i = 0 ; i < 26 ; i++ )
   //   cout << " " << (char) ( 65 + i ) << " " << frqs[i] << " , " ;
  
   cout << " - -- \n";
   huffNode* rt = construcHuff(frqs);
  
   preOrder(rt);
   printCode(rt,code,len);
   deleteHuff(rt);
}

######################## Output #####################