Thread: Huffman coding

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    15

    Code giving inconsistant output - Huffman coding

    I am writing a program for a class that calls for Huffman coding. The coding itself is not the issue. The problem is that I can't figure out why a chunk of my code works for the first 90% of the iterations, but fails at the very end, causing most of the codes to be correct, but some to be wrong. This is not the best way to do this I am sure (I don't actually build a tree), but it should work.

    When symbols are combined, I keep track of the originals in an array. All symbols in the array are affected when the combined symbol is affected. I.e: when symbol "ab" has a 1 added to it, so do "a" and "b".

    The included code is the part where these indicies are updated when symbols are combined. This is what is failing near the end of execution.

    Code:
        // This code is at the end of the huffman() function
        // -1 is a dummy value for an unused array element
        //  this codes executes 12 times with the sample input but that shouldn't matter
        
        // DUMMY = 999999
        // CODES = 256
        // arrays are declared with CODES (256) elements    
    
        // add in the new dependencies
        for(i=0; i<CODES && lower.indicies[i]!=-1; i++){
            if(_codes[_order[i]].total != DUMMY)
                new.indicies[i] = lower.indicies[i];
        }
    
        // add in the new dependencies
        for(j=0; j<CODES && low.indicies[j]!=-1; j++){
            if(_codes[_order[j]].total != DUMMY)
                new.indicies[i+j] = low.indicies[j];
        }
    
        // replace the old entries
        _codes[_order[0]].total = DUMMY;
        _codes[_order[1]] = new;
    
        // reset all dependencies for used symbols
        for(i=0; i<CODES; i++){
            _codes[_order[0]].indicies[i] = -1;
        }
    The whole program is available here

    Thanks in advance
    Last edited by fatinez; 10-31-2003 at 03:46 AM.

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Code:
        for(i=0; i<256; i++){
            for(j=0; j<256; j++){
                _image[i][j] = fgetc(_source);
            }
        }
        done:
    I think it might be best if you broke out of this loop once you hit EOF. Otherwise if it's a small file, most of your array locations will be set to EOF. The only way I could think of, was to use a goto. You could also use two break statements, but it's not as simple.
    Code:
        for(i=0; i<256; i++){
            for(j=0; j<256; j++){
                _image[i][j] = fgetc(_source);
                if (_image[i][j] == EOF)
                {
                   _image[i][j] = 0;
                   goto done;
                }
            }
        }
        done:
    Code:
        >while(j<=i){
    This should be:
        while(j<i){

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    15
    Sorry it took me so long to get back to you. I had to reformat my HD. The file I'm using for the assignment will fill the whole array, but thanks for the general advise. It did not help with the Huffman codes, though. The ones computed at the end of execution are still messed up.

  4. #4
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Are your Huffman codes getting too long? How many bits have you allocated for your max code-lengths? If this rolls, which it would tend to do towards the end of the data...

    Hope this helps
    It is not the spoon that bends, it is you who bends around the spoon.

  5. #5
    Registered User
    Join Date
    Sep 2003
    Posts
    15
    Thanks for the help guys. I figured it out. One of the if statements had an extra condition in it. I don't know why it didn't affect all the codes. But, thanks again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 03-20-2009, 05:22 PM
  2. Coding Guideline ....!!
    By imfeelingfortun in forum Tech Board
    Replies: 8
    Last Post: 10-08-2006, 07:09 AM
  3. huffman tree
    By blazer26 in forum C Programming
    Replies: 0
    Last Post: 04-25-2006, 03:39 PM
  4. Huffman coding
    By misplaced in forum C++ Programming
    Replies: 2
    Last Post: 04-21-2005, 01:14 PM
  5. Coding Contest....
    By Koshare in forum A Brief History of Cprogramming.com
    Replies: 46
    Last Post: 10-14-2001, 04:32 PM