엔트로피 코딩 (Entropy Coding) 이란?
일반적으로 엔트로피(Entropy)란 '무질서도' 혹은 '불확실성'을 가리킨다.
'정보의 양'을 중요시하는 정보공학적 관점에서는 '평균 정보량'을 엔트로피라고 한다.
엔트로피에 대해 설명하자면...
앞으로 발생할 사건에 대해 (확정적인) 정보가 많다면 예측률이 높아진다.
이러한 경우 우리는 사건이 발생해도 별로 놀라지 않는다.
즉, 이 사건은 결과적으로 우리에게 적은 정보를 제공한다.
이를 엔트로피가 낮다고 한다.
반면, 어떤 정보일지 불확실할수록 사건에 대해 예측이 어려워진다.
따라서 이 사건이 발생할 때 우리는 훨씬 유용한 정보를 제공받게 된다. (놀라운 정보가 많다)
이를 엔트로피가 높다고 한다.
예를 들어 동전과 주사위가 있다.
동전을 던져서 발생할 확률은 주사위를 던져 발생할 확률보다 작다.
즉, 동전 던지기보다 주사위 던지기가 엔트로피가 낮은 것이다.
정리하자면, 엔트로피가 낮다면 특정한 심볼이 발생활 확률이 높다. (예측 가능)
엔트로피가 높다면 각 심볼들이 무작위적(랜덤하게)으로 발생할 확률이 높고 중복성이 줄어든다.
엔트로피 코딩이란 데이터 심볼이 발생할 확률에 따라 각각의 심볼이나 연속된 심볼을 적절한 길이로 부호화하여 표현하는 것이다.
위에서 설명했듯이 데이터 심볼들의 발생 확률에 따라 '엔트로피' 즉 심볼당 평균 정보량이 결정된다.
따라서 심볼당 평균 부호 길이가 엔트로피에 가까워지도록 부호를 할당하여 압축 효율을 높이는 것이 엔트로피 코딩의 목적이다.
또한, 엔트로피 코딩은 대표적인 무손실 압축 기법 중 하나이다.
무손실 압축이란 압축한 데이터를 복원했을 때 압축전의 데이터와 완벽히 일치하는 것을 이야기한다.
엔트로피 코딩에서는 압축할 데이터의 특성을 고려하지 않고 모든 데이터에 대해 통계적인 방식으로 압축을 진행하므로 데이터 손실이 발생하지 않는 것이다.
런렝스 부호화 (Run-length encoding)
런렝스 부호화란 데이터에서 같은 값이 연속으로 나타나는 경우, 개수와 반복되는 값으로 표현하는 방법이다.
1bit 흑백 사진과 같이 연속된 값이 많이 있는 데이터에 효과적이다.
예를 들어 AAAAAAAAABBBBCDDDEEEEEEE라는 문자열이 있다.
해당 문자열의 길이는 24bit이다.
런렝스 부호화를 이용한다면 이를 9A4B1C3D7E로 압축할 수 있으며 압축된 문자열의 길이는 10bit임을 확인할 수 있다.
런렝스 부호화, 복호화를 수행하는 Java code를 작성해보았다.
간단한 개념 이해를 위해 간단하게 작성한 code라 아래 전제조건을 기본으로 한다.
- data 각각의 문자는 한자리의 알파벳 혹은 숫자이다.
- 10회 이상 반복되지 않는다.
public class RunLength {
public static void main(String args[]){
String data = "AAAAAAAAABBBBCDDDEEEEEEE";
System.out.println("@@data : " + data);
String encodeData = encoding(data);
System.out.println("encode : " + encodeData);
String decodeData = decoding(encodeData);
System.out.println("decode : " + decodeData);
}
public static String encoding(String data){
StringBuffer encodeData = new StringBuffer();
int runLength = 1;
for(int i=1; i<=data.length(); i++){
if(i<data.length()){
if (data.charAt(i - 1) == data.charAt(i)) {
runLength++;
} else {
encodeData.append(runLength);
encodeData.append(data.charAt(i - 1));
runLength = 1;
}
}else {
encodeData.append(runLength);
encodeData.append(data.charAt(i - 1));
}
}
return encodeData.toString();
}
public static String decoding(String data){
StringBuffer decodeData = new StringBuffer();
for(int i=0; i<data.length(); i=i+2){
for(int j=0; j<data.charAt(i)-'0'; j++){
decodeData.append(data.charAt(i+1));
}
}
return decodeData.toString();
}
}결과
@@data : AAAAAAAAABBBBCDDDEEEEEEE
encode : 9A4B1C3D7E
decode : AAAAAAAAABBBBCDDDEEEEEEE설명
encoding
- data 문자열의 2번째 문자부터 마지막 문자+1까지 반복하며 이전 문자와 동일한지 check
- 이전 문자와 동일하다면 runLength 개수를 1 증가
- 이전 문자와 다르다면 encodeData에 이전 문자의 runLength 개수와 문자를 append
- 마지막 Loop는 문자열을 벗어나게 되므로 무조건적으로 이전 문자의 runLength 개수와 문자를 append
decoding
- 전제조건에 따라 runlength와 문자는 각각 한 자릿수
- 따라서 runlength와 문자를 하나의 세트로 보고 runlength 개수만큼 반복하며 decode 수행