[알고리즘][압축] 압축(Compression) #5 codeword 검색하기

Huffman Coding의 단계

1. 문자열을 읽어서 Run 객체 생성 및 저장 (collectRuns 메서드)
2. Run 타입의 리스트를 활용한 Huffman Tree 생성 (createHuffmanTree 메서드)
3. Huffman Tree 리프노드에 codeword 할당 (assignCodewords 메서드)
4. Huffman Tree 리프노드들을 체이닝 구조의 배열에 저장 (storeRunsIntoArray, 현재 구현해야하는 단계)
5. 파일 압축 (encode 메서드)

1. Huffman Tree의 리프노드들을 체이닝 구조의 배열에 저장 필요성

데이터 파일을 압축하기 위해서는 데이터 파일을 다시 시작부터 읽으면서 run을 하나씩 인식한 후 해당 run에 부여된 codeword를 검색해야 합니다.

 

Huffman Tree에는 모든 run들이 다음과 같이 리프노드에 위치하므로 검색하기가 불편합니다.

따라서 리프노드들을 검색하기 쉬운 편리한 구조를 생성해야 합니다. 이에 대한 해결안으로 체이닝 구조의 배열을 사용하면 해결할 수 있습니다.

 

2. 체이닝 구조의 배열은 어떻게 구성되어 있는가?

체이닝 구조의 배열은 Array of Linked Lists로써 각각의 원소가 Linked List이고 이러한 원소들이 배열을 이루는 구조입니다. 그림으로 표현하면 다음과 같습니다.

• chars 배열의 크기가 256인 이유 : 아스키 코드 문자의 수 범위가 0~255사이이기 때문
• Run타입 리프노드 객체의 right 필드 용도 : 같은 심볼을 가지는 Run 객체를 가리키는 용도, 이는 탐색의 속도를 증가시킴

 

3. storeRunsIntoArray 메서드 구현

public class HuffmanCoding {
	private ArrayList<Run> runs;
	private Heap<Run> heap;		// min heap
	private Run theRoot;	// 허프만 트리의 루트
	private List<Run>[] chars;
	private long sizeOriginalFile;	// 원본파일의 길이

	public HuffmanCoding() {
		runs = new ArrayList<Run>();
		chars = new List[256];	// 아스키 코드 0~255에 대한 배열
		
		for(int i=0; i<chars.length; i++)
		{
			chars[i] = new LinkedList<Run>();
		}
	}
	...

	private void storeRunsIntoArray(Run p) {
		if(p.left == null && p.right == null)
		{
			// 배열 chars[(unsigned int) p.symbol]가 가리키는
			// 연결리스트의 맨 앞에 p를 삽입
			insertToArray(p);
		}
		else
		{
			storeRunsIntoArray(p.left);
			storeRunsIntoArray(p.right);
		}
	}

	private void insertToArray(Run p) {
		List<Run> run_list = chars[Integer.parseUnsignedInt(String.valueOf(p.symbol))];
		Run prev_run;
		
		if(!run_list.isEmpty())
		{
			prev_run = run_list.get(0);
			p.right = prev_run;
		}
		run_list.add(0, p);
	}

	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 할당
			storeRunsIntoArray(theRoot);		// step4. 각각의 Run 객체들 배열에 저장
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	@Test
	@Order(4)
	@DisplayName("storeRunsIntoArray 메서드 테스트")
	void storeRunsIntoArrayTest() {
		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();
		}
		
		List<Run>[] chars = app.getChars();
		
		for(List<Run> run_list : chars)
		{
			if(run_list.isEmpty())
			{
				continue;
			}
			
			for(Run run : run_list)
			{
				System.out.print(run + " ");			
			}
			System.out.println();
		}
	}

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=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] 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=67, runLen=2, freq=1, left=null, right=null, codeword=0, codewordLen=2]

 

4. findRun 메서드 구현

symbol과 runLength가 주어질 때 배열 chars를 검색하여 해당하는 run을 찾아 반환하는 메서드입니다.

	/**
	 * 배열 chars에서 (symbol, length)에 해당하는 run을 찾아 반환
	 * @param symbol 문자의 바이트형
	 * @param length runLength
	 * @return run 객체
	 */
	public Run findRun(byte symbol, int length)
	{
		List<Run> run_list = chars[Integer.parseUnsignedInt(String.valueOf(symbol))];
		
		for(Run run : run_list)
		{
			if(run.runLen == length)
			{
				return run;
			}
		}
		return null;
	}

	@Test
	@Order(5)
	@DisplayName("findRun 메서드 테스트")
	void findRunTest() {
		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();
		}
		
		List<Run>[] chars = app.getChars();
		
		byte symbol = 65;	// A
		int runLength = 3;
		
		Run run = app.findRun(symbol, runLength);
		
		System.out.println("탐색한 Run 정보");
		System.out.println(run);
		
	}

탐색한 Run 정보
Run [symbol=65, runLen=3, freq=1, left=null, right=null, codeword=2, codewordLen=3]

위 결과를 통하여 문자열 "AAA"의 codeword=2라는 사실을 알 수 있습니다.

 

References

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