# Entropy2

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 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){

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);
}
}

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){
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]);
}
}
}

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]++;
}
}

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 int size;

public void add(Node n){
}else{
Node lastNode=null;
while((currentNode!=null)&&(n.freq>currentNode.freq)){
lastNode=currentNode;
currentNode=currentNode.next;
}
if(lastNode==null){
n.next=currentNode;
}else{
lastNode.next=n;
n.next=currentNode;
}
}
size++;
}

public Node removeFront(){
size--;
return temp;
}

public void printList(){
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;
}
}
```