제 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);
}
}
}
댓글
댓글 쓰기