Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedOutputStream;
- import java.io.BufferedInputStream;
- import java.io.*;
- import java.util.*;
- import java.io.IOException;
- public class HuffmanCompress{
- int freq[];
- PriorityQueue q;
- public HuffmanCompress()
- {
- }
- /*
- * Method for compressing the input data.
- *
- */
- public void compress (InputStream fileInputName, OutputStream fileOutputName) throws IOException {
- freq = new int[256];
- int nextbyte = 0; //Read the next character of InputStream
- while (nextbyte != -1) {
- //If not EOF
- nextbyte = fileInputName.read();
- freq[nextbyte]++; //Add frequency of nextbyte
- if (fileInputName.available() == 0) {
- break;
- }
- }
- HuffmanTree finalTree = buildTree(freq);
- String[] prefix = new String[256];
- String pos = "";
- makeTable(finalTree, prefix, pos);
- writeTree(finalTree, fileOutputName);
- }
- private HuffmanTree buildTree(int[] freq) {
- q = new PriorityQueue();
- for (int i = 0; i < freq.length; i++) {
- if (freq[i] > 0) {
- q.offer(new HuffmanLeaf(freq[i],(char)i)); //Require HuffmanLeaf class
- }
- }
- while (q.size() > 1) {
- HuffmanTree first = (HuffmanTree) q.poll(); //Require HuffmanTree
- HuffmanTree second = (HuffmanTree) q.poll(); //Require HuffmanTree
- q.offer(new HuffmanNode(first, second)); //Enqueue the combined tree
- }
- return (HuffmanTree)q.poll();
- }
- private void makeTable(HuffmanTree tree, String[] prefix, String s) {
- if (tree instanceof HuffmanLeaf) {
- HuffmanLeaf leaf = (HuffmanLeaf)tree;
- prefix[((HuffmanLeaf)tree).value] = s;
- System.out.println(((HuffmanLeaf)tree).value + " " + prefix[((HuffmanLeaf)tree).value]);
- }
- else {
- if (tree instanceof HuffmanNode) {
- HuffmanNode node = (HuffmanNode)tree;
- makeTable(((HuffmanNode) tree).left, prefix, s + '0');
- makeTable(((HuffmanNode) tree).right, prefix, s + '1');
- }
- }
- }
- private void writeTree(HuffmanTree tree, OutputStream fileOutputName) throws IOException{
- if (tree instanceof HuffmanLeaf) {
- WriteBuffer w = new WriteBuffer(fileOutputName);
- w.write(((HuffmanLeaf)tree).value, 8);
- }
- else if (tree instanceof HuffmanNode) {
- writeTree(((HuffmanNode)tree).left, fileOutputName);
- writeTree(((HuffmanNode)tree).right, fileOutputName);
- }
- }
- public String decompress (InputStream fileInputName, OutputStream fileOutputName) {
- return null;
- }
- public static void main (String[] args) {
- boolean compressed = args[0].indexOf('c') != -1;
- boolean decompressed = args[0].indexOf('d')!= -1;
- try{
- FileInputStream fin = new FileInputStream(args[1]);
- FileOutputStream fout = new FileOutputStream(args[2]);
- HuffmanCompress huffman = new HuffmanCompress();
- if(compressed){
- huffman.compress(fin,fout);
- }
- else if(decompressed){
- huffman.decompress(fin, fout);
- }
- }
- catch(FileNotFoundException e){
- System.out.println("File not found");
- }
- catch(IOException e){
- System.out.println("Fail");
- e.printStackTrace();
- }
- }
- /**
- *A simple class for writing bitstreams to bytestreams
- **/
- class WriteBuffer{
- int pos;//the number of bits in the buffer
- long buffer;
- OutputStream out;
- WriteBuffer(OutputStream out){
- this.out = out;
- }
- /**
- *Writes the n least significant bits of m to the buffer
- **/
- public void write(int n, int m) throws IOException{
- buffer = (buffer<<n) + m%(1<<n);
- pos = pos+n;
- while(pos>=8){
- out.write((int) (buffer>>(pos-8)));
- pos = pos-8;
- }
- }
- /**
- *pads the final output with 0's and writes to
- *the output stream
- **/
- public void flush() throws IOException{
- write((8-pos%8)%8,0);
- }
- }
- }
- =======================================================================================================
- import java.util.PriorityQueue;
- public class Node implements Comparable<Node> {
- Node right;
- Node left;
- Node parent;
- String text;
- int frequency;
- public Node(String textIn, int frequencyIn){
- text = textIn;
- frequency = frequencyIn;
- }
- public Node(int frequencyIn){
- text = "";
- frequency = frequencyIn;
- }
- public int compareTo(Node n){
- if (frequency < n.frequency){
- return -1;
- }
- else if(frequency > n.frequency){
- return 1;
- }
- return 0;
- }
- public static void printFromPreOrder(Node n, String dashes){
- // print the colon if leaf node
- if(n.text != ""){
- System.out.println(dashes + n.frequency + ":" + n.text);
- }
- else{
- System.out.println(dashes + n.frequency);
- }
- //Start recursive on left child then right
- if(n.left != null){
- printFromPreOrder(n.left, dashes + "-");
- }
- if(n.right != null){
- printFromPreOrder(n.right, dashes + "-");
- }
- }
- //Returns root node to pass to printFromPreOrder
- public static Node createTree(int frequencies[], String text[]){
- PriorityQueue<Node> queue = new PriorityQueue<Node>();
- for (int i = 0; i < text.length; i++) {
- Node n = new Node(text[i], frequencies[i]);
- queue.add(n);
- }
- Node root = null;
- while (queue.size() > 1) {
- Node least1 = queue.poll();
- Node least2 = queue.poll();
- Node combined = new Node(least1.frequency + least2.frequency);
- combined.right = least1;
- combined.left = least2;
- least1.parent = combined;
- least2.parent = combined;
- queue.add(combined);
- // Keep track until we actually find the root
- root = combined;
- }
- return root;
- }
- public static void main(String[] args) {
- int frequencies[] = {10, 15, 12, 3, 4, 13, 1};
- String text[] = {"a", "b", "c", "e", "nl", "sp", "t"};
- Node root = Node.createTree(frequencies, text);
- Node.printFromPreOrder(root, "");
- }
- }
- ====================================================================================================
- public class HuffmanLeaf extends HuffmanTree {
- char value;
- public HuffmanLeaf (int freq, char val) {
- super(freq);
- value = val;
- }
- public int compareTo(Object o) {
- return 0;
- }
- }
- ====================================================================================================
- import java.util.Comparator;
- abstract class HuffmanTree implements Comparable{
- int frequency; //Frequency of the tree
- public HuffmanTree (int freq) {
- frequency = freq;
- }
- public int compareTo (HuffmanTree tree) {
- return frequency - tree.frequency;
- }
- }
- ====================================================================================================
- class HuffmanNode extends HuffmanTree {
- HuffmanTree left;
- HuffmanTree right;
- public HuffmanNode (HuffmanTree l, HuffmanTree r) {
- super (l.frequency + r.frequency);
- left = l;
- right = r;
- }
- public int compareTo(Object o) {
- return left.frequency - right.frequency;
- }
- }
- ====================================================================================================
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement