huffman tree algorithm
-
Hey guys-girls,I have been looking to find a good huffman tree example but i cant seem to find a code example of one that is in a language i know (C#, i can kinda desipher C/C++, they are all in java that i have found). I have no problem understanding the logic of the huffman tree algorithm but my problem lies in visualizing how to code it into C#. i want to write it in C# to see if i can do it. does anyone know of a good example or have any of you coded on before in a high level object language. I can kinda do it...i just dont know how to build the actuall tree portion of the Algorithm, any examples on that would help too. Thanks alot. Jesse M. The Code Project Is Your Friend...
-
Hey guys-girls,I have been looking to find a good huffman tree example but i cant seem to find a code example of one that is in a language i know (C#, i can kinda desipher C/C++, they are all in java that i have found). I have no problem understanding the logic of the huffman tree algorithm but my problem lies in visualizing how to code it into C#. i want to write it in C# to see if i can do it. does anyone know of a good example or have any of you coded on before in a high level object language. I can kinda do it...i just dont know how to build the actuall tree portion of the Algorithm, any examples on that would help too. Thanks alot. Jesse M. The Code Project Is Your Friend...
-
Hey guys-girls,I have been looking to find a good huffman tree example but i cant seem to find a code example of one that is in a language i know (C#, i can kinda desipher C/C++, they are all in java that i have found). I have no problem understanding the logic of the huffman tree algorithm but my problem lies in visualizing how to code it into C#. i want to write it in C# to see if i can do it. does anyone know of a good example or have any of you coded on before in a high level object language. I can kinda do it...i just dont know how to build the actuall tree portion of the Algorithm, any examples on that would help too. Thanks alot. Jesse M. The Code Project Is Your Friend...
I'm kind of puzzled: java and C# are very similar. If you've found a java example of creating a huffman tree than it should be easy to convert it into C#. To build a huffman tree you'll need two basic classes: the tree and a priority queue. (You need the latter to easily get the nodes or partial trees with the smallest weights every time.) A huffman tree consists of node objects. Each node object will have a left child node and a right child node, and will have a weight value (the weight being the count of characters in the node and its children). You'll also store the byte value in the node. So, first do it without regard to performance. Create an array of nodes, one for each possible byte in the input stream (i.e. 256 of them). Read through the input stream, for each byte you update the weight in the relevant node object. Push all the nodes with non-zero weights in the priority queue. Pop the top two off. Create a new parent node with weight equal to the sum of the two nodes' weights. The children of this parent are the two nodes popped off. Push the parent node into the priority queue. Perform the previous two steps until there is only one node in the queue. This is the huffman tree. Cheers, Julian Program Manager, C# This posting is provided "AS IS" with no warranties, and confers no rights.
-
I'm kind of puzzled: java and C# are very similar. If you've found a java example of creating a huffman tree than it should be easy to convert it into C#. To build a huffman tree you'll need two basic classes: the tree and a priority queue. (You need the latter to easily get the nodes or partial trees with the smallest weights every time.) A huffman tree consists of node objects. Each node object will have a left child node and a right child node, and will have a weight value (the weight being the count of characters in the node and its children). You'll also store the byte value in the node. So, first do it without regard to performance. Create an array of nodes, one for each possible byte in the input stream (i.e. 256 of them). Read through the input stream, for each byte you update the weight in the relevant node object. Push all the nodes with non-zero weights in the priority queue. Pop the top two off. Create a new parent node with weight equal to the sum of the two nodes' weights. The children of this parent are the two nodes popped off. Push the parent node into the priority queue. Perform the previous two steps until there is only one node in the queue. This is the huffman tree. Cheers, Julian Program Manager, C# This posting is provided "AS IS" with no warranties, and confers no rights.
-
Hey guys-girls,I have been looking to find a good huffman tree example but i cant seem to find a code example of one that is in a language i know (C#, i can kinda desipher C/C++, they are all in java that i have found). I have no problem understanding the logic of the huffman tree algorithm but my problem lies in visualizing how to code it into C#. i want to write it in C# to see if i can do it. does anyone know of a good example or have any of you coded on before in a high level object language. I can kinda do it...i just dont know how to build the actuall tree portion of the Algorithm, any examples on that would help too. Thanks alot. Jesse M. The Code Project Is Your Friend...
jtmtv18 wrote: i just dont know how to build the actuall tree portion of the Algorithm I would develope the tree as a Huffman Tree class all by itself. It is basically a Binary tree:
public class HuffmanTree { private HuffmanNode node = null; private HuffmanTree rightChild = null; private HuffmanTree leftChild = null; }with the Node beingpublic class HuffmanNode { private char c; //The character private int f; //The frequency }You can implement the joining of two trees (when you are building the Huffman tree based on the charactrs' frequencies) in the HuffmanTree class, or you can implement it outside the HuffmanTree class. In this second case, the HuffmanTree becomes a simple binary tree containing HuffmanNodes (you could generalize this and make your own BinaryTree class containing Objects instead of Huffmannodes). HTH, FOR PS: If I was at home, I'd pass along my C++ HuffmanTree code, but -alas- I am working :-) -
i think i can visualize writing the code for it.but how do i setup the decompressor ? Jesse Murcray. The Code Project Is Your Friend...
It depends on where the decompressor gets its input from. For instance, if your Huffman Tree compressed a clear text file into a compressed file, then the decompressor would get the compressed file to generate the clear file. Right? If so, remember that the compressed file should include in its header a serialized version of the HuffmanTree itself. Thus, the decompressor would first read this "symbol table" in the compressed file, and build the corresponding HuffmanTree from it (i.e. de-serializing the HuffmanTree). Once that is done, the decompressor should just read the rest of the compressed file, get the corresponding character from the HuffmanTree, and place this character in the output file. HTH, FOR
-
jtmtv18 wrote: i just dont know how to build the actuall tree portion of the Algorithm I would develope the tree as a Huffman Tree class all by itself. It is basically a Binary tree:
public class HuffmanTree { private HuffmanNode node = null; private HuffmanTree rightChild = null; private HuffmanTree leftChild = null; }with the Node beingpublic class HuffmanNode { private char c; //The character private int f; //The frequency }You can implement the joining of two trees (when you are building the Huffman tree based on the charactrs' frequencies) in the HuffmanTree class, or you can implement it outside the HuffmanTree class. In this second case, the HuffmanTree becomes a simple binary tree containing HuffmanNodes (you could generalize this and make your own BinaryTree class containing Objects instead of Huffmannodes). HTH, FOR PS: If I was at home, I'd pass along my C++ HuffmanTree code, but -alas- I am working :-)Thanks alot for your time. ill have to work on it later. I stayed up all night last night and got the tree down to a single node i.e they are all connected. One question though, since each new "tree" contains the weight of the previous 2 children combined, should the weight at the top of my tree be equal to the length of the string? Jesse M The Code Project Is Your Friend...
-
i think i can visualize writing the code for it.but how do i setup the decompressor ? Jesse Murcray. The Code Project Is Your Friend...
So it's more than just building the tree, then? Building the tree is the standard well-understood algorithm. Using the tree is where things diverge and get really tough. To compress using a huffman tree, you have to remember to pass an encoding of the tree to the decompressor, followed of course by the compressed data. There are various ways to encode the tree: pass along 256 int values, each containing the calculated weights. The decomnpressor can then use these in exactly the same way as you used to build the tree in the first place. Unfortunately 256 ints would be 1K, which is a lot to add to a compressed file. You can analyze the weights and compress out zero values. For example, compressing a text file would result in a lot of byte values (characters, if you like) being unused and hence having a zero weight. You could devise an RLE (run length encoding) scheme that replaces runs of zero bytes in the weights table. You could use a variable length encoding. Say you analyze the weights as you write them out. You output 2 bits before every wieght. If the bits are 00, the next weight will be 8 bits long. If the bits are 01, the next weight will be 16 bits long. If 10, the next weight will be 24 bits. If 11, a full 32 bits. And so on. You could of course try out all these possibilities and pass along the smallest result (along with an indicator to tell the decompressor which variety was used). Compressing and decompressing the data is the standard algorithm again. You would need to write a class that was a bit stream (to get the really nasty stuff out of the way), otherwise you're going to be writing a lot of bit manipulation code in the middle of your compression and decompression code. Cheers, Julian Program Manager, C# This posting is provided "AS IS" with no warranties, and confers no rights.
-
Thanks alot for your time. ill have to work on it later. I stayed up all night last night and got the tree down to a single node i.e they are all connected. One question though, since each new "tree" contains the weight of the previous 2 children combined, should the weight at the top of my tree be equal to the length of the string? Jesse M The Code Project Is Your Friend...
That's right. The weight (or frequency) for leaf nodes is merely the count of that particular character at the leaf in the source file; the weight for internal nodes, which are parents, is the count of all the characters in the children nodes. Cheers, Julian Program Manager, C# This posting is provided "AS IS" with no warranties, and confers no rights.
-
Thanks alot for your time. ill have to work on it later. I stayed up all night last night and got the tree down to a single node i.e they are all connected. One question though, since each new "tree" contains the weight of the previous 2 children combined, should the weight at the top of my tree be equal to the length of the string? Jesse M The Code Project Is Your Friend...
jtmtv18 wrote: should the weight at the top of my tree be equal to the length of the string? After the whole tree is built, yes, the weight of the root will be equal to the length of the text to be compressed. HTH, FOR