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

제 3단계

Codeword 부여하기

각각의 런들에게 실제로 코드워드 부여하는 법

: Huffman 트리의 리프 노드에 위치한 run 들에게 이진 codeword 를 부여할 차례이다.

-리마인드-

Prefix Code

: 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드

(codeword란 하나의 문자에 부여된 이진코드를 말함)

-리마인드 끝-

assignCodeword(prefix, node)

만약에 node가 leaf 이면

    prefix 를 node 에 할당한다. (부여한다)

아니면

    assignCodeword(prefix + '0' , node.left);

    assignCodeword(prefix + '1', node.right);

루트 

루트 자식 왼쪽 - 0 | 루트 자식 오른쪽 - 1

루트 자식 왼쪽의 왼쪽 - 00 | 루트 자식 왼쪽의 오른쪽 - 01 

ㄴ 이런 식으로 자식 위치에 따라서 나의 codeword 에 0  이나 1을 추가한다.

루트 자식 오른쪽의 왼쪽 - 10 | 루트 자식 오른쪽의 오른쪽 - 11 

루트 자식 오른쪽의 오른쪽의 왼쪽 - 110 | 루트 자식 오른쪽의 오른쪽 - 111

ㄴ 이런 식으로 추가하라는 수도 코드임

여기서 prefix를 하나의 32비트 정수로 표현한다 (8비트)

하지만 32비트 중에서 하위 몇 비트만이 실제 부여된 codeword이다.

따라서 codeword의 길이를 따로 유지해야 한다.

class Run implements Comparable<Run>{

    public byte symbol;

    public int runLen;

    public int freq;

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

    //노드에 부여된 코드워드를 저장하기 위한 필드를 아래와 같이 추가한다.

    public int codeword; //부여된 코드워드를 32비트 정수로 저장.

    public int codewordLen; //부여된 코드워드의 길이 - 즉 코드워드의 

                            //하위 코드워드 렝스 비트가 실제 코드워드이다.

}

루트는 코드워드 길이가 nothing 인 거고

루트 - nothting ( = "")

루트 자식 왼쪽 - 0(0000..... 0) | 루트 자식 오른쪽 - 1 (0000......0001) 

이런 식으로 실제 32비트 정수로 저장될 것이다.

요고는 비트 연산으로 코딩해야 할 것인데, 

codeword 구현 할때는 left shift 연산 사용해서 << ← 사용한 뒤에,

0이나 1을 뒤에 붙여주는 식으로 구현해야 함.

0011 1100 을 << 1 하면 0111 1000 으로 한 칸 shift 해서 2배 증가 함

60 -> 120

그래서 0011 1100 을 << 1 + 1 해서 0111 1001 해서 2배 증가 + 1추가 함

↑ 이게 구현하려는 것임 (0 추가 or 1 추가 해서 자식 애들 분기 할 수 있도록 함)

private void assignCodewords (Run p, int codeword, int length){

//assignCodewords(theRoot, 0,0)으로 처음 호출한다.

//codeword는 노드 p에 부여된 codeword

//length는 노드 p에 부여된 codeword의 길이

    

    if(p.left == null && p.right == null){

        p.codeword = codeword;

        p.codewordLen = length;

    }

    else{

        assignCodeword(prefix + '0' , node.left); //이런 식으로 구현 하지는 않음

        assignCodeword(prefix + '1', node.right); //이런 식으로 구현 하지는 않음

        //왼쪽 자식노드에게는 codeword의 뒤에 0을 추가

        //오른쪽 자식노드에게는 1을 추가

    }

}

-------------------------------------------------------------------

public class HuffmanCoding {

    …

    //이렇게 함수로 빼서 사용

     public void compressFile(RandomAccessFile fIn) {

         collectRuns(fIn);

         createHuffmanTree();

         assignCodewords(theRoot, 0, 0);

     }

    static public void main (String args[]) {

        HuffmanCoding app = new HuffmanCoding();

        RandomAccessFile fIn;

        

        try {

            fIn = new RandomAccessFile(“sample.txt”,”r");

             app.compressFile(fIn);

            fIn.close();

        } catch (IOException io) {

            System.err.println("Cannot open " + fileName);

        }

    }

}