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

Huffman Method with Run-Length Encoding

무손실 압축 알고리즘을 하이브리드로 이용해서 구현을 해 본다고 한다.

 

- 파일을 구성하는 각각의 run 들을 하나의 super-symbol로 본다.

이 super-symbol에 대해서 허프만 코딩을 적용한다.

예를 들어 AABAACCAABA는 AAA B AA CC AA 로 구성되며

등장 회수는 1 1 1 2 2 와 같다.

A3 - 1

C2 - 1

A1 - 1

B1 - 2

A2 - 2

이 파일에 등장하는 run 들에게 이진 코드를 부여해서 동작시킨다.

A3 - 110

C2 - 10

A1 - 00

B1 - 01

A2 - 111

로 run에 대해서 이진 코드를 부여하면

AAABAACCAABA는 110 01 10 111 10 01 00 으로 인코딩 된다

1100110111100100 <-

이거 이진 트리로 변경 하면 접두사가 겹치지 않는 트리를 제작 가능

* Run과 frequncy 찾기

- 압축할 파일을 처음부터 끝까지 읽어서 파일을 구성하는 run 들과 각 run 들의 등장횟수를 구한다.

- 먼저 각 run들을 표현할 하나의 클래스 class run을 정의한다.

클래스 런은 적어도 세개의 데이터 멤버 symbol, runLen, freq를 가져야 한다.

symbol만 byte고 다른 것은 다 정수이다.

- 인식한 run 들은 하나의 ArrayList에 저장한다.

- 적절한 생성자와 equals 메소드를 구현한다.

symbol : run이 가지고 있는 단자? (AAA 면 A가 symbol이다)

runlen : 길이

freq : 빈도

class Run{

    byte symbol;

    int runlen;

    int freq;

}

요러면 데이터 파일을 적어도 두번은 읽어야 한다.

1) run 찾기

2) 실제 압축 수행

RandomAccessFile을 이용해서 데이터 파일을 읽어본다고 한다.

[RandomAccessFile]

 원래 스트림은 원칙적으로 순서대로 처리되지만

 예외적으로 접근처리를 할수있게 하는 입출력스트림이다.

 말그대로 임의로 파일에 접근할수 있게 한다. 

 다른 스트림과다르게 INPUT OUTPUT을 상속하지 않고

 바로 Object를 상속받는다. 

= 스캐너 클래스처럼 쓰면 되나 부다.

출처: https://ddo-o.tistory.com/40 [공순이의 블로그]

//읽을 데이터 파일을 연다

RandomAccessFile fin = new RandomAccessFile(fileName, "r");

//한 바이트를 읽어 오면, 읽어온 바이트는 0~255사이의 정수로 반환된다.

// EOF면 -1을 반환한다.

int ch = fin.read();

//필요시에는 byte로 캐스팅해서 저장한다.

byte symbol = (byte) ch;

* Run 인식하기

1. 파일의 첫 바이트를 읽으면 이것을 start_symbol이라고 한다.

2. 파일의 끝에 도달하거나 start_symbol과 다른 byte가 나올 때까지 연속해서 읽는다.

AAABBCAAB <- 일 경우에는 A가 끝나는 시점이 B - 현재까지 읽은 바이트 수를 count 라고 한다.

요기서는 지금 byte가 4이다.

AAA B <- 4

3. start_symbol , count-1 인 run이 하나 인식 되면

이 run을 저장하고, 가장 마지막에 읽은 byte를 start_symbol로, count = 1로 reset 하고 다시 반복한다.

고롬 AAA[B]BCAAB 니까 BB C <- 면 byte가 6이 되고 다시 3으로 돌아가서 진행한다.

* Run과 frequency 찾기

class Run{

    public byte symbol;

    public int runLen;

    public int freq;

    //추가적으로 생성자랑 equals 메소드를 완성해야 한다. - symbol하고 runlen 위한 것

}

public class HuffmanCoding{

//인식한 런들을 저장할 어레이리스트를 만든다.

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

    private void collectRuns(RandomAccessFile fin) throws IOExcetpion{

        데이터 파일 fin에 등장하는 모든 run들과 각각의 등장횟수를 count해서 

        어레이리스트 runs에 저장한다.

        

    }

}

main(){

    HuffmanCoding app = new HuffmanCoding();

    RandomAccessFile fin;

    

    try{

        fin = new RandomAccessFile(파일, "r");

        app.collectRuns(fin);

        fin.close();

    }catch(){

        에러 발생시 출력

    }

}

* C 구현체도 있는데

요것도 데이터 파일 fin에 등장하는 모든 run들과 각각 등장횟수를 카운트해서 배열 runs에 저장하고

Run 객체를 동적메모리 할당<-으로 생성하여 배열 runs에서 객체 주소를 저장한 뒤에

배열 크기가 부족할 경우에만 array doubling 을 하도록 하면 된다.