huffman encoding help

This is a discussion on huffman encoding help within the C Programming forums, part of the General Programming Boards category; I'm having problems figuring out how to encode/decode. This is the code i've got for encoding: Code: f = fopen("out.txt", ...

  1. #1
    Unregistered
    Guest

    huffman encoding help

    I'm having problems figuring out how to encode/decode.

    This is the code i've got for encoding:

    Code:
      f = fopen("out.txt", "w");
    
      for (i = 0; i < strlen(data); i++) {
        if (bit_pos == 8) {
          fputc(ch, f);
          ch = 0;
          bit_pos = 0;
        }
    
        for (y = 0; ; y++) {
          if (tree[data[i]].huf[y] == '\0') break;
          ch <<= 1;
          ch |= (tree[data[i]].huf[y] - 48);
          bit_pos++;
        }
      }
    and the test string i'm been using is: "hello"

    char : freq
    h 1
    e 1
    l 2
    o 1

    encoded then is:

    h : 111
    e : 110
    l : 0
    o : 10

    which then encoded with the above code comes out as: 1111100000000010

    when its decoded then it comes out as:

    hellllllllo

    because the decoder is picking up the extra 0's as 'l' (which i suppose is right) but is there anyway around that or a better way of encoding?

    Thanks

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I always liked this page, you may find it useful.
    http://ciips.ee.uwa.edu.au/~morris/Y...0/huffman.html

    -Prelude
    My best code is written with the delete key.

  3. #3
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    i know i'm stating the obvious here...

    the problem is in encoding your zero. maybe you're encoding an 'l' as 0000 but decoding it as 0

  4. #4
    Unregistered
    Guest

    update

    while the way i tried to get around it was once the for loop had ended to put this:

    for (bit_pos; bit_pos < 8; bit_pos++) {
    ch <<= 1;
    }

    to try and get rid of the redundant bits, that worked. But when i then tried with the string "hello*", it didn't work.

    It seems to work about 80% of the work, but of course thats not good enough.

    Any ideas?

  5. #5
    Unregistered
    Guest
    Ok, i've managed to fix the problems i was having but now another problem.

    I'm dynamic creating the huffman tree based on the frequency of the characters entered. The problem is once the program has ended the huffman tree to do the encoding/decoding is lost, so what is the best way to write out the huffman tree to the file?

    Thanks

  6. #6
    Unregistered
    Guest
    anyone?

  7. #7
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    Go Here and see #6.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Audio encoding (where to start)
    By cs_student in forum C++ Programming
    Replies: 4
    Last Post: 08-04-2008, 01:23 PM
  2. encoding scheme
    By blazer26 in forum C Programming
    Replies: 11
    Last Post: 05-02-2006, 11:45 PM
  3. huffman tree
    By blazer26 in forum C Programming
    Replies: 0
    Last Post: 04-25-2006, 03:39 PM
  4. Huffman Encoding
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-29-2001, 01:31 PM
  5. Huffman compression
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-01-2001, 07:30 AM

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