[알고리즘][압축] 압축(Compression) #4 Huffman Tree에 Codeword 부여

이전글

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

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

 

이전글에서 문자열을 압축하기 위한 Huffman Tree를 생성하였습니다. 이번 글에서는 생성한 Huffman Tree에 Codeword를 부여하도록 하겠습니다.

 

문자열 "AAABAACCAABA"에서 Huffman method with Run-Length Encoding 방식으로 Huffman Tree를 생성했을때 다음과 같이 생성됩니다.

• (C, 2, 1) : (문자열 심볼, 동일한 심볼이 연속된 길이, 빈도수)를 의미합니다. 예를 들어 (C, 2, 1)은 CC 심볼이 1번 등장했다는 의미입니다.
• 리프 노드들의 부모 노드들은 두 자식의 빈도수를 합한 노드입니다. 예를 들어 (A, 2, 2) Run과 (B, 1, 2) 노드의 부모 노드의 빈도수는 합해서 4입니다.

 

1. Codeword 부여하기

• 생성된 Huffman Tree에 대해서 왼쪽 자식일때 0, 오른쪽 자식일때 1을 뒤에 부여함

예를 들어 위 Huffman Tree에 대한 각각의 리프노드의 Codeword는 다음과 같습니다.

2. Codeword 부여 메서드 구현

Codeword 부여 메서드에 대한 핵심 내용은 다음과 같습니다.

	private void assignCodewords(Run p, int codeword, int length) {
		if(p.left == null && p.right == null)
		{
			// 압축하고자 하는 문자가 1개인 경우
			if(p == theRoot)
			{
				p.codeword = 0;
				p.codewordLen = 1;
			}
			else
			{
				p.codeword = codeword;
				p.codewordLen = length;
			}
		}
		else
		{
			// 왼쪽 자식 노드에게는 codeword의 뒤에 0을 추가
			// 오른쪽 자식 노드에게는 codeword의 뒤에 1을 추가			
			assignCodewords(p.left,  codeword << 1, length + 1);
			assignCodewords(p.right, (codeword << 1) + 1, length + 1);
		}
	}

• Huffman Tree의 리프 노드인 경우 해당 노드에 codeword와 길이를 저장
• 리프 노드가 아닌 중간 노드라면 왼쪽과 오른쪽 자식에 대해서 재귀 호출 수행

	public void compressFile(String inFileName, RandomAccessFile fIn) throws IOException{
		
		String outFileName = new String(inFileName+".z"); // 압축 파일 이름 설정
		RandomAccessFile fOut = new RandomAccessFile(outFileName, "rw");
		fOut.setLength(0);
		
		try {
			collectRuns(fIn);                   // step1. Run 객체 수집
			outputFrequencies(fIn, fOut);       // step2. 압축파일 헤더에 Run객체 정보 및 원본파일크기 저장
			createHuffmanTree();                // step3. Huffman Tree 생성 
			assignCodewords(theRoot, 0, 0);     // step4. 각각의 Run 객체에 Codeword 할당
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

1. 문자열에 대한 Run 탐색 및 리스트 배열(runs)에 저장
2. Run 타입 리스트 배열에 대해서 Huffman Tree 생성
3. 루트 노드(theRoot)를 기준으로 Codeword 부여 수행

	@Test
	void compressFileTest() {
		printLine("compressFileTest");
		
		HuffmanCoding app = new HuffmanCoding();
		RandomAccessFile fIn;
		
		try {
			fIn = new RandomAccessFile("sample.txt", "r");
			app.compressFile(fIn);
			fIn.close();
		} catch (FileNotFoundException e) {
			System.out.println("Cannot open sample.txt");
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		app.getRuns().forEach((run)->System.out.println(run));
	}

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

• AAA : codeword=2 => 10 => codewordLen=3 => 010
• B     : codeword=3 => 11 => codewordLen=2 => 11
• AA   : codeword=2 => 10 => codewordLen=2 => 10
• CC   : codeword=0 => 0  => codewordLen=2 => 00
• A    : codeword=3 => 11 => codewordLen=3 => 011

 

References

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