[OOP_Lab5] Huffman coding (recursive methods) - 1편

Huffman coding에 대해 글을 찾아보았지만 너무 어려우므로 수업 시간에서 다룬 대로만 남겨보려고 한다. 어짜피 recursive function이 헷갈려서 쓰는 글이라 Huffman coding이 중요한 부분이 아니기 때문에 그냥 넘어가야겠다.

 

수업에서 교수님이 말씀하셨던 것처럼 recursive function은 magical 하다..!

우리나라 말로 재귀 함수라고 말하는 것 같은데 정말 생소한 개념이다.

가만히 듣다 보면 무슨 소린지 알겠는데 나보고 직접 짜라고 하면 절대 생각해내지 못할 것 같다.

 

수업 시간 내내 '우와...'하면서 쳐다보다가 뭔가 이해 가는 것 같다가도 이해가 안가서 글을 써본다.

---

What is Huffman Tree?

• Suppose that our alphabet has four letters: A, B, C, D.
• Suppose that we also know that A: 45%, B:35%, C:20%, D:5% (단순 가정)
• We can encode them as:
  • A: 0
  • B: 10
  • C: 110
  • D: 111
• This requires on average 1.7 bits per letter, as opposed to 2 (=세자리 수로 모두 구성하는 것보단 낫다..!)

Class Materials: Lab5

---

Huffman Trees

• The key to this algorithm is the construction of a Huffman tree.
• This is a binary tree with:
  • Letters at the leaves
  • The edges represent the 0 or 1 in the code.
  • Each node contains a frequency.

Picture of Huffman Tree

Class Materials: Lab5

---

Let's Build a Tree !

public class Huffman {
	public void buildTree() {
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        getLetterFrequencies();

        double total = 0;
        /* Step 1 */
        for (String key : letterCounts.keySet()) {
            total += letterCounts.get(key);
        }

        /* Step 2 */
        for (String key : letterCounts.keySet()) {
            queue.add(new Node(key, letterCounts.get(key) / total));
        }

        /* Step 3 */
        while ( queue.size() > 1 ){
            Node n1 = queue.remove();
            Node n2 = queue.remove();

            Node newNode = new Node("", n1.getFrequency() + n2.getFrequency());
            newNode.setLeftChild(n2);
            newNode.setRightChild(n1);
            queue.add(newNode);
        }

        huffmanTree = new BinaryTree(queue.poll());
    }
}

• Tree 를 만들 때 우선적으로 frequency를 고려해야한다. 단어가 자주 나타날수록 트리 상단에 존재해야하기 때문(타고타고타고 X)
• Step1: Input File 기반으로 frequency를 얻는다. frequency = 단어 등장 수 / 모든 단어 수 
• Step2: Node를 만들어서 PriorityQueue queue에 넣는다. 이때 Node.java 가 implements Comparable<Node>이기 때문에 자동적으로 frequency가 낮은 것을 앞에, 높은 것을 뒤에 넣는다.
• Step3: queue 사이즈가 1이 될 때 까지 (노드가 모두 트리 형태로 될 때 까지) 아래를 반복한다.
  • n1: 가장 앞에 있는 노드 빼냄(remove)
  • n2: 그 다음 노드 빼냄(remove)
  • newNode: 새로운 노드 생성 with n1.frequency + n2.frequency (위에 사진에서 C, D가 합인 0.25가 제일 먼저 만들어짐)
  • newNode.setLeftChild(n2): n1 이랑 n2 중에 더 큰 값인 n2을 leftChild로 셋팅(e.g. C가 제일 먼저 셋팅)
  • newNode.setRightChild(n1): n1이랑 n2 중에 더 작은 값인 n1을 rightChild로 셋팅(e.g. D가 제일 먼저 셋팅)
  • queue.add(newNode): 두 개 노드 빼내고 새로 생성된 하나를 집어넣음. 다른 값들 보다 작으므로 제일 앞에 들어감(comparable~)
  • D, C, B, A → new(CD), B, A → new(B-CD), A → new(A-B-CD) 이렇게 줄어들다가 queue.size()가 1이 되면 while문이 멈춘다.
• 그렇게 만들어진 queue를 queue.poll()해서 huffmanTree에 할당하면 사진과 같이 트리가 만들어진다!

---

Let's build code for every letter!

Huffman.java

public class Huffman {
    public BinaryTree huffmanTree;
    public Map<String, String> codes;

    public void getCodes() {
        if (huffmanTree.root == null) {
            return;
        } else {
            huffmanTree.root.buildCodes(codes);
        }
    }
}

• BinaryTree huffmanTree는 우선 Node로 구성되어 있다(위에서 트리 만든거 보면 알 수 있음).
• 제일 꼭대기(root)가 null이면 그냥 리턴. 트리가 걍 없는 것임
• buildCodes(codes)를 가지고서 생성하러 가보자. codes 는 코드를 만들어서 문자, 코드를 담아줄 딕셔너리라고 보면 된다. 예를 들어 <"A":"01">이런 식으로 담아줄 딕셔너리다.

---

Node.java

public class Node implements Comparable<Node> {
    protected String data; // letter itself
    protected double frequency;
    protected Node   leftChild;
    protected Node   rightChild;
    
    // 1번 
    public void buildCodes(Map<String, String> codes) {
        buildCodes(codes, "");
    }

    // 2번 - Overloading
    public void buildCodes(Map<String, String> codes, String codeSoFar) {
        if ( isLeaf() ){
            codes.put( this.data, codeSoFar);
        }else{
            leftChild.buildCodes( codes, codeSoFar + "0");
            rightChild.buildCodes( codes, codeSoFar + "1");
        }
    }
}

• 가장 먼저 huffman.root.buildCodes(codes)를 통해서 1번 buildCodes()가 호출된다.
• 딕셔너리를 가지고서 다시 오버로딩된 2번 buildCodes()를 호출한다.
• 만약에 이 노드가 isLeaf()
  • 딕셔너리에 this.data(알파벳)과 이때까지 쌓은 코드(codeSoFar)를 저장한다.
• isLeaf()가 아니면?
  • leftChild 보고 buildCodes하라고(니가 해) 명령하고 지금까지의 코드(codeSoFar)에 "0"을 더해준다.
  • rightChild 보고 buildCodes하라고(니가 해) 명령하고 지금까지의 코드(codeSoFar)에 "1"을 더해준다.

첫 번째 recursive

두 번째 recursive

세 번째 recursive

마지막 recursive

---

그 결과

@Test
void getCodes() {
    huffman.buildTree();
    huffman.getCodes();
    for (String key : huffman.codes.keySet()) {
        System.out.printf("%s %s\n", key, huffman.codes.get(key));
    }
}

이렇게 테스트를 돌리면 

7 10100001101101
8 01101000111010
9 0011011110110
: 110100100111
; 1010000110101
= 0110100011101101110
? 110100100101
A 011010000
B 101000000
C 1010000011
D 1010001010
...
J 10100010110
K 001101111010
L 1010000010

이런 식으로 codes 딕셔너리가 구성되어 있는 것을 알 수 있다.

---

encode()와 decode()가 이해가 되지 않아 시작한 글인데 아직 시작도 못했다.

다음 편으로 나누어서 작성해보아야 겠다.