huffman algorithm needs help in storing char code

Question

I have written program to obtain the code for each char as shown in the program output.

enter some text: nslfaslfjasfj text = "nslfaslfjasfj"

a:2

f:3

j:2

l:2

n:1

s:3

Huffman Algorithm Below is "CHAR CODE":

n code:111

j code:110

f code:10

s code:01

l code:001

a code:000

My next step should be storing the above in structure and comparing it my original text = "nslfaslfjasfj" to encode as "11101.....so on".

I am finding a problem in storing "CHAR CODE" in structure. Should it be stored as string like string s="111" and then stored in the strucuture?.. Thanks in advance.

Answer 1

Considering you're trying to compress something, using strings would be a horrible idea. You'll want to store the char codes as raw binary.

Answer 2

Usually the point of Huffman encoding is to decrease the length of the message, i.e. compress it. This means you want to be writing bits out, not the characters '0' and '1'. Therefore it makes sense to store your character codes also as bits, and use bit operations to transfer them to the stream. Storing a pair (character code, code length) for each element is sufficient to construct the encoding.

Having said that, you can do it with strings as you suggest. It's not wrong, and it might make it a little easier to debug, but it will perform worse.

Answer 3

You're going to need to make some kind of "BitWriter". We covered the topic of bitwise I/O in Java for huffman coding in a data structures class at my university, the lecture slides are freely available here. Obviously Java != C, but the concept is the same.