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

1. Huffman Method with Run-Length Encoding

• 파일을 구성하는 각각의 run들을 하나의 super-symbol로 봅니다.
• super-symbol들에 대해서 Huffman coding을 적용합니다.
• 예를 들어 문자열 AAABAACCAABA은 5개의 super-symbol들 AAA, B, AA, CC, A로 구성되며, 각 super-symbol의 등장횟수는 아래와 같습니다.

symbol	A	C	A	B	A
run length	3	2	1	1	2
frequency	1	1	1	2	2

 

Prefix Code 이진트리 생성 과정

 

• AAABAACCAABA은 1100110111100100으로 인코딩됩니다.

 

2. 제 1단계 : Run과 Frequency 찾기

• 압축할 파일을 처음부터 끝까지 읽어서 파일을 구성하는 run들과 각 run들의 등장횟수를 계산함
• 먼저 각 run들을 표현할 하나의 클래스 class Run을 정의. 클래스 Run은 적어도 3개의 필드 멤버 symbol, runLen, 그리고 freq을 가져야 합니다. 여기서 symbol은 byte 타입이이고 나머지는 정수 타입입니다.
• 인식할 run들은 하나의 ArrayList에 저장함
• 적절한 생성자와 symbol과 runLen을 비교할 equals 메서드를 구현함
• 데이터 파일을 적어도 두번 읽어야합니다. 한번은 run들을 탐색하기 위해서, 그리고 다음은 실제로 압축을 수행하기 위해서입니다.

Run 인식하기

 

public class Run {
	public byte symbol;
	public int runLen;
	public int freq;
	
	public Run(byte symbol, int runLen, int freq) {
		this.symbol = symbol;
		this.runLen = runLen;
		this.freq = freq;
	}

	public boolean equals(byte symbol, int runLen) {
		return this.symbol == symbol && this.runLen == runLen;
	}

	@Override
	public String toString() {
		return "Run [symbol=" + symbol + ", runLen=" + runLen + ", freq=" + freq + "]";
	}
	
	
}

public class HuffmanCoding {
	private ArrayList<Run> runs = new ArrayList<Run>();
	
	private boolean checkSymbol(byte symbol, int runLen)
	{
		for(Run r : runs)
		{
			if(r.equals(symbol, runLen))
			{
				r.freq++;
				return true;
			}
		}
		return false;
	}
	
	private void collectRuns(RandomAccessFile fIn) throws IOException
	{
		int ch=-1;
		List<Byte> list = new ArrayList<Byte>();
		int count = 0;
		byte prev_symbol = 0;
		
		while((ch = fIn.read())!=-1)
		{
			byte symbol = (byte) ch;
			
			if(list.isEmpty())
			{
				list.add(symbol);		
			}
			else if(prev_symbol==symbol)
			{
				list.add(symbol);
			}
			else
			{
				if(checkSymbol(prev_symbol, count))
				{
					list.clear();
					list.add(symbol);
					count = 0;
				}
				else
				{
					runs.add(new Run(prev_symbol, count, 1));
					list.clear();
					list.add(symbol);
					count = 0;
				}
				
			}
			prev_symbol = symbol;
			count++;		
		}
		
		if(!list.isEmpty())
		{
			if(!checkSymbol(prev_symbol, count))
			{
				runs.add(new Run(prev_symbol, count, 1));
			}
		}
	}
	
	public static void main(String args[])
	{
		HuffmanCoding app = new HuffmanCoding();
		RandomAccessFile fIn;
		String fileName = "sample.txt";
		try {
			fIn = new RandomAccessFile("sample.txt", "r");
			app.collectRuns(fIn);
			fIn.close();
		} catch (FileNotFoundException e) {
			System.out.println("can not open" + fileName);
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}
}

sample.txt

AAABAACCAABA

 

[
 Run [symbol=65, runLen=3, freq=1], 
 Run [symbol=66, runLen=1, freq=2], 
 Run [symbol=65, runLen=2, freq=2], 
 Run [symbol=67, runLen=2, freq=1], 
 Run [symbol=65, runLen=1, freq=1]
]

 

References

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