[알고리즘][압축] 압축(Compression) #3 Huffman Tree 생성

이전글

https://yonghwankim-dev.tistory.com/306

[알고리즘][압축] 압축(Compression) #2 Huffman Method with Run-Length Encoding

 

이전글에서 문자열 "AAABAACCAABA"에서 Run을 탐색하고 배열 리스트 runs에 저장하였습니다. 배열 리스트 runs에 Run들은 다음과 같이 저장되었습니다.

0 : Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=, codewordLen=0]
1 : Run [symbol=66, runLen=1, freq=2, left=null, right=null, codeword=, codewordLen=0]
2 : Run [symbol=65, runLen=2, freq=2, left=null, right=null, codeword=, codewordLen=0]
3 : Run [symbol=67, runLen=2, freq=1, left=null, right=null, codeword=, codewordLen=0]
4 : Run [symbol=65, runLen=1, freq=1, left=null, right=null, codeword=, codewordLen=0]

 

1. Huffman Tree 생성

Huffman Tree의 생성과정은 다음과 같습니다.

1. 최소 힙으로 runs 배열 리스트에 있는 모든 run 객체들을 넣음 (run 객체의 frequency를 가지고 대소를 비교함)
2. 최소 힙에서 run 두개를 추출함
3. 추출한 두 run 노드를 자식으로 두는 하나의 이진 트리로 생성함 (부모 노드는 두 자식의 frequency를 합한 노드)
4. 생성한 이진 트리를 최소힙에 다시 넣음
5. 2~4번 과정을 최소힙의 크기가 1이 될때까지 반복함
6. Run 타입의 theRoot 변수가 최소 힙의 루트를 가리킴

위의 Huffman Tree의 생성과정을 그림으로 표현하면 다음과 같습니다.

2. createHuffmanTree 메서드 구현

public class HuffmanCoding {
	private ArrayList<Run> runs = new ArrayList<Run>();
	private Heap<Run> heap;		// min heap
	private Run theRoot = null;	// 허프만 트리의 루트
   
	void createHuffmanTree() {
		heap = new Heap<Run>(256);
		
		// 1. 힙으로 모든 run 객체들을 저장
		runs.stream().forEach((run)->heap.add(run));
				
		// 2. heap의 크기가 1이 될때까지 반복문 수행
		while(heap.size() > 1)
		{
			// 2.1 heap에서 run을 두개 추출
			Run first = heap.remove();
			Run second = heap.remove();
			
			// 2.2 두개의 run을 하나의 이진 트리로 생성
			Run tree = makeBinaryTree(first, second);

			// 2.3 생성한 이진 트리를 heap에 넣음
			heap.add(tree);
		}
		
		// 3. theRoot는 heap의 루트를 가리킴
		theRoot = heap.getMin();
	}
    
    	// first, seocnd run 객체를 자식으로 두는 이진 트리를 생성함
	private Run makeBinaryTree(Run first, Run second) {
		Run tree = new Run((byte) 0, 0, first.freq + second.freq);
		
		tree.left = first;
		tree.right = second;
		
		return tree;
	}

	void printHuffmanTree() {
		preOrderTraverse(theRoot, 0);
	}
	
	private void preOrderTraverse(Run node, int depth) {
		for(int i=0; i<depth; i++)
		{
			System.out.print(" ");
		}
		
		if(node == null)
		{
			System.out.println("null");
		}
		else
		{
			System.out.println(node.toString());
			preOrderTraverse(node.left, depth + 1);
			preOrderTraverse(node.right, depth + 1);
		}
	}

	@Test
	void createHuffmanTreeTest() {
		HuffmanCoding app = new HuffmanCoding();
		RandomAccessFile fIn;
		String fileName = "sample.txt";
		ArrayList<Run> runs = app.getRuns();
		
		// 1. Run 탐색
		try {
			fIn = new RandomAccessFile("sample.txt", "r");
			app.collectRuns(fIn);
			fIn.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		// 2. HuffmanTree 생성
		app.createHuffmanTree();
		
		// 3. HuffmanTree 출력
		app.printHuffmanTree();
	}

실행 결과
Run [symbol=0, runLen=0, freq=7, left=Run [symbol=0, runLen=0, freq=3, left=Run [symbol=67, runLen=2, freq=1, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=0, runLen=0, freq=2, left=Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=65, runLen=1, freq=1, left=null, right=null, codeword=0, codewordLen=0], codeword=0, codewordLen=0], codeword=0, codewordLen=0], right=Run [symbol=0, runLen=0, freq=4, left=Run [symbol=65, runLen=2, freq=2, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=66, runLen=1, freq=2, left=null, right=null, codeword=0, codewordLen=0], codeword=0, codewordLen=0], codeword=0, codewordLen=0]
 Run [symbol=0, runLen=0, freq=3, left=Run [symbol=67, runLen=2, freq=1, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=0, runLen=0, freq=2, left=Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=65, runLen=1, freq=1, left=null, right=null, codeword=0, codewordLen=0], codeword=0, codewordLen=0], codeword=0, codewordLen=0]
  Run [symbol=67, runLen=2, freq=1, left=null, right=null, codeword=0, codewordLen=0]
   null
   null
  Run [symbol=0, runLen=0, freq=2, left=Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=65, runLen=1, freq=1, left=null, right=null, codeword=0, codewordLen=0], codeword=0, codewordLen=0]
   Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=0, codewordLen=0]
    null
    null
   Run [symbol=65, runLen=1, freq=1, left=null, right=null, codeword=0, codewordLen=0]
    null
    null
 Run [symbol=0, runLen=0, freq=4, left=Run [symbol=65, runLen=2, freq=2, left=null, right=null, codeword=0, codewordLen=0], right=Run [symbol=66, runLen=1, freq=2, left=null, right=null, codeword=0, codewordLen=0], codeword=0, codewordLen=0]
  Run [symbol=65, runLen=2, freq=2, left=null, right=null, codeword=0, codewordLen=0]
   null
   null
  Run [symbol=66, runLen=1, freq=2, left=null, right=null, codeword=0, codewordLen=0]
   null
   null

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/compression
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌