[알고리즘][압축] 압축(Compression) #7 디코딩(Decoding)

1. 압축 해제 수행과정

1. 압축 파일의 헤더에서 Run 객체들의 개수, 원본 파일의 크기, Run 객체들의 정보를 추출하여 저장(runs) (inputFrequencies 메서드)
2. runs 리스트를 기반으로 허프만 트리 생성 (createHuffmanTree 메서드)
3. 허프만 트리를 기반으로 Run 객체들의 codeword 할당 (assignCodeword 메서드)
4. 압축 파일을 읽어서 디코딩을 수행 (decode 메서드)

위 수행과정에서 허프만 트리 생성과 codeword 할당은 인코딩 과정에서의 메서드와 동일합니다.

 

2. inputFrequencies 메서드

압축 파일의 맨 앞부분(헤더)을 읽어서 Run 객체들의 개수, 원본 파일의 크기, Run 객체들의 정보들을 읽어서 runs 리스트에 저장하는 메서드입니다.

	/**
	 * fIn 파일의 run 객체 정보를 읽어서 runs에 추가함
	 * @param fIn
	 * @throws IOException
	 */
	private void inputFrequencies(RandomAccessFile fIn) throws IOException {
		int dataIndex = fIn.readInt();		// Run 객체들의 개수
		sizeOriginalFile = fIn.readLong();	// 원본파일의 크기
		runs.ensureCapacity(dataIndex);		// 리스트 크기 설정
		
		for(int i = 0; i < dataIndex; i++)
		{
			Run r = new Run();
			r.symbol = (byte) fIn.read();	// 문자
			r.runLen = fIn.readInt();		// 문자의 길이
			r.freq = fIn.readInt();			// 빈도수
			runs.add(r);
		}
	}

 

3. decode 메서드

압축 파일의 본문부터 시작하여 0 또는 1로된 문자를 읽어서 Run 객체를 탐색하고 Run 객체의 symbol을 압축해제 파일에 작성하는 메서드입니다.

	/**
	 * 압축파일을 압축해제하는 메서드
	 * @param fIn 압축파일
	 * @param fOut 압축해제한 파일
	 * @throws IOException 
	 */
	private void decode(RandomAccessFile fIn, RandomAccessFile fOut) throws IOException {
		int ch;
		Run p = null;
		
		while(fIn.getFilePointer() < fIn.length())
		{
			ch = fIn.read()-48;
			p = theRoot;
			while(true)
			{
				if(p.left == null && p.right == null)
				{
					for(int i = 0; i < p.runLen; i++)
					{
						fOut.write(p.symbol);
					}
					break;
				}
				else if(ch == 0)
				{
					p = p.left;
				}
				else
				{
					p = p.right;
				}
				
				if(p.left != null || p.right != null)
				{
					ch = fIn.read()-48;
				}
			}
		}
	}

	@Test
	@Order(8)
	@DisplayName("encode/decode 메서드 테스트")
	void encodeTest2() throws IOException {
		HuffmanEncoder he = new HuffmanEncoder();
		HuffmanDecoder hd = new HuffmanDecoder();
		
		he.encoder("sample.txt");
		
		hd.decoder("sample.txt.z");
	}

sample.txt.z 내용
0 0 0 5 0 0 0 0 0 0 0 12 65 0 0 0 3 0 0 0 1 66 0 0 0 1 0 0 0 2 65 0 0 0 2 0 0 0 2 67 0 0 0 2 0 0 0 1 65 0 0 0 1 0 0 0 1 48 49 48 49 49 49 48 48 48 49 48 49 49 48 49 49 
encode 완료
decode 파일 내용
AAABAACCAABA

 

References

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