[Java] Huffman Coding 2/2

공학수학2 / 2002년 2학기 / 박근수 교수님

[HuffmanTree.java]

import java.io.*;

/** 이곳이 HEAP을 구현한 부분입니다! **/
class Heap
{
       public Heap()
       {
               size = 0;                                                                                // 현재 heap내에 data는 0개
               data = new Comparable[DEFAULT_CAPACITY+1];                // 어느정도 크기만큼 초기화
       }

       public Heap(Comparable[] array)                                                // array 내용을 바로 heap에 넣음
       {
               size = array.length;                                                        // data의 갯수는 array길이만큼.
               data = new Comparable[array.length+1];                        // array 길이보다 1 크게 초기화함.
               for (int i=0; i<array.length; i++)
                       data[i+1] = array[i];                                                // data들을 넣음
               buildHeap();                                                                        // heap으로 만듬
       }

       private void buildHeap()
       {
               for (int i=size/2; i>0; i--)                                        // child를 갖고 있는 노드 중 가장 아래 노드부터 맨 위 root 노드까지
                       compareDown(i);                                                                // 아래로 내릴 수 있는곳까지 내림.
       }

       private void compareDown(int index)                                        // child와 비교해 내려갈 수 있으면 내려가는 메쏘드
       {
               int child = index*2;                                                        // index를 두배하면 child중 왼쪽 node
               if (child > size)                                                                // 만약 child가 없으면 그냥 return
                       return;
               if (child!=size && data[child].compareTo(data[child+1])>0)                        // 오른쪽 child가 존재하고, 그 node의 값이 왼쪽보다 작으면
                       child++;                                                                                                                // 왼쪽 node 대신 오른쪽 node를 비교 대상으로 정함
               if (data[index].compareTo(data[child]) > 0)                        // 비교 대상으로 정해진 child와 현재 node를 비교해서 현재 node가 더 작으면
               {
                       swap(index, child);                                                                // 두 node를 바굼
                       compareDown(child);                                                                // 바꾼 아래 node에 대해 같은 작업 반복 (recursive call)
               }
               return;
       }

       private void compareUp(int index)                                        // 위와 반대로 수행함. 같은 원리
       {
               int parent = (int)(index/2);
               if (parent < 1)
                       return;
               if (data[index].compareTo(data[parent]) < 0)
               {
                       swap(index, parent);
                       compareUp(parent);
               }
               return;
       }

       private void swap(int i1, int i2)                                        // node 두 개를 바꿈
       {
               if (i1>size || i2>size)
               {
                       System.out.println("Swapping Element Failure in Heap!");
                       System.exit(0);
               }
               else
               {
                       Comparable temp = data[i1];
                       data[i1] = data[i2];
                       data[i2] = temp;
               }
       }

       public Comparable removeMin()                                                // 가장 작은 node를 뱉으면서 삭제
       {
               if (size < 1)
               {
                       System.out.println("Error : remove element with empty heap.");
                       System.exit(0);
               }
               Comparable minValue = data[1];
               data[1] = data[size--];                                                        // 맨 위를 빼고, 맨 뒤에 노드를 맨 위로 올림
               compareDown(1);                                                                        // 그 노드를 내릴 수 있는곳까지 내림
               return minValue;
       }

       public void insert(Comparable x)
       {
               if (++size == data.length)                                                // 크기를 1 플러스 하고, 그게 현재 array 길이보다 길면 array를 두배함.
                       doubleArray();
               data[size] = x;                                                                        // 마지막에 데이타 추가
               compareUp(size);                                                                // 그 노드를 올릴 수 있는 곳까지 올림.
       }

       private void doubleArray()                                                        // array 크기를 두배함
       {
               Comparable[] newArray = new Comparable[data.length*2];
               for (int i=0; i<data.length; i++)
                       newArray[i] = data[i];
               data = newArray;
       }

       public boolean isEmpty()
       {
               return (size==0);
       }

       private static final int DEFAULT_CAPACITY = 100;
       private Comparable[] data;
       private int size;
}

public class HuffmanTree
{
       public HuffmanTree()
       {
               count = new int[256];                                                                        // 글자 카운트 값을 저장할 곳 초기화
       }

       public void charCount(InputStream in) throws IOException
       {

               int buf = in.read();                                                                        // 한 글자를 읽어서
               while (buf != -1)
               {
                       count[buf]++;                                                                                // 그 글자의 카운트값 1 플러스
                       buf = in.read();
               }

               buildTree();                                                                                        // 카운트를 가지고 트리를 만듬
       }

       private void buildTree()
       {
               nodes = new HuffNode[256];

               Heap heap = new Heap();

               for (int i=0; i<count.length; i++)
                       if (count[i]>0)
                               heap.insert( nodes[i] = new HuffNode(i, count[i], null, null, null) );                // 링크가 없고 data만 가진 node들을 일단 heap에 넣음
               
               heap.insert( nodes[EOF] = new HuffNode(EOF, 1, null, null, null) );                        // EOF도 node로 추가. 카운트가 1이라고 봄

               HuffNode temp1, temp2, p;
               temp1 = (HuffNode) heap.removeMin();                                // heap에서 카운트가 가장 작은 값을 읽어들임.
               while (!heap.isEmpty())                                                                // heap이 비어있을때까지
               {
                       temp2 = (HuffNode) heap.removeMin();                        // 최소값을 한번 더 읽음

                       p = new HuffNode(NOT_A_VALUE, temp1.count + temp2.count, null, temp1, temp2);        // 좌,우 링크를 가지는 새 노드를 만듬.
                       temp1.parent = temp2.parent = p;                                // 두 노드의 parent를 지정
                       heap.insert(p);                                                                        // heap에 새 node를 넣음

                       temp1 = (HuffNode) heap.removeMin();
               }
               root = temp1;                                                                                // 가장 마지막 최소값 node가 root!
       }

       public String getCode(int key)                                                        // key를 주면 code를 뱉음
       {
               HuffNode current = nodes[key];
               if (current == null)                                                                // 해당 node가 없으면 null
                       return null;

               String code = "";
               HuffNode p = current.parent;                                                // 맨 아래 node 부터 위로 올라가면서

               while (p != null)
               {
                       if (p.left == current)                                                        // 왼쪽이면 0
                               code = '0' + code;
                       else if (p.right == current)                                        // 오른쪽이면 1
                               code = '1' + code;
                       current = p;
                       p = current.parent;
               }

               return code;
       }

       public int getKey(String code)
       {
               HuffNode temp = root;                                                                // 맨 위 node 부터
       for(int i = 0; i<code.length(); i++)                                // code 길이만큼 내려가면서
               {
                       if (temp == null)
                               return ERROR;                                                                // 코드가 끝나기 전에 트리가 끝나면 에러
           if (code.charAt(i) == '0')                                                // 0 이면 왼쪽
               temp = temp.left;
           else                                                                                        // 1이면 오른쪽
               temp = temp.right;
       }
               
       return temp.value;  
       }

       public void writeFreq(DataOutputStream out) throws IOException                // 프리퀀시 파일 쓰기
       {
               for (int i=0; i<count.length; i++)
                       if (count[i]>0)                                                        // 카운트가 0 이상인 것만
                       {
                               out.writeByte(i);                                        // 글자값을 byte로 쓰기
                               out.writeInt(count[i]);                                // 그 글자의 count 값을 int(4byte)로 쓰기
                       }
               out.writeByte(0);
               out.writeInt(0);                                                        // 마지막임을 알리기 위해 0 0 을 한번씩 써줌
       }

       public void readFreq(DataInputStream in) throws IOException                        // 프리퀀시 파일 읽기
       {
               byte key = in.readByte();
               int c = in.readInt();                                                // 한 바이트와 인트 씩 읽어서
               while (c != 0)                                                                // 인트가 0일때까지
               {
                       count[key] = c;                                                        // 현재 글자의 카운트 값 저장
                       key = in.readByte();
                       c = in.readInt();
               }

               buildTree();                                                                // 카운트를 근거로 트리를 만듬
       }

       public static int NOT_A_VALUE = -2;
       public static int ERROR = -3;
       public static int EOF = 255;
       private HuffNode root = null;
       private int[] count;
       private HuffNode[] nodes;

       private class HuffNode implements Comparable
       {
               public HuffNode(int v, int c, HuffNode p, HuffNode l, HuffNode r)
               {
                       value = v; count = c; parent = p; left = l; right = r;
               }

               public int compareTo(Object receivedArg)        // 오브젝트끼리 비교하는 함수
           {
                       return count - ((HuffNode)receivedArg).count;
               }

               public int value;
               public int count;
               public HuffNode parent, left, right;
       }
}