Compression (3)
HuffmanCoding
- Huffman Coding 알고리즘은 트리들의 집합을 유지한다.
- 매 단계마다 가장 빈도가 작은 두 트리를 찾는다.
- 두 트리를 하나로 합친다. 이 때 부모 노드는 두 자식 노드를 합한 값이다.
- 위 연산에 가장 적합한 자료구조는 최소 힙(minimum heap)이다.
- 힙에 저장된 각 원소들은 하나의 트리이다. (노드 또는 런이 아니다.)
최소 힙
위 트리의 각 구성요소들은 전부 트리들이다. (single node tree) 그렇기 때문에 위 트리는 5개의 single node tree가 있다고 할 수 있다.
왼쪽 트리는 개념적인 구조이며 오른쪽 배열은 트리를 실제로 구현한 것이다.
extractMin작업을 하게 될 경우 루트가 항상 가장 작기 때문에 루트를 제거하고 가장 마지막 요소를 루트로 올린다. 그렇게 되면 최소 힙의 구조가 깨지게 되며 이를 복구하기 위해 heapify를 수행한다.
최종 직전의 상태에서 두 트리를 extrctMin하면 잠시 힙이 비게 된다. 이 때 빈 힙에 최종적으로 완성된 허프만 트리를 삽입하여 과정을 완성한다. 완성된 트리의 루트 트리는 theRoot라 칭한다.
class Run 수정
class Run implements Comparable<Run> {
public byte symbol;
public int runLen;
public int freq;
//트리의 노드로 사용하기 위해 왼쪽과 오른쪽 자식 노드 필드를 추가한다.
//두 개의 run간 크기를 비교하는 compareTo 메소드를 overriding한다.
//run간 비교를 수행하는 기준은 freq 변수다.
public int codeword; //32비트의 정수로 저장된 codeword
public int codewordLen; //codewordLen이 실제로 저장된 codeword의 길이가 된다.
}
class Heap<Run>
- 일반적인 Heap클래스 구조를 이용하여 구현한다. Generics로 수정 후 heapify, insert, extractMin 등의 함수를 min heap에 맞게 수정한다.
Huffman Tree 만들기
public class HuffmanCoding {
private ArrayList<Run> runs = new ArrayList<>();
private Heap<Run> heap; //minimun heap을 이용한다.
private Run theRoot = null //완성된 허프만 트리의 루트를 저장하는 변수
private void createHuffmanTree() {
heap = new Heap<Run>();
//1. 모든 run들을 힙에 저장한다.
//2. heap의 크기가 1보다 클 경우 반복한다 (while heap size > 1)
// extractMin연산을 두 번 수행한다.
// extractMin연산을 통해 분리된 트리들을 하나로 결합한 트리를 만든다.
// 결합한 트리를 원래 힙에 합친다.
//3. theRoot변수에 최종적으로 완성된 허프만 트리의 루트를 저장한다.
}
}
print Huffman Tree
private void printHuffmanTree() {
preOrderTraverse(theRoot, 0);
}
private void preOrderTraverse(Run node, int depth) {
for (int i = 0; i < depth; i++)
System.out.println(" ");
if (node == null)
System.out.println("null");
else {
System.out.println(node.toString());
preOrderTraverse(node.left, depth + 1);
preOrderTraverse(node.right, depth + 1);
}
}
Codeword 부여
- Huffman Tree의 리프 노드에 위치한 run들에 binary codeword를 부여한다. 왼쪽 가지는 0으로, 오른쪽 가지는 1로 설정한 후 각 리프 노드들의 codeword를 지정한다.
- prefix를 하나의 32비트 정수로 표현한다. 하지만 32비트 중 하위 몇개의 비트만이 실제로 부여된 codeword가 된다. 따라서 codeword의 길이는 따로 유지해야만 한다.
//assignCodewords(theRoot, 0, 0);을 통해 호출된다.
// codeword변수는 노드 p에 부여된것이며 length를 통해 그 길이를 알 수 있다.
private void assignCodewords(Run p, int codeword, int length) {
if (p.left == null && p.right == null) {
p.codeword = codeword;
p.codewordLen = length;
} else {
assignCodewords(p.left, codeword + '0', length + 1);
assignCodewords(p.right, codeword + '1', length + 1);
}
}
main과 compressFile메소드
public class HuffmanCoding {
~
public void commpressFile(RandomAccessFile fIn) {
collectRuns(fIn);
createHuffmanTree();
assignCodewords(theRoot, 0, 0);
}
public static void main(String[] args) {
HuffmanCoding app = new HuffmanCoding();
RandomAccessFile fIn;
try {
fIn = new RandomAccessFile("sample.txt", "r");
app.compressFile(fIn);
fIn.close();
} catch (IOException e) System.err.println(fileName + "을 열 수 없습니다.");
}
}
비트 연산
public class bit {
public static void main(String[] args) {
int a = 60; // 0011 1100
int b = 13; // 0000 1101
int c = 0;
c = a & b; // 12 = 0000 1100 (and)
c = a | b; // 61 = 0011 1101 (or)
c = a ^ b // 49 = 0011 0001 (xor)
c = ~a; // -61 = 1100 0011 (nor)
c = a << 1 // 120 = 0111 1000 (left shift)
c = (a << 1) + 1; // 121 = 0111 1001
c = a << 2; // 240 = 1111 0000
}
}
