Huffman 트리 구축
1.구성 노드:
package Huffman;
public class Node implements Comparable{
private int weight;//
private int data;//
//private String code;
private Node leftNode;//
private Node rightNode;//
//
public Node(int data,int weight) {
this.data = data;
this.weight = weight;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
/**
*
*/
public int compareTo(Object o){
int k=0;
if(o instanceof Node){
Node node=(Node)o;
if(weight>node.weight){
k=1;
}
if(weight<node.weight){
k=-1;
}
if(weight==node.weight){
if(data>node.data){
k=1;
}
if(data<node.data){
k=-1;
}
}
}
return k;
}
}
2. Huffman ：
package Huffman;
import java.util.PriorityQueue;
public class hfmTree {
// , 256
protected String[] SaveCode=new String[256];
protected Node root;//
// , 256
private int[] ascii=new int[256];
private String str;
// ，
public hfmTree(int[] a,String str){
this.ascii=a;
this.str=str;
}
/**
* ascii
*/
public void createhfmTree(){
// ，
PriorityQueue<Node> queue=new PriorityQueue<Node>();
// ascii ，
for(int i=0;i<ascii.length;i++){
if(ascii[i]!=0){
//
Node node=new Node(i,ascii[i]);//i ，ascii （ ）
queue.add(node);//
}
}
// weight
while(queue.size()>1){
// ，
Node node1=queue.poll();
Node node2=queue.poll();//
//
Node result=new Node(Math.max(node1.getData(), node2.getData()),node1.getWeight()+node2.getWeight());
result.setLeftNode(node1);
result.setRightNode(node2);
queue.add(result);//
}
root=queue.peek();// ，
}
/**
* @param node:
* @param s： （ 01 ）
* ( )
* String SaveCode
*/
public void getBM(Node node,String s){
//node 0， 1
if (node.getLeftNode()!=null){
getBM(node.getLeftNode(),s+"0");
}
if(node.getRightNode()!=null){
getBM(node.getRightNode(),s+"1");
}
if(node.getLeftNode()==null&&node.getRightNode()==null)//
{
//
System.out.println(" :"+(char)node.getData()+" hfm "+s);
//
SaveCode[node.getData()]=s;
}
}
/**
*
* 01 byte
*/
public byte[] ChangeCode(){
String temp="";//
for(int i=0;i<str.length();i++){
temp=temp+this.SaveCode[str.charAt(i)];
}
int length=temp.length();
int zero=length%8;//zero
// for temp zero
for(int i=0;i<zero;i++){
temp=temp+"0";
}
// byte
byte[] array=new byte[temp.length()/8];
for(int i=0;i<temp.length()/8;i++){
array[i]=(byte)(-Integer.parseInt(String.valueOf(temp.charAt(8*i)))*128+
Integer.parseInt(String.valueOf(temp.charAt(8*i+1)))*64+
Integer.parseInt(String.valueOf(temp.charAt(8*i+2)))*32+
Integer.parseInt(String.valueOf(temp.charAt(8*i+3)))*16+
Integer.parseInt(String.valueOf(temp.charAt(8*i+4)))*8+
Integer.parseInt(String.valueOf(temp.charAt(8*i+5)))*4+
Integer.parseInt(String.valueOf(temp.charAt(8*i+6)))*2+
Integer.parseInt(String.valueOf(temp.charAt(8*i+7)))*1);
}
return array;
}
}
3. ：
package Huffman;
import java.util.Scanner;
public class Shuzu {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(" ：");
// ( )
Scanner scanner=new Scanner(System.in);
String s=scanner.next();
//
int [] array=new int [256];
for(int i=0;i<s.length();i++){
array[s.charAt(i)]++;
}
for(int i=0;i<array.length;i++){
if(array[i]!=0){
System.out.println(""+(char)i+array[i]);
}
}
// ，
hfmTree tree=new hfmTree(array,s);
//
tree.createhfmTree();
//
tree.getBM(tree.root,"");
System.out.println(" ：");
//
for(int i=0;i<s.length();i++){
System.out.print(tree.SaveCode[s.charAt(i)]);
}
System.out.println();
// byte
byte[] b=tree.ChangeCode();
System.out.println(" byte ：");
for(int i=0;i<b.length;i++){
System.out.print(b[i]+" ");
}
}
}
！
좋은 웹페이지 즐겨찾기
