개발 공부 - [Huffman Coding] 압축 (Compression) - 3

제 2단계

Huffman Tree

Huffman coding 알고리즘은 [트리들의 집합]을 유지하면서

매 단계에서 가장 프리퀀시가 작은 두 트리를 찾아서

두 트리를 하나로 합친다.

이런 연산에 가장 적합한 자료구조는 최소 힙이다. (우선순위큐!)

즉 힙에 저장된 각각의 원소들은 하나의 트리이다. (노드가 아니라)

ㄴ 런 객체들이 모여서 만들어지는 트리이다.

ㄴ extractMin (힙 안의 최소값을 꺼내 주는 것) 

ㄴ insert (넣기)

이 기능을 지원하도록 만들 것

최소 힙

- 크기가 5인 힙

- 5개의 트리가 저장되어 있다

- 각 트리는 오직 하나의 노드로 구성되어 있다.

 heap

0 : A3 1(프리퀀시 값)

1 : C2 1

2 : A1 1

3 : B1 2

4 : A2 2

이렇게 각각의 런을 싱글 노드 트리라고 보면 되고,

각 트리가 노드 하나짜리 트리이다.

min heap은 컴플릿 바이너리 트리 + 힙 프로퍼티를 만족해야 함

부모는 자식보다 작거나 같다 - frequency 값으로 보는 것

A3 1 - C2 1 / A1 1

C2 1 - B1 2 / A2 2 

트리 모양은 이런 구조로 되어 있음

힙을 이진 트리 모양으로 만들기는 하는데, 프로그램 상에서는 그냥 1차원 배열 힙으로 만들면 되는 거라서 

 heap

0 : A3 1(프리퀀시 값)

1 : C2 1

2 : A1 1

3 : B1 2

4 : A2 2

이런 식으로 삽입 하면 된다.

일단 최소 힙 만들기 위해 힙을 만들어서 extreactMin을 두번 반복하고 insert를 하면 

공백 7 (루트 - the Root 라고 부름)

공백 4  - 차일드 2 

    A2 2

    B1 2

공백 3  - 차일드 2 

    C2 1

    공백 2 - 차일드 2

        A3 1

        A1 1

이런 허프만 트리를 조성할 수 있다.

class Run implements Comparable<Run>{

    public byte symbol;

    public int runLen;

    public int freq;

    //트리의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.

    //두 run의 크기관계를 비교하는 compareTo 메소드를 오버라이딩 하라

    // 비교의 기준은 freq이다.

}

힙은 3장에서 작성한 Heap 클래스를 가져와서 사용하고,

Generics로 수정하고, heapify, insert, extractMin 등의 함수를 min heap에 맞게 수정한다.

public class HuffmanCoding{

    private ArrayList<Run> runs = new ArrayList<Run>();

    private Heap <Run> heap; //min heap 이다.

    private Run theRoot = null; //허프만트리 루트이다.

    

    private void createHuffmanTree(){

        heap = new Heap<Run>();

        //일단 힙을 하나 생성하고

        // 모든 런들을 힙에다가 집어넣고 (insert)

        // 힙 사이즈가 1이 될 때까지 

        // 힙에서 extractMin을 2번 해서 2번 min 값을 꺼내고

        // 두개의 트리를 합쳐서 하나의 트리로 만들고

        // 도로 트리를 힙에다가 넣어주면

        // 마지막에 남아있는 애를 theRoot로 root로 지정해 주면 끝

        

    }

    

    private void collectRuns(RandomAccessFile fin) throws IOExcetpion{

        ...

    }

}

코드는 그냥 출력용으로만 하나의 트리 보여주기 용으로 맨들어 줬는데

소스 짜 봐야 할 듯.