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

제 4단계

Codeword 검색하기

인코딩

- 데이터 파일을 압축하기 위해서는 [데이터 파일을 다시 시작부터 읽으면서 run들을 하나씩 인식한 후 ] 해당 run에 부여된 codeword를 검색하다.

- 허프만 트리에서는 모든 run들이 리프노드에 위치하므로 검색하기 불편하다.

- 따라서 검색하기 편리한 구조를 만들어야 한다.

= 런들이 트리 구조로 되어 있어서 AAA라는 run이 어디에 있는지, 어떤 애가 AAA인지 찾는게 상당히 번거롭게 되어 있음. (규칙성이 없어서 불편함)

이제 4단계에서는 tree 구조 필요가 없어서 다른 자료구조 형태로 변경한다.

예전 가이드 : 해시맵 구조로 변경

현재 가이드 : 연결리스트로 변경 (hashing 비슷한 것)

symbol                : A 

codeword            :  0

freg                    : 1

runLen                : 1

codewordLen        : 2 

right                   : 

이런 식으로 되어 있으면 runLen이 1이고 symbol이 A 이므로 A이다.

symbol                : A 

codeword            :  2

freg                    : 2

runLen                : 2

codewordLen        : 2 

right                   : 

이런 식으로 되어 있으면 runLen이 2이고 symbol이 A이므로 AA이다.

이렇게 symbol이 동일한 run 들을 하나의 연결리스트로 저장한다.

각 run의 right 필드는 다음 노드를 가리키는 링크 필드로 사용한다.

한 run에 대해 마지막 노드는 right 값이 null이 된다.

이렇게 동일한 심볼의 run들을 연결 리스트로 만들어서 저장한다.

크기가 256인 chars 라는 연결 리스트 배열을 만들어서 사용한다.

아스키 코드로 A를 변환해서 그 거를 정수형으로 symbol 에 저장하고 하는 식으로 사용한다.

private Run [] chars = new Run [256];

    

     /* Huffman 트리의 모든 리프노드들을 chars에 recursion으로 저장한다 */

     private void storeRunsIntoArray(Run p) {

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

             insertToArray(p);

             // 배열 chars[(unsigned int)p.symbol] 가 가리키는 연결리스트의 맨 앞에 p를 삽입한다.

         }

         else {

             storeRunsIntoArray(p.left);

             storeRunsIntoArray(p.right);

         }

     }

     public void compressFile(RandomAccessFile fIn) {

         collectRuns(fIn);

         createHuffmanTree();

         assignCodewords(theRoot, 0, 0);

         storeRunsIntoArray(theRoot);

     }

Run 검색하기

- symbol과 runLength가 주어질 때 배열 chars 를 검색하여 해당하는 run을 찾아 반환하는 메서드를 작성한다.

public Run findRun(byte symbol, int length){

    //배열 chars에서 (symbol, length)에 해당하는 run을 찾아 반환한다.

}