Entropy2

From Progteam

Revision as of 18:28, 10 November 2007 by Jjx203 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Jjx203.


Idea: The idea is really simple. I don't see any difference between this so-called entropy encoder and Huffman encoder. Therefore, I use Huffman's method to encode the message and calculate the total bits required by both an ASCII encoder and a Huffman encoder and solved this problem.

import java.util.*;

public class Main{
	//stat 0-25 represents A-Z, 26-35 represents 0-9, 36 represents _
	public static int[] stat;
	public static int[] code;
	public static int charCount;
	public static NodeList list;
	public static void main(String[] args){
		Scanner reader=new Scanner(System.in);
		
		String line=reader.next();
		while(!line.equals("END")){
			getStatistics(line);
			getList();
//			printStat();
			getCode(list);	
			int ascL=calcASCLength();
			int L=calcLength();
			double ratio=((double)ascL)/L;
			long round=Math.round(ratio*10);
			double ratio_m=round/10.0;
			System.out.println(ascL+" "+L+" "+ratio_m);					
			line=reader.next();		
		}
	}
	
	public static int calcASCLength(){
		int sum=0;
		for(int i=0;i<stat.length;i++){
			sum=sum+stat[i]*8;
		}
		return sum;
	}
	
	public static int calcLength(){
		int sum=0;
		for(int i=0;i<stat.length;i++){
			sum=sum+stat[i]*code[i];
		}
		return sum;
	}
	
	public static void getCode(NodeList list){
		if(list.size==1){
			String ids=list.head.index;
			int id=Integer.parseInt(ids);
			code[id]++;
		}
		while(list.size>1){
//			list.printList();
//			printCode();
			mergeList(list);
		}
//		printCode();
//		list.printList();
	}
	
	public static void getStatistics(String line){
		stat=new int[37];
		code=new int[37];
		charCount=0;
		for(int i=0;i<line.length();i++){
			char ch=line.charAt(i);
			if((ch>='A')&&(ch<='Z')){
				stat[ch-'A']++;
			}else if(ch=='_'){
				stat[36]++;
			}
			else{
				stat[ch-'0'+26]++;
			}
		}
	}
	
	public static void getList(){
		list=new NodeList();
		for(int i=0;i<stat.length;i++){
			if(stat[i]!=0){
				Node n=new Node(i,stat[i]);
				list.add(n);
			}
		}
	}
	
	public static void mergeList(NodeList list){
		Node n1=list.removeFront();
		Node n2=list.removeFront();
		Node n=new Node(n1.index+" "+n2.index,n1.freq+n2.freq);
		StringTokenizer t=new StringTokenizer(n.index);
		while(t.hasMoreTokens()){
			String num=t.nextToken();
			int id=Integer.parseInt(num);
			code[id]++;
		}
		list.add(n);
	}
	
	public static void printStat(){
		for(int i=0;i<stat.length;i++){
			System.out.print(stat[i]+" ");
		}
	}
	
	public static void printCode(){
		for(int i=0;i<stat.length;i++){
			System.out.print(code[i]+" ");
		}
	}
	
	
}

class NodeList{
	public Node head;
	public int size;
	
	public void add(Node n){
		if(head==null){
			head=n;
		}else{
			Node currentNode=head;
			Node lastNode=null;
			while((currentNode!=null)&&(n.freq>currentNode.freq)){
				lastNode=currentNode;
				currentNode=currentNode.next;				
			}
			if(lastNode==null){
				n.next=currentNode;
				head=n;
			}else{
				lastNode.next=n;
				n.next=currentNode;
			}		
		}
		size++;
	}
	
	public Node removeFront(){
		Node temp=head;
		head=head.next;
		size--;
		return temp;		
	}
	
	public void printList(){
		Node temp=head;
		while(temp!=null){
			System.out.println("Size:"+size);
			System.out.print("("+temp.index+" "+temp.freq+"),");
			temp=temp.next;
		}
	}
}

class Node{
	public String index;
	public int freq;
	public Node next;
	public Node(int i,int f){	
		index=String.valueOf(i);
		freq=f;
	}
	
	public Node(String i,int f){
		index=i;
		freq=f;
	}	
}
Personal tools