Huffman

This is a discussion on Huffman within the C Programming forums, part of the General Programming Boards category; please excuse me for not posting the code in this thread and providing a link, but it is easier to ...

  1. #1
    Registered User
    Join Date
    Dec 2012
    Posts
    3

    Huffman

    please excuse me for not posting the code in this thread and providing a link, but it is easier to just read the files from the zip file rather than put them all up individually.


    My code is in C.


    Im working with Huffman encoding and my task at hand is to create a file that contains the header information to construct a hufman tree. I believe i know how to create the header, but im having trouble creating the tree.
    the link contains my files that i am working with. my problem is with the utility.c file. the creating of the tree is in this file and is at the bottom of the file.


    tree.zip


    the file im testing is called "testcase" and is entered in the call of the program along with the output file name (though at the moment it does nothing).the tree i am trying to create should look like this...
    imgur: the simple image sharer


    there is a post order walk that is completed later in the program that should have an output like so...
    Left
    Left
    Left
    Back
    Right
    Back
    Leaf: g
    Back
    Right
    Left
    Back
    Right
    Back
    Leaf: o
    Back
    Back
    Right
    Left
    Left
    Left
    Back
    Right
    Back
    Leaf: s
    Back
    Right
    Left
    Back
    Right
    Back
    Leaf:
    Back
    Back
    Right
    Left
    Left
    Left
    Back
    Right
    Back
    Leaf: e
    Back
    Right
    Left
    Back
    Right
    Back
    Leaf: h
    Back
    Back
    Right
    Left
    Left
    Back
    Right
    Back
    Leaf: p
    Back
    Right
    Left
    Back
    Right
    Back
    Leaf: r
    Back
    Back
    Back
    Back




    i know this is a lot to ask, but im out of ideas for how to fix this. ive spent hours looking at this and am out of ideas for how to fix it. the issue is with creating the tree and located in the utility.c file. if you could help in any way i would greatly appreciate it.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Your indentation is quite inconsistent. Consider adopting an indentation style and sticking with it, it will make your code more readable so you'll be able to spot bugs faster, and other people will be more willing to read it....

    Anyway. Code like this
    Code:
    int compressed_array[length][2];
    
    for (i=0;i<=length;i++){
        compressed_array[i][0] = org_array[i][0];
        compressed_array[i][1] = org_array[i][1];
        }
    causes a buffer overrun since the valid indices of compressed_array[i] are 0 through length-1. You should use the for(i=0;i<length;i++) idiom. It's even worse when, lower down, you have an off-by-two error!
    Code:
       for(i = 0; i <=length+1; i++){
    That's going two elements too far.

    Another minor point: when you open a file the file pointer will be at the beginning of the file. There's no need to fseek(fp, 0, SEEK_SET) unless you've read some data from the file.

    If I fix these buffer overruns through the hacky method of making enough space in the arrays rather than fixing your loops,
    Code:
    $ diff utility.c.orig utility.c
    59c59
    < int compressed_array[length][2];
    ---
    > int compressed_array[length+2][2];
    83c83
    <    LEAF *array[length] ;
    ---
    >    LEAF *array[length+2] ;
    then when I run the program I no longer get a segmentation fault but rather an infinite loop from the PostOrderWalk function. In other words, you've probably managed to construct a cycle in your tree. I didn't look into it any more closely than that but maybe this will get you started.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Jun 2010
    Location
    In a house
    Posts
    15
    I don't think you understand Huffman encoding fully and you should use a linked list for the tree.

    I suggest use an array of linked list pointers when constructing the tree.

    -Before you construct the tree, the key frequency must be in an ascending order. [you also need a sorting subroutine]

    so the tree construction routine is like this:


    while (there is something in the character array)
    1] make a node for each of the first two elements and take them out from the array. [think about what if there is only 1 element]
    2] make a new node: the key could be anything you want and the value is the combined frequency of the elements. left child of the new node is element 1 and right child is element 2.
    3] put the new node back to the array and sort the whole thing according to the frequency [least frequent key start at the beginning].

  4. #4
    Registered User
    Join Date
    Dec 2012
    Posts
    3
    Quote Originally Posted by dwks View Post
    then when I run the program I no longer get a segmentation fault but rather an infinite loop from the PostOrderWalk function. In other words, you've probably managed to construct a cycle in your tree. I didn't look into it any more closely than that but maybe this will get you started.
    Thank you, while i didnt fix my indention problems, i did go in and straighten out the length and loop problems. unfortunatly, after working on it for a few more hours, i still cant seem to figure out the tree construction. if you wouldnt mind looking at the updated utility.c here https://gist.github.com/4410592 it would be a life saver, i had a breakdown earlier today and am starting to stress over the issue. thank you

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Huffman coding
    By etoh in forum C Programming
    Replies: 1
    Last Post: 11-13-2011, 09:12 AM
  2. huffman coding
    By ratikag in forum C++ Programming
    Replies: 12
    Last Post: 01-20-2010, 10:22 AM
  3. huffman code
    By edesign in forum C Programming
    Replies: 4
    Last Post: 03-23-2008, 12:09 PM
  4. The Huffman Algorithm
    By Desolation in forum C++ Programming
    Replies: 3
    Last Post: 05-26-2006, 12:30 PM
  5. Huffman compression
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-01-2001, 07:30 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21