Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

arcticf0x

  • 2 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.

  • This Question is Closed
  1. agdgdgdgwngo
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. arcticf0x
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. agdgdgdgwngo
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. arcticf0x
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this is my first project :D

  6. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  15. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    they may not allow access from the US ;)

  19. arcticf0x
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  20. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  21. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    yeah, probably a good idea

  22. arcticf0x
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. opiesche
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    OK, I'm off to bed - night!

  24. arcticf0x
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Good Night! And Thanks a lot!

  25. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.