Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- class HuffmanNode implements Comparable<HuffmanNode>{
- HuffmanNode right;
- HuffmanNode left;
- HuffmanNode parent;
- int count;
- String letter;
- public HuffmanNode(){}
- public HuffmanNode (String letter, int count){
- this.letter = letter;
- this.count = count;
- }
- public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){
- this.letter = letter;
- this.count = count;
- this.left = left;
- this.right = right;
- this.parent = parent;
- }
- public void setCount(int count){
- this.count = count;
- }
- public int getCount(){
- return count;
- }
- public void setRight(HuffmanNode right){
- this.right = right;
- }
- public HuffmanNode getRight(HuffmanNode right){
- return right;
- }
- public void setLeft(HuffmanNode left){
- this.left = left;
- }
- public HuffmanNode getLeft(HuffmanNode left){
- return left;
- }
- public void setParent(HuffmanNode right){
- this.left = left;
- }
- public HuffmanNode getParent(HuffmanNode parent){
- return parent;
- }
- public void buildTree(HuffmanNode node){
- if (node.compareTo(this) <= 0 && left != null){
- System.out.println(node.getCount() + ":" + this.count);
- left.buildTree(node);
- }
- else if (node.compareTo(this) <= 0 && left == null){
- this.left = node;
- node.parent = this;
- }
- else if (node.compareTo(this) > 0 && right != null){
- System.out.println(node.getCount() + ":" +this.count);
- right.buildTree(node);
- }
- else if (node.compareTo(this) > 0 && right == null){
- this.right = node;
- node.parent = this;
- }
- }
- public int compareTo(HuffmanNode x){
- return this.count - x.count;
- }
- public void genCode(String s){
- if(left != null){
- left.genCode(s + "0");
- }
- if(right != null){
- right.genCode(s + "1");
- }
- if (left == null && right == null){
- System.out.println(s);
- }
- }
- }
- public class hw4{
- public static void main (String []args)throws IOException{
- //ask user to enter file name
- System.out.printf("Enter a file location and name to encode [press Enter]: ");
- Scanner input = new Scanner(System.in);
- String filename = input.next();
- //Gets file name from Scanner and checks to see if valid
- File file = new File(filename);
- //if (!file.isFile()){
- //System.out.printf("Enter a file location and name to encode [press Enter]: ");
- //}
- Scanner text = new Scanner(file);
- String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
- int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
- String letter;
- String tempStr;
- int tempInt;
- while(text.hasNext()){
- letter = text.next();
- //System.out.printf("%s\n", letter);
- char c = letter.charAt(0);
- int index = c - 97;
- freq[index]++;
- }
- for(int i=0; i <25; i++){
- System.out.printf("%s:%d\n", letters[i], freq[i]);
- }
- System.out.printf("\n");
- for (int n=0; n <25; n++) {
- for (int i=0; i <25; i++) {
- if (freq[i] > freq[i+1]) {
- // exchange elements
- tempInt = freq[i];
- tempStr = letters[i];
- freq[i] = freq[i+1];
- letters[i] = letters[i+1];
- freq[i+1] = tempInt;
- letters[i+1] = tempStr;
- }
- }
- }
- PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>();
- for(int i=0; i <26; i++){
- System.out.printf("%s:%d\n", letters[i], freq[i]);
- if(freq[i] > 0){
- huffmanList.add(new HuffmanNode(letters[i],freq[i]));
- }
- }
- HuffmanNode root = new HuffmanNode();
- while(huffmanList.size() > 1){
- HuffmanNode x = huffmanList.poll();
- HuffmanNode y = huffmanList.poll();
- HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
- if(root == null){
- root = result;
- }
- else{
- root.buildTree(result);
- }
- huffmanList.add(result);
- }
- root.genCode(" ");
- }
- }
- input file data:
- a
- a
- a
- a
- d
- d
- d
- d
- d
- d
- d
- d
- k
- k
- k
- k
- k
- k
- f
- f
- f
- f
- f
- f
- h
- h
- h
- h
- h
- h
- b
- b
- b
- b
- b
- b
- b
- b
- n
- n
- n
- n
- n
- n
- n
- e
- e
- e
- e
- e
- i
- i
- i
- i
- i
- i
- i
- i
- l
- k
- j
- a
- n
- s
- g
- l
- k
- j
- a
- s
- v
- o
- i
- j
- a
- s
- d
- l
- k
- g
- k
- n
- m
- a
- s
- d
- k
- l
- o
- v
- h
- a
- s
- d
- g
- z
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement