We will ignore consecutive 1 because we know consecutive 1 are just fillers (valid codes are 1 followed by zeroes, not 1 followed by 1).
#Betterzip huffman code code#
Questions?ĮDIT : Oh yes! Almost forgot : the last Huffman code won't probably fill the last byte, so fill it with 1 bits with no zeroes. I'm not sure if I explained everything well. The compression level depends on the character frequencies. Remember, this is a poor implementation of Huffman, but it works. Store the char in the decompressed file.Find the code in the Huffman table (at the beginning of the file).Read zeroes until you reach another 1 or the end.It's easy to decode uniform Huffman codes because bits 1 are the delimiters, they mark the beginning of each Huffman code and the character they represent. Let's see how the word "ARE" was compressed : ARE = 100001000100 The rest is ancient history: convert the ones and zeroes in bits inside bytes and store the bytes in the resulting (and not too much compressed) file.Įxtremely important : save the Huffman codes and the characters they represent at the beginning of the file as strings. Don't get nervous, we are not using trees, it's just to illustrate our point. Notice the previous tree is just the implementation of an array, that's why we can use arrays to generate Huffman codes. Next image shows the equivalent code if we would be using a tree: Step 2 : assign Huffman codes for each character in a uniform way : every character gets a bit 1, and as many zeroes as its position, the first character gets the code 10, the second, 100, the third 1000, and so on. Step 1 : count all characters in the file you want to compress, put the characters and their counters in arrays and sort them in DESCENDING order (the most frequent char the first, the least frequent the last). I know it works because I used it for a homework in good old Pascal (not as old as Thomas Kilian), it's very simple:
Ok, dear H.N., there is a poor implementation of Huffman algorithm with arrays, not trees at all.
0 kommentar(er)
