[알고리즘][압축] 압축(Compression) #6 인코딩(Encoding)

1. 압축 수행과정

1. 압축파일 맨 앞부분(헤더)에 파일을 구성하는 run들에 대한 정보를 기록 (outputFrequencies 메서드)
   • run 객체의 개수
   • 원본 파일의 크기, byte단위이고 8byte로 저장됨
   • 각각의 Run 객체에 대한 문자(symbol), 길이(runLen), 빈도수(freq)를 저장함
     • symbol : 1byte 단위로 저장
     • runLen : 4byte 단위로 저장
     • freq : 4byte 단위로 저장
2. 원본 파일의 문자들을 codeword로 변환하여 0또는 1의 형태로 저장 (encode 메서드)

 

예를 들어 원본파일의 내용이 "AAABAACCAABA"인 경우 인코딩 수행과정은 다음과 같습니다.

위 수행과정에서 압축파일(fOut)에 작성하는 부분은 outputFrequencies 메서드와 encode 메서드 부분입니다.

 

2. outputFrequencies 수행과정

 

 

3. outputFrequencies 메서드 구현

	/**
	 * 압축 파일의 헤더에 Run들에 대한 정보와 원본파일의 크기를 출력
	 * @param fIn	: 압축할 파일
	 * @param fOut  : 압축된 파일
	 * @throws IOException 
	 */
	private void outputFrequencies(RandomAccessFile fIn
								 , RandomAccessFile fOut) throws IOException
	{
		fOut.writeInt(runs.size());	// run의 개수 출력, 4byte로 저장됨
		
		fOut.writeLong(fIn.getFilePointer());	// 원본 파일의 크기(byte단위)를 출력, 8byte로 저장됨
		
		// 각각의 Run 객체에 대한 정보를 압축 파일에 출력
		for(int i = 0; i < runs.size(); i++)
		{
			Run r = runs.get(i);
			fOut.write(r.symbol);	// 1byte 저장
			fOut.writeInt(r.runLen);// 4byte 저장
			fOut.writeInt(r.freq);  // 4byte 저장
		}
	}

 

	@Test
	@Order(6)
	@DisplayName("outputFrequencies 메서드 테스트")
	void outputFrequenciesTest() {
		HuffmanCoding app = new HuffmanCoding();
		RandomAccessFile fIn;
		
		try {
			fIn = new RandomAccessFile("sample.txt", "r");
			app.compressFile("sample.txt", fIn);			
			fIn.close();
		} catch (FileNotFoundException e) {
			System.out.println("Cannot open sample.txt");
		} catch (IOException e) {
			e.printStackTrace();
		}		
	}

 

위 수행결과를 보시면 Run객체들의 개수, 원본 파일의 크기, Run 객체들의 정보(symbol, runLen, freq)들이 byte형태로 작성됨을 볼 수 있습니다.

 

3. encode 수행과정

1. 원본파일의 맨처음부터 마지막까지 탐색을 수행함
2. 탐색하면서 Run 객체를 인식
3. Run 객체의 codeword를 buffer에 저장
4. 2~3번 과정을 모든 내용을 탐색할때까지 반복
5. buffer의 내용을 압축 파일에 저장

 

3. encode 메서드 구현

	/**
	 * 파일 압축 메서드
	 * fIn 파일 내용을 입축하여 fOut에 출력
	 * @param fIn  : 원본 파일
	 * @param fOut : 압축 파일
	 * @throws IOException 
	 */
	private void encode(RandomAccessFile fIn, RandomAccessFile fOut) throws IOException
	{
		byte prev_b = 0;
		int runLen = 0;
		StringBuffer buffer = new StringBuffer(32);
		
		while(fIn.getFilePointer() < fIn.length())
		{
			byte b = fIn.readByte();
			
			if(prev_b != 0 && b != prev_b)
			{
				// run 인식 & codeword 탐색
				Run run = findRun(prev_b, runLen);
				String codeword = getCodeword(run);
				// codeword를 buffer로 pack
				// 만약 버퍼가 꽉찼다면 출력 파일에 버퍼에 있는 것을 작성
				packCodewordToBuffer(codeword, buffer, fOut);
				runLen = 0;		
			}
			prev_b = b;
			runLen++;
		
			// 마지막 문자인 경우
			if(fIn.getFilePointer() >= fIn.length())
			{
				Run run = findRun(prev_b, runLen);
				String codeword = getCodeword(run);
				packCodewordToBuffer(codeword, buffer, fOut);
			}
		}
		fOut.writeBytes(buffer.toString());
	}

	/**
	 * codeword에 대한 각각의 byte들을 버퍼에 저장
	 * 만약 버퍼의 크기가 32byte가 되면 버퍼의 내용을 압축파일(fOut)에 작성하고
	 * 내용을 비움 
	 * @param codeword 각 문자에 대한 codeword
	 * @param buffer codeword의 byte들을 저장하는 버퍼
	 * @param fOut 압축파일
	 * @throws IOException
	 */
	private void packCodewordToBuffer(String codeword, StringBuffer buffer, RandomAccessFile fOut) throws IOException
	{		
		for(int i = 0; i < codeword.length(); i++)
		{
			if(buffer.length()==32)
			{
				fOut.writeBytes(buffer.toString());
				buffer.setLength(0);
			}
			buffer.append(codeword.charAt(i));
		}
	}

	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 객체들 배열에 저장
			fIn.seek(0);					// 파일의 맨 앞부분으로 이동
			encode(fIn, fOut);					// step5. fIn의 내용을 압축(encode)
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	@Test
	@Order(7)
	@DisplayName("encode 메서드 테스트")
	void encodeTest() {
		HuffmanCoding app = new HuffmanCoding();
		RandomAccessFile fIn;
		
		try {
			fIn = new RandomAccessFile("sample.txt", "r");
			app.compressFile("sample.txt", fIn);			
			fIn.close();
		} catch (FileNotFoundException e) {
			System.out.println("Cannot open sample.txt");
		} catch (IOException e) {
			e.printStackTrace();
		}		
	}

 

References

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