Huffman Coding

2013. 4. 9. 15:47 카테고리 없음

허프만 부호화(Huffman coding)

Information Security/Algorithm

허프만 부호화(Huffman coding)


허프만 부호화는 문자들의 빈도로부터 접두 부호(어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프만 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일하다.


1. 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.

2. 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다.

2.1 목록으로부터 가장 빈도가 낮은 것을 2개 고른다.

2.2 그 다음 허프만이 두가지 기호를 부모 노드를 가지는 부트리를 구성하고 자식노드를 생성한다. 부모 노드 단 기호들의 빈도수를

더하여 주 노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다.

2.3 목록에서 부모노드에 포함된 기호를 제거한다.


허프만 알고리즘은 입력 기호를 잎으로 하는 이진 트리를 만들어서 접두 부호를 만들어 내는 알고리즘이다.


출처: http://ko.wikipedia.org/wiki/허프만_부호화

01 // Huffman_test.java
02  
03 import java.io.*;
04  
05 public class Huffman_test{
06     public static void main(String[] args){
07          
08         String str;
09  
10         try{
11             /* 읽을 파일을 지정해서 열기 */
12             BufferedReader fin = new BufferedReader(new FileReader("test.txt"));
13              
14             System.out.println("____________________________");
15             System.out.println("HUFFMAN CODING");
16             System.out.println("CODE BY DAEGYEONG KIM");
17             System.out.println("FROM DANKOOK UNIVERSITY");
18             System.out.println("____________________________\n");
19  
20  
21             System.out.println("[+] Reading from the file...");
22             str = fin.readLine();
23             System.out.println("[+] The object of Huffman Tree is being made...");
24             Huffman_tree Huff_tree = new Huffman_tree();
25             System.out.println("[+] Alphabets are being counted...");
26             Huff_tree.count_alphabet(str);
27             System.out.println("[+] Each alphabet is being put into heap...");
28             Huff_tree.heapify();
29             System.out.println("\n[+] The counted numbers of alphabets are being treeized..");
30             Huff_tree.treeize();
31             System.out.println("\n[+] The counted numbers of alphabets are being tablized...");
32             Huff_tree.tablize();
33             System.out.println("\n[+] Each alphabet's Huffman code is being generated...");
34             Huff_tree.printTable();
35             System.out.println("\n[+] The input data is being Huffman codized...");
36             System.out.println(Huff_tree.huffmanCodize());
37             System.out.println("\n[+] The program normally exited!");
38  
39             fin.close();        /* 파일 닫기 */
40         }catch(Exception e){
41             System.out.println("\n[-] Fail: " + e);
42         }
43     }
44 }

 
001 /**
002  *  input a alphabet-written file and find out the frequency of each alphabet
003  *  make a Huffman tree(decode free), covert the string in the file to Huffman code
004  * 
005  *  ASCII codes which can be used for the Huffman coding:
006  *  'space'!"#$%^'()*+,-./0123456789:;<">?ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`
007  *  abcdefghijklmnopqrstuvwxyz
008  * 
009  *  Coded by Daegyeong Kim
010  *  Dankook Univ.
011  *  April 28, 2012
012  * 
013  **/
014  
015 // Huffman_tree.java
016  
017 public class Huffman_tree{
018      
019     final int NUM_OF_ASCII = 122;
020     private TreeNode rootNode;      /* 루트 노드 */
021     private MinHeap minHeap;        /* 최소히프 */
022     private String input;           /* 입력 문자열 */
023     Huffman_hashtable [] huffTable = new Huffman_hashtable[NUM_OF_ASCII];   /* 해쉬테이블 */
024  
025     public Huffman_tree(){     
026         minHeap = new MinHeap(NUM_OF_ASCII);            /* 최소히프 객체 생성 */
027          
028         for (int i = 32; i < NUM_OF_ASCII; i++){
029             huffTable[i] = new Huffman_hashtable();     /* one alphabet, one object
030                                                            index = Ascii code
031                                                            1:1 대응을 통하여 해쉬테이블화 */
032         }
033     }
034      
035     public void count_alphabet(String theInput){
036         input = theInput;
037         /* upper case: 65-90, lower case: 97-122, Space: 32 */
038         for (int i = 0; i < input.length(); i++){        /* 입력받은 문자열을 전체에 대하여 */
039             int ascii = (int)input.charAt(i);           /* i에 해당하는 아스키값으로 변환 */
040             huffTable[ascii].count++;                   /* 알파벳 하나하나 count */
041         }
042     }
043      
044     public void heapify(){
045         for (int i = 32; i < NUM_OF_ASCII; i++){
046             if (huffTable[i].count != 0 ){              /* 1개 이상 존재하는 알파벳에 대하여 */
047                 TreeNode newNode = new TreeNode();      /* 새 노드 객체를 만들어서 */
048                 newNode.setElement(huffTable[i].count); /* 객체에 카운트 된 숫자를 넣고 */
049                 newNode.setAscii((char)i);              /* Ascii값을 넣고 */
050                 minHeap.put(newNode);                   /* 객체를 히프에 넣음 */
051             }
052         }
053         System.out.println(minHeap.toString());
054     }
055      
056     private TreeNode choose(){
057         return minHeap.removeMin();                 /* return the minimum element's index */
058     }
059      
060     /* Making a tree */
061     public void treeize(){
062         for (;minHeap.size() > 1;) {                 /* 노드 하나가 남을 때까지 반복 */
063             TreeNode newNode = new TreeNode();
064             newNode.setLeftLink(choose());          /* 제일 작은 수를 뽑아서 왼쪽 자식 */
065             newNode.setRightLink(choose());         /* 그 다음 제일 작은 수를 뽑아서 오른쪽 자식 */
066             newNode.setElement(newNode.getLeftLink().getElement() /* 왼쪽 자식과 */
067                     + newNode.getRightLink().getElement()); /* 오른쪽 자식의 길이를 합산하여 저장 후 */
068             minHeap.put(newNode);                   /* 히프에 넣음 */
069         }
070         rootNode = minHeap.removeMin();             /* 루트 노드를 반환 */
071     }
072      
073     /* Fulfil the table */
074     public void tablize(){
075         for (int i = 32; i < NUM_OF_ASCII; i++){
076             huffTable[i].setAscii(i);               /* 해쉬테이블에 Ascii 값을 채워넣음 */
077         }
078         System.out.print("Preordered Tree is [");
079         preOrderTree(rootNode);                     /* 전위순회하면서 Huffman code를 구함 */
080         System.out.print("]\n");
081     }
082      
083     /* preorder traversal for assign Huffman code */
084     private void preOrderTree(TreeNode currNode){
085         if (currNode == null){
086             return;
087         }
088         if (currNode.getLeftLink() != null){        /* 왼쪽자식이 있으면 왼쪽자식에 "0"을 더함 */
089             currNode.getLeftLink().setHuffmanCode(currNode.getHuffmanCode() + "0");
090         }
091         if (currNode.getRightLink() != null){       /* 오른쪽자식이 있으면 오른쪽자식에 "1"을 더함 */
092             currNode.getRightLink().setHuffmanCode(currNode.getHuffmanCode() + "1");
093         }
094  
095 //      System.out.print(currNode.getAscii());
096         System.out.print(currNode.getElement() + ", ");
097 //      System.out.print(currNode.getHuffmanCode() + " ");
098          
099         if (currNode.getAscii() != 0){          /* 단말노드이면(단말노드에는 ASCII값이 저장되어 있음) */
100             /* 단말노드의 Huffman Code를 해쉬테이블에 저장함 */
101             huffTable[(int)currNode.getAscii()].huffCode = currNode.getHuffmanCode();
102         }
103          
104         preOrderTree(currNode.getLeftLink());   /* 왼쪽 탐색 */
105         preOrderTree(currNode.getRightLink());  /* 오른쪽 탐색 */
106     }
107      
108     /* 해쉬 테이블 출력 */
109     public void printTable(){
110         System.out.println("Ascii  Char   count   Huffman_code");
111         for (int i = 32; i < NUM_OF_ASCII; i++){
112             System.out.println("  " + huffTable[i].ascii + "     "
113                     + huffTable[i].letter + "      "
114                     + huffTable[i].count + "      "
115                     + huffTable[i].huffCode);
116         }
117     }
118      
119     /* 각 알파벳을 Huffman code로 변환 */
120     public StringBuffer huffmanCodize(){
121         StringBuffer sb = new StringBuffer();
122         for (int i = 0; i < input.length(); i++){
123             sb.append(huffTable[(int)input.charAt(i)].huffCode);
124         }
125         return sb;
126     }
127 }


 
01 // Huffman_hashtable.java
02  
03 public class Huffman_hashtable{
04     public char letter;             /* character for the Ascii code */
05     public int ascii;               /* Ascii code */
06     public int count;               /* frequency */
07     public StringBuffer huffCode;   /* huffman code */
08      
09     public Huffman_hashtable(){
10         count = 0;
11         huffCode = new StringBuffer();
12     }
13      
14     public void setAscii(int theAscii){
15         ascii = theAscii;
16         letter = (char)theAscii;
17     }
18 }


 
001 // MinHeap.java
002  
003 /* import utilities.ChangeArrayLength ; */
004  
005 public class MinHeap{
006     /* data members */
007     TreeNode [] heap;   /* array for complete binary tree */
008     int size;           /* number of elements in heap */
009  
010     /** create a heap with the given initial capacity
011      * @throws IllegalArgumentException when
012      * initialCapacity < 1 */
013     /* constructors : 초기 크기를 매개변수로 넘겨줌 */
014     public MinHeap(int initialCapacity){
015         if (initialCapacity < 1){
016             throw new IllegalArgumentException
017             ("initialCapacity must be >= 1");
018         }
019         /* 인덱스 0를 사용하지 않기 위해서 "+1" */
020         heap = new TreeNode [initialCapacity + 1];
021         size = 0;
022     }
023  
024     /** create a heap with initial capacity 10 */
025     public MinHeap()
026     {this(10);}
027  
028     /* methods */
029     /** @return true iff the heap is empty */
030     public boolean isEmpty()
031     {return size == 0;}
032  
033     /** @return number of elements in the heap */
034     public int size()
035     {return size;}
036  
037     /** @return maximum element
038      * @return null if the heap is empty */
039     /* 빈 배열일 경우 null, if not, 인덱스 1의 원소를 반환 */
040     public TreeNode getMin(){
041         return (size == 0) ? null : heap[1];
042     }
043  
044     /** put theElement into the heap */
045     public void put(TreeNode treeNode){
046         /* increase array size if necessary
047               오류 처리 후 종료 */
048         if (size == heap.length - 1)
049             System.out.println("Heap is full. No insertion.");
050         /*  동적으로 2배 크기만큼 할당하여 기존 것을 copy하여 삽입 수행
051             heap = (TreeNode []) ChangeArrayLength.changeLength1D
052                                                 (heap, 2 * heap.length); */
053         else{
054             /* find place for theElement
055                currentNode starts at new leaf and moves up tree */
056             int currentNode = ++size;
057             while (currentNode != 1 &&
058                     /* 부모와 삽입할 노드를 비교하여  */
059                     heap[currentNode / 2].getElement() > treeNode.getElement())
060             {
061                 /* cannot put theElement in heap[currentNode] */
062                 heap[currentNode] = heap[currentNode / 2]; /* move element down */
063                 /* 부모를 자식노드로 옮김 */
064                 currentNode /= 2;                          /* move to parent */
065             }
066  
067             /* 부모노드보다 크다면 그 자리에 삽입 */
068             heap[currentNode] = treeNode;
069         }
070     }
071  
072     /** remove max element and return it */
073     public TreeNode removeMin(){
074         /* if heap is empty return null */
075         if (size == 0) return null;       /* heap empty */
076  
077         /* 나중에 리턴할 값 */
078         TreeNode minElement = heap[1];  /* max element */
079  
080         /* 마지막에 있는 노드를 삭제하고 루트에 임시로 넣음 */
081         /* reheapify */
082         TreeNode lastElement = heap[size--];
083  
084         /* find place for lastElement starting at root */
085         int currentNode = 1,
086         child = 2;     /* child of currentNode */
087         while (child <= size){
088             /* heap[child] should be smaller child of currentNode */
089             if (child < size && (heap[child].getElement() > heap[child + 1].getElement()))
090                 child++;
091  
092             /* can we put lastElement in heap[currentNode]? */
093             if (lastElement.getElement() <= heap[child].getElement())
094                 break;   /* yes */
095  
096             /* no */
097             heap[currentNode] = heap[child]; /* move child up */
098             currentNode = child;             /* move down a level */
099             child *= 2;
100         }
101         heap[currentNode] = lastElement;
102  
103         return minElement;
104     }
105  
106     /* 힙의 내용을 모두 출력 */
107     public String toString(){
108         StringBuffer s = new StringBuffer();
109         s.append("The " + size + "-element minHeap has [");
110         if (size > 0)
111         {/* nonempty heap */
112             /* do first element */
113             s.append(heap[1].getElement());
114             /* do remaining elements */
115             for (int i = 2; i <= size; i++){
116                 s.append(", " + heap[i].getElement());
117             }
118         }
119         s.append("]");
120  
121         return new String(s);
122     }
123 }


 
01 // TreeNode.java
02  
03 public class TreeNode
04 {
05     private int element;
06     private TreeNode leftLink;          /* left subtree */
07     private TreeNode rightLink;         /* right subtree */
08     private char ascii;                 /* leaf node has its own Ascii code */
09     private StringBuffer huffmanCode;   /* Huffman code */
10      
11     /* constructors */
12     public TreeNode(){
13         huffmanCode = new StringBuffer();
14     }
15  
16     public TreeNode(int theElement){
17         element = theElement;
18         huffmanCode = new StringBuffer();
19     }
20  
21     public TreeNode(int theElement,
22                     TreeNode theleftLink,
23                     TreeNode therightLink)
24     {
25         element = theElement;
26         leftLink = theleftLink;
27         rightLink = therightLink;
28         huffmanCode = new StringBuffer();
29     }
30  
31     /* accessor methods */
32     public TreeNode getLeftLink(){
33         return leftLink;
34     }
35     public TreeNode getRightLink(){
36         return rightLink;
37     }
38     public int getElement(){
39         return element;
40     }
41     public char getAscii(){
42         return ascii;
43     }
44     public StringBuffer getHuffmanCode(){
45         return huffmanCode;
46     }
47  
48     /* mutator methods */
49     public void setLeftLink(TreeNode theLeftLink){
50         leftLink = theLeftLink;
51     }
52     public void setRightLink(TreeNode theRightLink){
53         rightLink = theRightLink;
54     }
55     public void setElement(int theElement){
56         element = theElement;
57     }
58     public void setAscii(char theAscii){
59         ascii = theAscii;
60     }
61     public void setHuffmanCode(String code){
62         huffmanCode.append(code);
63     }
64 }

 

출처 : http://tyche87.tistory.com/208 

저작자표시 비영리 동일조건
posted by townone

티스토리툴바