|
Subject:
|
java program
|
|
Posted By:
|
todeepak_g
|
Post Date:
|
1/25/2006 5:04:47 AM
|
hello, i m a beginner in java.please help me in making this program
First count the number of times each word appears in the input file and find out frequency of occurrence of each word. Output the words and counts. Hint: Use StringTokenizer for extracting words from the file. Add all the words and frequencies to a HashMap.
B. Then compress the file using Huffman coding, as described below. Huffman coding has the following properties:
* Codes for more frequently occurring words are shorter than ones for less frequent words.
* Each code can be uniquely decoded.
Huffman codes are generated as follows:
A binary tree where the leaf nodes represent the words and internal nodes contain frequencies is constructed. Bit '0' represents following the left child and bit '1' represents following the right child.
* Use a priority queue (which contains frequencies) and remove two words with lowest frequencies from it.
* Create a new internal node, with the two just-removed frequency words as children and sum of their freqs as the new freq.
* Add the two frequencies and insert sum into priority queue.
* Repeat this procedure until the last word in priority queue.
(1) Output the Huffman code for each word stored in the HashMap, in text format, and
(2) Dump the Huffman code of the whole input file to a binary file.
Optional part:
Get the text back from given Huffman Coding by traversing the binary tree(decompression). The binary file created in the previous part can be read using FileInputStream, DataInputStream and calling appropriate method
(DataInputStream.readInt if you have written code as ints or DataInputStream.readChar in case of characters).
hi
|
|
