|
I'll have to find the usb drive I have it on since I did it a little while ago. Hopefully I'll find it by tommorrow and post the code so you can see it.
But here's an explaination of how it works (please note if you don't know what a tree, structure, or linked list is I would suggest reading the wikipedia articles to learn that first since huffman uses them):
Suppose you had a long text file where all the letters were either an A,B,C,or D and you wanted to save them in the minumum space possible. Also suppose you knew that 80% were A, 15% were B, 3% were C, 2% were D. You could give each letter a 2 digit binary code but that would not be as efficient as giving the most commons letter(s) a shorter binary code even if this means the less common ones have to be slightly longer code.
For instance huffman would give them these codes:
A = 0
B = 10
C = 110
D = 111
It creates these codes by creating an unbalanced binary tree. To do this you create a list of nodes that are placed in order according to frequency. Then you remove the 2 least common nodes and create a parent node for them that contains the frequency of both nodes and place the parent node back into the list in order. You keep doing this till you have only 1 node and that node is your root node.
Here's what the tree looks like:
Root...................................(ABCD Freq 100%)
Level 1..........(A Freq 80% Code 0)..................(BCD Freq 20%)
Level 2...............................(B Freq 15% Code 10).........(CD Freq 5%)
Level 3.............................................(C Freq %3 Code 110)..(D Freq 2% Code 111)
The codes are determinded by where the node is on the tree. Left is 0 right is 1. To encode you create the tree and write the binary code for each symbol. To decode you start at the root and go left if the number is 0 and right if it is 1. You continue doing this until you reach a leaf node. Once you reach a leaf node you write the letter and start again at the root.
|
|
|
|
|
thx mates ..
i am oready know about the teory ..
but i feel hard to write it down to a code ..
specially in jscript ..
thank you very much for answer my question
regards
novhard
|
|
|
|
|
Basically this is a project I did in college, it reads a file with 0s and 1s (he didn't encript the punctuation) and writes out the message in plain text. He also gives us a file with the frequencies and we also had to print some other misecleous stuff in the console window if I recall.
ps code project system took out the indents in the code and stripped out my includes for some reason, just so you know.
modified on Monday, April 20, 2009 12:44 PM
|
|
|
|
|
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MAXBITS 26
void prq_create(struct prqueue*);
int prq_empty(struct prqueue*);
void prq_insert(struct prqueue*, struct info_node*);
void prq_remove(struct prqueue*, struct info_node*);
void merge_nodes(struct info_node*, struct info_node*, struct info_node*);
void init_node(struct info_node*);
void print_level_order(FILE*, struct info_node*);
void print_code(FILE*, struct info_node*);
int isleft(struct info_node*);
int build_numcode(struct info_node*, int []);
void print_code(FILE*,struct info_node* pleaf_location[]);
void build_pque (FILE*, struct prqueue*, struct info_node* []);
struct info_node* build_tree (struct prqueue*);
void print_inorder(FILE*, struct info_node*);
void decode (FILE* ,struct info_node* , FILE*);
#define TRUE 1
#define FALSE 0
struct info_node
{
char code[MAXBITS] ;
float weight ;
int level ;
struct info_node* father ;
struct info_node* left ;
struct info_node* right ;
struct info_node* next ;
} ;
struct prqueue
{
struct info_node * prqtop ;
};
struct lo_queue
{
struct info_node* front ;
struct info_node* rear ;
};
int main()
{
struct prqueue pque ;
struct info_node* pleaf_location[MAXBITS] ;
struct info_node* tree_root ;
FILE* infile; FILE* outfile; FILE* dec_result; FILE* bitfile;
int count = 0;
infile = fopen("symb_freq.txt", "r");
outfile = fopen("code_tree.txt", "w");
bitfile = fopen("bit_file.txt", "r");
dec_result = fopen("decoded_file.txt", "w");
//builds the priority queue
pque.prqtop = NULL;
build_pque(infile, &pque, pleaf_location);
fclose(infile);
////builds the tree
tree_root = build_tree(&pque);
//does the inorder traversal
print_inorder(outfile, tree_root);
fprintf(outfile, "\n\n");
//prints the level order traversal
print_level_order(outfile, tree_root);
//prints the code for each letter
print_code(outfile, pleaf_location);
//decodes the zeros and ones into a message
decode(bitfile, tree_root, dec_result);
fclose(outfile);
fclose(bitfile);
fclose(dec_result);
return( 0 ) ;
} // end of function main()
void build_pque (FILE* infile, struct prqueue* pque, struct info_node* pleaf_location[])
{
int n = 0; struct info_node* node;
//creates the priority queue and loads pleaf_location array
while(!feof(infile))
{
node = (info_node*) malloc(sizeof(struct info_node));
init_node(node);
fscanf(infile, "%s", &node->code[0]);
fscanf(infile, "%f", &node->weight);
prq_insert(pque, node);
pleaf_location[n] = node;
n++;
}
}
struct info_node* build_tree (struct prqueue* pque)
{
struct info_node* p1; struct info_node* p2;
struct info_node* rnode; struct info_node* tree_root;
//builds the tree
while(pque->prqtop->next != NULL)
{
p1 = pque->prqtop;
p2 = p1->next;
pque->prqtop = p2->next; //moves top to the next spot
rnode = (info_node*) malloc(sizeof(struct info_node));
init_node(rnode);
merge_nodes(p1, p2, rnode);
prq_insert(pque, rnode);
}
tree_root = pque->prqtop;
pque->prqtop = NULL;
return tree_root;
}
void print_code(FILE* outfile, struct info_node* node)
{
int n = 0;
while(node->code[n] != '\0')
{
fprintf(outfile, "%c",node->code[n]);
n++;
}
fprintf(outfile, " ");
}
//makes a node and inititializes it
void init_node (struct info_node* node)
{
node->father = NULL;
node->left = NULL;
node->right = NULL;
}
//test if it is empty
int prq_empty(struct prqueue* prq)
{
if (prq->prqtop == NULL)
return TRUE;
else
return FALSE;
}
//inserts node into priority queue
void prq_insert(struct prqueue* prq, struct info_node* node)
{
struct info_node* curnode; struct info_node* lastnode = NULL;
curnode = prq->prqtop;
if ((curnode == NULL) || (node->weight <= curnode->weight)) //inserts at the start of the queue
{
node->next = curnode;
prq->prqtop = node;
}
else //moves through the list and inserts at the right spot
{
//lastnode = curnode;
//curnode = lastnode->next;
while ((curnode != NULL) && (node->weight > curnode->weight))
{
lastnode = curnode;
curnode = lastnode->next;
}
lastnode->next = node;
node->next = curnode;
}
return;
}
//removes one node and passes it back by reference
void prq_remove(struct prqueue* prq, struct info_node* node)
{
node = prq->prqtop;
prq->prqtop = node->next;
node->next = NULL;
}
//this creates a new node above the 2 existing nodes and calculated values for the new node
void merge_nodes(struct info_node* p1, struct info_node* p2, struct info_node* rnode)
{
//links nodes
rnode->left = p1;
rnode->right = p2;
p1->father = rnode;
p2->father = rnode;
//calculates value for the father
rnode->weight = p1->weight + p2->weight;
strcpy(rnode->code , p1->code);
strcat(rnode->code, p2->code);
//clears old links
p1->next = NULL;
p2->next = NULL;
}
//builds the code in left to right order. //this will be reversed when it is read
int build_numcode(struct info_node* node, int numcode [])
{
int count = 0;
while (node->father != NULL)
{
if (isleft(node))
{
numcode[count] = 0;
count += 1;
}
else
{
numcode[count] = 1;
count += 1;
}
node = node->father;
}
return count;
}
//test if the node is on the left side of the father node
int isleft(struct info_node* node)
{
if (node == node->father->left)
return TRUE;
else
return FALSE;
}
///////////////////////////////////////////////////////////////////////////////
// PRINTS THE CODE FOR EACH LETTER
void print_code(FILE* outfile, struct info_node* pleaf_location[])
{
int n; int a; int count; int numcode[10];
//prints the code for each letter
fprintf(outfile, "\n\n");
for (n = 0; n < MAXBITS; n++)
{
count = build_numcode(pleaf_location[n], numcode);
fprintf(outfile, "Symbol: %c Huffman Code: ", pleaf_location[n]->code[0]);
for (a = (count - 1); a >= 0; a--) //prints code in reverse order
fprintf(outfile, "%d", numcode[a]);
fprintf(outfile, "\n");
}
}
////////////////////////////////////////////////////////////////////////////////
// IN ORDER TRAVERAL CODE
void print_inorder(FILE* outfile, struct info_node* node)
{
if (node != NULL)
{
print_inorder(outfile, node->left);
fprintf(outfile, "FREQUENCY: %f SYMBOL: ", node->weight);
print_code(outfile, node); //prints out all the letters
fprintf(outfile, "\n");
print_inorder(outfile, node->right);
}
}
////////////////////////////////////////////////////////////////////////////////////////
//LEVEL ORDER TRAVERSAL CODE
//prints the current layer and gets nodes of the next layer
void print_level_order(FILE* outfile, struct info_node* tree_root)
{
struct info_node* left; struct info_node* right; int level = 0;
struct lo_queue* queue;
queue = (lo_queue*) malloc(sizeof(struct lo_queue));
//prints out the levels
tree_root->level = 0;
queue->rear = tree_root;
queue->front = tree_root;
fprintf(outfile, "level 0: ");
//print_levels(outfile, &real_queue);
while(queue->rear != NULL)
{
if (queue->rear->level != level) //if level changed
{
fprintf(outfile, "\n");
fprintf(outfile, "level %d: ", queue->rear->level);
}
print_code(outfile, queue->rear);
level = queue->rear->level;
//puts atoms in the queue
left = queue->rear->left;
if (left != NULL)
{
left->level = level + 1;
queue->front->next = left;
queue->front = left;
}
right = queue->rear->right;
if (right != NULL)
{
right->level = level + 1;
queue->front->next = right;
queue->front = right;
}
queue->rear = queue->rear->next;
}
}
////////////////////////////////////////////////////////////////////////////////////////
//Decoding
void decode (FILE* infile,struct info_node* tree_root, FILE* outfile)
{
char num; int n = 0; struct info_node* node;
node = tree_root;
while(!(feof(infile)))
{
fscanf(infile, "%c", &num);
if (num == '0')
{
node = node->left;
if (node->left == NULL) //is a leaf node
{
fprintf(outfile, "%c" , node->code[0]);
node = tree_root;
}
}
else if (num == '1')
{
node = node->right;
if (node->right == NULL) //is a leaf node
{
fprintf(outfile, "%c" , node->code[0]);
node = tree_root;
}
}
else
{
fprintf(outfile, "%c", num);
}
n++;
}
}
|
|
|
|
|
00110100 011011011111011111 00001101000111100 00001010100000001100111 0001101
110000100 01111001111000101-1000010001011111111001010000, 00001101110000
11101111011110 001111001010 11100101100 010010101100111000010011111
10000100100101000111011110, 00001101110000 0000110100110010
11100101100
10010101111111010011010011111 110000110010 000011010010110101
010010101100111000011010101 0011010110000110 010011000101000111010111010
01000101011101111010111001010111011000011110100 0101101111001101100000111,
00001101110000 11100011111011010110011 00001101000111100 11100101100
11110101100101100, 1111010111100001000101000110010 1110101011111 0000110100
1100010100001010111010001011000 110100101
011011101100011100011011101010001110111. 00001101110000 0001101
011110001001010000101100 00001101000111100 0101101111001101100000111,
1100111101001000100010110100011110010100000111
11100101100
10111010011100010110000100000010011111 11100011111011010110011 001111001010,
111111000101101100100010111010110011 000011010010110101 001001011010000111000
11000111010011010001010111 001010101110100111 0000110100
010011101101001111001010000 110100101 0000110100
11001111010010001000101101010011111. 00001101110000
00110011010010101000010001000101 11101010110010 001011101010100111 110100101
110011110100100010001011010001111001010000 110000100010011101001111000111
111111000111000010101000010010001011001000100 0001101 00001101000111100
1001010111110111, 1011000 10110111 0000110100 010110111100110110000 110100101
0000110100 110001100110111000111110100 0001101 1110111100001000101 11010101
0001101 1110110000110111110101101110110 1011000, 1110101011111 0001101
101110100111000101100001000000100 101010000110
110011110100100010001011010001111001010000, 11110111011001010111010110011
10110000111 001011101010001010111111110000101111011010 11011010
011101000010010110 110001010110111010010011011110001111101000111 1110101011111
1101010111001111101010101100100100010111010110011 10110000111
11000111010011010001010111 10111010
011101000010010110 001011101010100111,
11100111 0001101 000011010000111 0111011011101111011110 011110010000111
0011111010111000 111101011001001110011110110010 0001101
100001010010110001001000 000011010010110101 0111111000101100000110010
1110101011111 011011101100011100011011101010001110111.
|
|
|
|
|
a 8.167
b 1.492
c 2.782
d 4.253
e 12.702
f 2.228
g 2.015
h 6.094
i 6.966
j 0.153
k 0.772
l 4.025
m 2.406
n 6.749
o 7.507
p 1.929
q 0.095
r 5.987
s 6.327
t 9.056
u 2.758
v 0.978
w 2.360
x 0.150
y 1.974
z 0.074
|
|
|
|
|
thx MikeMarq
this code really help me ..
regards
novhard
|
|
|
|
|
I'm trying to display text in the shape of a cross on a JFrame using 4 JTextAreas but when I do all of the JTextAreas display correctly except the last one which ends up in the upper left corner. It is always the last item that ends up in the wrong spot. For instance I tried creating the west one first and it was then fine but then south became wrong. Here's the display code thanks in advance for your help.
Mike
JFrame frame = new JFrame();
jtextnorth = new JTextArea ("North" + '\n' + party[0] + '\n');
jtextnorth.setLocation(150, 0);
jtextnorth.setSize(100,100);
frame.add(jtextnorth);
jtexteast = new JTextArea ("East" + '\n' + party[1] + '\n');
jtexteast.setLocation(300, 150);
jtexteast.setSize(100,100);
frame.add(jtexteast);
jtextsouth = new JTextArea ("South" + '\n' + party[2] + '\n');
jtextsouth.setLocation(150, 300);
jtextsouth.setSize(100,100);
frame.add(jtextsouth);
jtextwest = new JTextArea ("West" + '\n' + party[3] + '\n');
jtextwest.setLocation(25, 150);
jtextwest.setSize(100,100);
frame.add(jtextwest);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(400,400);
frame.setVisible(true);
|
|
|
|
|
Hi All,
I am working on an online assessment tool for that i want to show the time to user for the test he/she would be taking so can anyone tell something about how to add time in it.
I am using struts 2.0 framework.
Regards
Kaushal Kishore Sharma
|
|
|
|
|
Can any body tells me how to make a video player in java? 
|
|
|
|
|
It's not suitable for java to make a video player.I think.
|
|
|
|
|
I appreciate your assistance. 
I need to log into a website with both a user name, password, and a certificate.
I have the username, password, and certificate information (using firebug).
I have the URL syntax to transmit the username and password.
What I can't figure out is which object is best used to transmit the certificate information when I connect to the site.
Thank you in advance
|
|
|
|
|
in JSP how to get text from radio button
|
|
|
|
|
String value=request.getParameter("radio");
|
|
|
|
|
Can anyone tell me how to get special folder icon (eg . My Computer , Network place,My Picture...) ?
|
|
|
|
|
The icons are found in "(c:/windows/system32/)shell32.dll".
I am not aware have not tried to access it using Java, therefore I suggest using a program to extract the icons and then include them in your project.
IconEdit[^]
Microangelo/[^]
hmmm pie
|
|
|
|
|
|
www.google.com
It's got everything you need
Panic, Chaos, Destruction.
My work here is done.
|
|
|
|
|
Hello
I am developing an application desktop based in Java Swing, in which there is a data entry form where use will enter book title and book author in URDU langauge and it will store in database. But i am unable to store URDU in db although i have set URDU as my keyboard input langauge from windows regional options. When i enter urdu word in textfield and press save button then instead of saving urdu word it stores "??????".
I am using ms access. if i write urdu word in title column in database then it is fine but when i try to retreive it on JTable it again display "??????".
Please any body who can tell me how to store and retrieve URDU using java?
if java is not supporting it then please tell me any other tool which will solve my urdu langauge storage and retreival problem?????
Regards
Atiya Khan
|
|
|
|
|
Hi All,
I want to know the method for appending data on an excel file using java or jsp or struts framework.
Please help me.
Regards
Kaushal Kishore Sharma
|
|
|
|
|
hi can anyone help me to find out if there is any IDE avail for java application programming and the JSP too like Visual studio for .net
thanx in advance
the code is here, mind is clear.
modified on Friday, April 10, 2009 8:06 AM
|
|
|
|
|
There are numerous IDE's available for Jave - the top ones are probably Eclipse and Netbeans, both free. Oracle JDeveloper is also free, and another top one is IntelliJ IDEA, which is not.
Scott
|
|
|
|
|
yaa!! i know netbeans and eclipse but what i am talking about here is a drop down feature like VS i seen it in JFrame builder (a very limited approach for drop down)
so can i make it for a full like VS.
Thanx
|
|
|
|
|
I'm trying to build a server application that will allow users to upload multiple files from the users local computer (e.g. 100 text files in one go) into it via browser.
I'd like to use tag libraries as much as possible.
I'm using the Struts-html tag library e.g <html:file property="someStrutsAction" xmlns:html="#unknown"> but I don't know how to use it for multiple files upload - is there anything better than the Struts-html?
Any help will be much appreciated,
Pav
Pav
|
|
|
|
|
I've just found this - hope this will help me - I'll keep posting either way
http://www.theserverside.com/discussions/thread.tss?thread_id=37184
Pav
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
