압축 (2)

Compression (2)

Huffman Method with Run-Length Encoding

- Huffman과 Run-Length를 적절히 결합한 알고리즘이다.

- 파일을 구성하는 각 런들을 하나의 super-symbol로 본다. 그 후 이들에 대해 Huffman Coding을 적용하게 된다.

- Ex) 문자열 AAABAACCAABA는 5개의 super-symbol인 AAA, B, AA, CC, A로 구성된다.

위 그림은 각 슈퍼 심볼의 빈도와 길이를 표시한 테이블이다.

Run과 Frequency 찾기

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

- 각 런들을 표현할 하나의 class Run을 우선 정의한다. 클래스 run은 적어도 세개의 데이터 맴버인 symbol, runLen, freq는 가져야만 한다. 이때 symbol은 byte타입이며 나머지는 정수 타입을 가진다.

- 인식한 런들은 하나의 ArrayList에 차례로 저장한다.

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

- 데이터 파일을 적어도 두 번 읽어야 한다. 한 번은 런들을 찾기 위해, 다음은 실제 압축을 수행하기 위해서이다.

- RandomAccessFile을 이용하여 데이터 파일을 읽는 예시

RandomAccessFile fIn = new RandomAccessFile(fileName, "r"); //읽을 데이터 파일을 연다.

int ch = fIn.read(); //한 바이트를 읽어오며 이는 0~255사이의 정수로 반환된다. 파일의 끝에 도달하면 -1을 반환한다.

byte symbol = (byte)ch; //symbol이 필요하다면 byte로 캐스팅해 저장한다.

- 코드 구현

class Run {
    public byte symbol;
    public int runLen;
    public int freq;
    //적절한 생성자와 equals메소드를 작성하는 부분
}
public class HuffmanCoding {
    //인식한 run들을 저장할 ArrayList
    private ArrayList<Run> runs = new ArrayList<>();
    private void collectRuns(RandomAccessFile fIn) throws IOException {
        //데이터 파일인 fIn에 있는 모든 fun들과 각각의 등장횟수를 세 runs에 저장
    }
    public static void main(String[] args) {
        HuffmanCoding app = new HuffmanCoding();
        RandomAccessFile fIn;
        try {
            fIn = new RandomAccessFile("sample.txt", "r");
            app.collectRuns(fIn);
            fIn.close();
        } catch (IOException e) {
            System.err.println(fileName + "을 열 수 없습니다.");
        }
    }
}

Run 인식하기

- AAABBCAAB...가 주어졌다 하자.

1) 파일의 첫 바이트를 읽고 이를 start_symbol이라 한다. (제일 처음 A)

2) 파일의 끝에 도달하거나 start_symbol과 다른 바이트가 나올 때까지 연속해서 읽는다. 현재까지 읽은 바이트 수를 count라고 할때 위 에시에서 start_symbol과 다른 바이트가 나왔을 때의 count는 4인 상태이다. (처음 B가 나온 시점)

3) (start_symbol, count - 1)인 run이 하나 인식된다. 이 run을 저장한 후 가장 마지막에 읽은 바이트(B가 된다.)를 start_symbol로, count는 1로 초기화한 후 다시 2번 과정을 반복한다.