Implementing Huffman Tree

Question

I have a program that produces a huffman tree based on ascii character frequency read in a text input file. The huffman codes are stored in a string array of 256 elements, empty string if character is not read.

I am now trying to implement the huffman tree by writing a function that takes my huffman codes that are stored in a string array and outputting the encoding of input file into an output file.

I soon realized that my current approach defeats the meaning of the assignment. I have tried simply copying the string of codes to output file making my encoded output file bigger than the input file.

I am hoping to get help in changing my current function so that it can output the bits into output file making the output file smaller than input file. I am stuck because I am only reading and writing bytes currently?

My current function(fileName being input file parameter, fileName2 being output file parameter):

void encodeOutput(const string & fileName, const string & fileName2, string code[256]) {
    ifstream ifile;//to read file
    ifile.open(fileName, ios::binary);
    if (!ifile)//to check if file is open or not
    {
        die("Can't read again"); // function that exits program if can't open
    }
    ofstream ofile; 
    ofile.open(fileName2, ios::binary); 
    if (!ofile) {
        die("Can't open encoding output file"); 
    }
    int read;
    read = ifile.get();//read one char from file and store it in int
    while (read != -1) {//run this loop until reached to end of file(-1)
        ofile << code[read]; //put huffman code of character into output file
        read = ifile.get();//read next character
    }
    ifile.close();
    ofile.close();
}

GBrandt GBrandt · Accepted Answer · 2019-03-07T19:37:42

You can't just use ofile << code[read]; if what you need is writing bits, the smallest unit ofstream understands is a byte.

To overcome that, you can write your bits to some sort of "bit buffer" (a char will do) and write that out once it has 8 bits. I don't know exctly what you code strings look like, but this should do:

char buffer = 0, bit_count = 0;
while (read != -1) {
  for (int b = 0; b < code[read].size(); b++) {
    buffer << 1;
    buffer |= code[read][b] != 0;
    bit_count++;
    if (bit_count == 8) {
      ofile << buffer;
      buffer = 0;
      bit_count = 0;
    }
  }
  read = ifile.get();
}

if (bit_count != 0)
  ofile << (buffer << (8 - bit_count));

Implementing Huffman Tree

1 Answers