## arcticf0x 3 years ago How do we do huffman coding and decoding in C++? It must implement a binary tree, binary search, scanning of Input stream, generation of Code.

1. agdgdgdgwngo

Good luck with that :-D I can't even implement a binary search correctly :(

2. arcticf0x

Oh :( i guess i will have to find some advanced books to do all that.

3. agdgdgdgwngo

There's probably no need for an advanced book; try google :-D

4. arcticf0x

Its too complicated, the part i'm not getting is converting those simple data structure algorithms to real time code. I have some idea overall on how this project will finally work, but need to join the pieces together through a bit of copy pasting and some research :P

5. arcticf0x

this is my first project :D

6. opiesche

Ah, good ol' Huffman. Once you've got the binary tree internalized, it becomes more clear how to do the rest of it. As for the binary tree, it's all about the data structure. A binary tree by definition means every non-leaf node has two children: N / \ N N / \ N N So that means your data structure for each node needs to contain the node data itself, and then pointers to two child nodes. You can use NULL child pointers to identify a leaf node. The tree itself then actually only needs to contain the root node, from there you can traverse with a recursive function to all other nodes. The trick about this is that it's O(logN) to find a particular piece of data in the tree if you structure it properly. Imagine you've got pointers to objects associated with an integer value between 1-10. The node data in this case should be a range of numbers, and in leaf nodes, a pointer to an object associated with that number. The root node R could contain the range 1-10, and children halve the range of the parent (with a special condition where the number isn't divisible by 2): 0-10 / \ 0-5 6-10 ... / \ 6-8 9-10 / \ / \ 6 7-8 9 10 / \ 7 8 I've only shown one branch from the root node here, but you get the idea. Now imagine you're searching for the pointer to the object associated with the value 7. You start at the root node. 0-10 contains 7, so check both children. The range of the left child 0-5 doesn't contain 7, so stop there. The right child is 6-10, which contains 7, so again check both children. Continue until you've reached the leaf node with the value 7, and you've found your object - in O(logN) time. Searching through an array would have O(N) complexity.

7. arcticf0x

Yeah, as i was telling you, i have been taught only these concepts in the last semester, implementing all that in real time has driven me nuts. I understood Hoffman from this video http://www.youtube.com/watch?v=0PahtaFK640 But i guess first i need to code sorting and searching and implementation of binary tree properly in order to make that project.

8. opiesche

To implement this, you'll need a node data structure that contains your data and simply pointers to two child nodes (and in the example case, an integer range and a pointer to the object): class BinaryTreeNode { .... private: Node *m_child1, *m_child2; int m_min, m_max; MyObject *m_pData; }; To traverse, you'll need recursion. You can implement the traversal function into the node class itself. That would look something like this: MyObject * BinaryTreeNode::Traverse(int value) { MyObject *pObj = 0; if(m_min<=value && value<=m_max) { // we have reached a leaf node if both children are 0, so check // if we've found the value we're looking for if(m_pChild1==0 && m_pChild2==0 && m_min==m_max && value==m_min) { pObj = m_pData; } else { // otherwise, traverse down the left side of the tree, and if // we don't find the object there, go down the right side pObj = m_pChild1->Traverse(value); if(!pObj) { pObj = m_pChild1->Traverse(value); } } } return pObj; } Now, this will probably not just work or even compile, but hopefully it helps to illustrate the idea.

9. opiesche

You traverse down the tree until you've found the object, and if you've found it, it is passed back up the call chain by returning it, and the initial Traverse() call will return the found object. If it's not found, a null pointer will be passed back up by the successive return statements, so your initial call to Traverse() will return 0.

10. arcticf0x

No matter i will need the whole day to digest that code, but i still understood the working of the tree and how you used the search, let me work the whole code and successfully run a traverse on the binary tree and then tackle the Huffman coding. Btw, the book i was using before for c++ was very theory ish so i have switched to Problem Solving with C++, WALTER SAVITCH.

11. arcticf0x

The problem also is, some of my basic concepts about pointers arent very clear, i still need to get a feel for them.

12. opiesche

I haven't read that one. I've got Numerical Recipes In C++, and can highly recommend it. Yeah, you'll have to get pointers down ;) Technically, they're memory addresses. If you allocate an object with new, malloc will be called to allocate a block of memory for that object. The result of that is a memory address, at which the object (the block of memory allocated for it) resides. A pointer is simply a representation of that memory address. By having a pointer to an object (a pointer of type Node, or Node *ptr, for example), you can use the -> operator to access that object. Conceptually, it's like an arrow that points to another object. Follow the arrow with -> and you can access the object it points to ;)

13. arcticf0x

Yeah i have heard that expression "The sign to the restroom is a pointer not the toilet itself" :D And downloading that book right away!

14. arcticf0x

btw isnt it around 3am at yours O.o?

15. opiesche

Yeah, it is. I'm debugging an oriented box intersection routine and can't let go until it works. What can I say, I'm a nerd :P

16. opiesche

It's a bit cumbersome code - using the Separating Axis Theorem to find out if two oriented boxes are intersecting or not ;) I'm getting a 404 for that link. What is it?

17. arcticf0x

Oh ok, Its an e-book library, but that strange, its working for me.

18. opiesche

they may not allow access from the US ;)

19. arcticf0x

shall i delete its link? people who own this site might get into trouble lol

20. opiesche

that's quite a collection for most books these days i try to get them on iPad to make them accessible everywhere ;)

21. opiesche

yeah, probably a good idea

22. arcticf0x

Yeah, but pdf to epub is sometimes messy for me, so i just read them on the laptop.

23. opiesche

OK, I'm off to bed - night!

24. arcticf0x

Good Night! And Thanks a lot!