Thread: HUffman encoding(data compression)

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    3

    HUffman encoding(data compression)

    i have a static code of hauffman encoding but i want to write a code that reads a file and calculate frequencies and encode the file. here is my code can any one help me to change it to adaptive code..
    Code:
    #include<iostream>
    #include<string.h>
    #include<stdlib.h>
    using namespace std;
    const int max=10;
    
    
    	class node
    	{
    	  public:
    		int freq;
    		char ch[10];
    		node* right;
    		node* left;
    	};
    
    
    	node* make_node(char* a, int x)
    	{
    		node* nptr= new node;
    		nptr->freq = x;
    		strcpy( nptr->ch , a);
    		nptr->right = nptr->left = NULL;
    		return nptr;
    
    	}
    
    	
    
    	void sort(node* a[], int n)
    	{
    		node* tptr;
    
    		for (int i = 0; i < n-1 ; i++)
    
    			for (int j = i; j < n; j++)
    
    				    if (a[i]->freq > a[j]->freq)
    				    {
    					tptr = a[i];
    					a[i] = a[j];
    					a[j] = tptr;
    				    }
    	}
    
    	
    	void shift_right(node* a[], int n)
    	{
    	       for (int i = 1; i < n - 1; i++)
    			a[i] = a[i + 1];
    
    	}
    
    	void encode(node* tptr, int c[], int n)
    	{
    	       if ((tptr->left == NULL) && (tptr->right == NULL))
    	       {
    			cout<<" code:   "<< tptr->ch<<"    ";
    
    			   for (int i = 0; i < n; i++)
    			  {
    				cout<< c[i];
    			  }
    
    			   cout<<endl;
    
    		}
    
    		else
    		{
    			c[n] = 1;
    			n++;
    
    			encode(tptr->left, c, n);
    
    			c[n - 1] = 0;
    
    			encode(tptr->right, c, n);
    		}
    
    	}
    
    	
    
        	void del(node * root)
    	{
    		if(root!=NULL)
    		{
    			del(root->left);
    			del(root->right);
    			delete root;
    		}
    
    	}  
    
        
    
    int main()
    
    {
    	  
    	    node* nptr;
    	    node* head;
    	    node* a[20];
    
    	    int n,freq,b,c[15];
    
    	    char str[10];
    
    	    cout<<"\n\n\tEnter the no.of letter you want to code: " ;
    	    cin>>n;
    
    	    for (int i = 0; i < n; i++)
    
    	    {
    			cout<<"\n\tEnter the string: " ;
    			cin>>str;
    
    			cout<<"\n\tEnter frequency: ";
    			cin>>freq;
    
    			a[i] = make_node(str, freq);
    
    	    }
    
    	   while (n > 1)
    	    {
    			sort(a, n);
    
    			b = a[0]->freq + a[1]->freq;
    
    			strcpy(str,a[0]->ch);
    			strcat(str,a[1]->ch);
    			nptr = make_node(str, b);
    			nptr->right = a[1];
    			nptr->left = a[0];
    			a[0] = nptr;
    			shift_right(a, n);
    			n--;
    
    	    }
    
    	    encode(a[0], c, 0);
    	  
    		system("pause");
    }
    Last edited by Salem; 05-30-2010 at 04:43 AM. Reason: Added [code][/code] tags - learn to use them yourself

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by jia View Post
    i have a static code of hauffman encoding but i want to write a code that reads a file and calculate frequencies and encode the file. here is my code can any one help me to change it to adaptive code..
    FYI, that code doesn't even come close to being a Huffman compressor, static or otherwise. For one thing, your implementation attempts to deal with the frequencies of "strings". You should instead be calculating the frequency of each individual character in the entire block to be encoded. Also, the maximum number of nodes in a Huffman tree is 511 (assuming 8-bit characters), but you only set aside enough room for 20! Finally, the whole point of a compressor is to, well, compress stuff, and your code doesn't do any such thing. So the question is: Why are you trying to convert your code to the "adaptive" algorithm when you haven't even got the "static" one working correctly?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    3
    well if its not working properly thn can u guide me in writing a new one...

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by jia View Post
    well if its not working properly thn can u guide me in writing a new one...
    Sure. First, start by learning how to ask smart questions. In other words, don't simply ask "How do I build a house?" - if you want someone else to do it for you, then hire a contractor. Otherwise, you'll need to research your problem well, formulate your misunderstandings clearly, and be prepared to do most of the "footwork" yourself. Fair enough?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Here is a complete implementation of the static Huffman algorithm in C++. Not sure how helpful the code may be to you (as a learning tool), but in any case, it might be useful for verifying the results of your own implementation.

    Cheers!
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Huffman Compression Program
    By ChadJohnson in forum C++ Programming
    Replies: 13
    Last Post: 01-23-2005, 02:49 PM
  2. compression
    By X PaYnE X in forum C Programming
    Replies: 20
    Last Post: 01-11-2005, 05:14 PM
  3. efficient compression algorithm pls
    By gooddevil in forum C Programming
    Replies: 7
    Last Post: 05-08-2004, 03:33 AM
  4. IDEA: Huffman compression function
    By confuted in forum Contests Board
    Replies: 4
    Last Post: 07-01-2003, 07:05 PM
  5. Huffman compression
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-01-2001, 07:30 AM