C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  encoding tree          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message tonokio Guest Posted: Tue Apr 25, 2006 8:06 pm    Post subject: encoding tree I wanted to write a simple huff tree table that would take a basic list of frequenccy table and return the code for each character. Say input would be: //"print this out." is what the this table represents 10 1 32 2 46 1 104 1 105 2 110 1 111 1 112 1 114 1 115 1 116 3 117 1 The program will then convert to the code for each character and it would look like the follwing: 117 000 32 001 105 010 10 0110 46 0111 104 1000 110 1001 111 1010 112 1011 114 1100 115 1101 116 111 If anyone has any ideas on how to start or how to make it read the list from stdin and start this process that would be great. Back to top osmium Guest Posted: Tue Apr 25, 2006 8:06 pm    Post subject: Re: encoding tree "tonokio" writes: Quote: I wanted to write a simple huff tree table that would take a basic list of frequenccy table and return the code for each character. Say input would be: //"print this out." is what the this table represents 10 1 32 2 46 1 104 1 105 2 110 1 111 1 112 1 114 1 115 1 116 3 117 1 The program will then convert to the code for each character and it would look like the follwing: 117 000 32 001 105 010 10 0110 46 0111 104 1000 110 1001 111 1010 112 1011 114 1100 115 1101 116 111 If anyone has any ideas on how to start or how to make it read the list from stdin and start this process that would be great. I will take a wild guess that huff is street talk for Huffman. I had no idea he had entered the popular culture; how very trendy. If my guess is right, there are two parts to the problem. o Construct a table containing the frequency of the various characters in the alphabet. o Using that table, contract a table of suitable codes. There are several tutorials on the web WRT bullet 2 that are probably better than anything someone is going to write in a few minutes and post here. If your problem is with bullet 1, say so. Back to top Victor Bazarov Guest Posted: Tue Apr 25, 2006 8:06 pm    Post subject: Re: encoding tree tonokio wrote: Quote: I wanted to write a simple huff tree table that would take a basic list of frequenccy table and return the code for each character. Say input would be: //"print this out." is what the this table represents 10 1 32 2 46 1 104 1 105 2 110 1 111 1 112 1 114 1 115 1 116 3 117 1 The program will then convert to the code for each character and it would look like the follwing: 117 000 32 001 105 010 10 0110 46 0111 104 1000 110 1001 111 1010 112 1011 114 1100 115 1101 116 111 If anyone has any ideas on how to start or how to make it read the list from stdin and start this process that would be great. Start like this: #include <iostream> int main() { while (!std::cin.eof()) { // read what you need, using operator >> or 'getline'. // act upon what you just read } } V -- Please remove capital 'A's when replying by e-mail I do not respond to top-posted replies, please don't ask Back to top tonokio Guest Posted: Tue Apr 25, 2006 9:06 pm    Post subject: Re: encoding tree I did some reading online and I realize there is more than one way to implement this huffman tree and even more suprising it doesn't require an advanced data structure, I think it was purposed somewhere that even that is not necessary. I don' think we're suppose to use an ADT, just something simple to encode to the huffman codes. I think a BST would be easy to use, but I want to see if there is something that could be simpler and more straight forward, least in the coding sense. I'm only given input files that are already in a frequency list format as the beginning post stated. Back to top tonokio Guest Posted: Tue Apr 25, 2006 9:06 pm    Post subject: Re: encoding tree Yes, I have a problem with bullet 1 which is to Construct a table containing the frequency of the various characters in the alphabet. osmium wrote: Quote: "tonokio" writes: I wanted to write a simple huff tree table that would take a basic list of frequenccy table and return the code for each character. Say input would be: //"print this out." is what the this table represents 10 1 32 2 46 1 104 1 105 2 110 1 111 1 112 1 114 1 115 1 116 3 117 1 The program will then convert to the code for each character and it would look like the follwing: 117 000 32 001 105 010 10 0110 46 0111 104 1000 110 1001 111 1010 112 1011 114 1100 115 1101 116 111 If anyone has any ideas on how to start or how to make it read the list from stdin and start this process that would be great. I will take a wild guess that huff is street talk for Huffman. I had no idea he had entered the popular culture; how very trendy. If my guess is right, there are two parts to the problem. o Construct a table containing the frequency of the various characters in the alphabet. o Using that table, contract a table of suitable codes. There are several tutorials on the web WRT bullet 2 that are probably better than anything someone is going to write in a few minutes and post here. If your problem is with bullet 1, say so. Back to top red floyd Guest Posted: Tue Apr 25, 2006 9:06 pm    Post subject: Re: encoding tree Victor Bazarov wrote: Quote: tonokio wrote: I wanted to write a simple huff tree table that would take a basic list of frequenccy table and return the code for each character. Say input would be: //"print this out." is what the this table represents 10 1 32 2 46 1 104 1 105 2 110 1 111 1 112 1 114 1 115 1 116 3 117 1 The program will then convert to the code for each character and it would look like the follwing: 117 000 32 001 105 010 10 0110 46 0111 104 1000 110 1001 111 1010 112 1011 114 1100 115 1101 116 111 If anyone has any ideas on how to start or how to make it read the list from stdin and start this process that would be great. Start like this: #include <iostream int main() { while (!std::cin.eof()) { // read what you need, using operator >> or 'getline'. // act upon what you just read } } Victor, I'm surprised at you! You know that that the "while not eof" idiom gives an extra spurious read. #include <iostream> int main() { int value; int frequency; while (std::cin >> value >> frequency) { // do something with your value and frequency } } Back to top tonokio Guest Posted: Wed Apr 26, 2006 6:06 am    Post subject: Re: encoding tree My program already generates the frequency list and I was wondering how would we read int he first and second column and store it into an array? #include <iostream> int main() { int value; //perhaps make this into an array int frequency; //perhaaps make this into an array while (std::cin >> value >> frequency) { // do something with your value and frequency } } the file that I will redirect in to the huffman program will look like: //char //freq 102 4 117 29 .. .. .. I wanted to know how to parse it in stdin and store them into an array before I generate a min-heap and insert the values to make the huffman tree. tonokio wrote: Quote: I did some reading online and I realize there is more than one way to implement this huffman tree and even more suprising it doesn't require an advanced data structure, I think it was purposed somewhere that even that is not necessary. I don' think we're suppose to use an ADT, just something simple to encode to the huffman codes. I think a BST would be easy to use, but I want to see if there is something that could be simpler and more straight forward, least in the coding sense. I'm only given input files that are already in a frequency list format as the beginning post stated. Back to top tonokio Guest Posted: Mon May 01, 2006 6:06 pm    Post subject: Re: encoding tree I got some of the program working and when I generate the huff code I still get some descrepency and I was wondering if anyone could see if there is anything wrong with my logic. http://cpp.sourceforge.net/?show=15272 We were given a test app to use our code and the enc/dec part of the program hasn't been written but I tested my program so far with the code that I generate and an input and the output does not match when it is enc/dec with my codes. Thank you for your time. tonokio wrote: Quote: My program already generates the frequency list and I was wondering how would we read int he first and second column and store it into an array? #include <iostream int main() { int value; //perhaps make this into an array int frequency; //perhaaps make this into an array while (std::cin >> value >> frequency) { // do something with your value and frequency } } the file that I will redirect in to the huffman program will look like: //char //freq 102 4 117 29 . . . I wanted to know how to parse it in stdin and store them into an array before I generate a min-heap and insert the values to make the huffman tree. tonokio wrote: I did some reading online and I realize there is more than one way to implement this huffman tree and even more suprising it doesn't require an advanced data structure, I think it was purposed somewhere that even that is not necessary. I don' think we're suppose to use an ADT, just something simple to encode to the huffman codes. I think a BST would be easy to use, but I want to see if there is something that could be simpler and more straight forward, least in the coding sense. I'm only given input files that are already in a frequency list format as the beginning post stated. Back to top        C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1 Powered by phpBB © 2001, 2006 phpBB Group