 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
산술 부호화(算術符號化, Arithmetic coding)는 무손실 압축에 사용되는 엔트로피 부호화 알고리즘 가운데 하나이다. 다른 엔트로피 부호화 알고리즘이 각각의 기호를 1:1로 부호로 대체하는 반면에, 산술 부호화는 전체 메시지를 하나의 실수 n으로 대체한다. (0.0 ≤ n < 1.0) 산술 부호화는 주어진 기호와 확률분포에 대해 최적에 가까운 압축률을 보일 수 있다.
목차 |
동작 원리
메시지 모형
산술 부호화를 실행하기 위해서는 먼저 데이터의 모형을 결정해야 한다. 모형이란 메시지의 기호들이 어떤 패턴을 갖고 있을 것인지를 예측하는 것으로, 이 모델이 실제 메시지를 더 정확하게 예측할수록 압축률은 더 높아진다.
예를 들어 다음과 같이 메시지에 출현하는 기호들의 고정된 통계적 모형을 가정할 수 있다 :
- 60% : "가"
- 20% : "나"
- 10% : "다"
- 10% : "메시지 끝" (이 기호가 나타나면 메시지가 끝났음을 알려 복호화 알고리즘이 정상적으로 종료되도록 한다.)
위와 같은 간단한 네 개의 기호 집합 외에도 더 복잡한 모형 또한 얼마든지 다룰 수 있다. 예를 들어 고차 모형은 이전까지 나온 기호들의 역사에 따라 다음 기호가 나타날 확률을 달리 계산할 수도 있다. 만약 영어 텍스트를 압축하려고 한다면 "Q"나 "q" 기호 다음에는 "u"가 나타날 확률이 훨씬 높을 것이라고 예측할 수 있을 것이다. 혹은 적응적인 모형을 생각할 수도 있다. 이 경우에는 부호화 알고리즘이 기호를 하나씩 압축할 때마다 지금까지 나온 기호의 분포에 따라 모델을 조금씩 바꿔가면서 압축한다. 부호화 알고리즘이 어떤 모형을 취하든 복호화 알고리즘이 동일한 모형을 취한다면 메시지를 원래 그대로 복원할 수 있다.
부호화 단계
각각의 부호화 단계는 다음과 같은 세 가지 정보에 따라 실행된다.
- 부호화할 다음 기호
- 현재의 구간(0에서 1사이의 임의의 두 실수 사이를 가리킨다)
- 각각의 단계에서 다음에 올 수 있는 기호들의 확률 (앞에서도 언급한 것처럼 이 확률은 고정되어 있을 수도 있고 고차 모형이나 적응적인 모형의 경우에서처럼 계속해서 변할 수도 있다.)
먼저 현재의 구간을 다음에 올 수 있는 기호들에 해당하는 더 작은 구간으로 나눈다. 이때 각각의 기호에 해당하는 구간들의 크기의 비율은 기호가 나타날 확률에 비례해야 한다. 그리고 이 구간들 가운데 메시지에 실제로 나타나는 기호에 해당하는 구간을 골라 다시 이 구간으로 다음 단계를 진행한다.
위의 네 개의 기호를 사용하는 모형을 예로 들어 [0-1)의 구간을 나누어 보자. (이 예제에서는 이해를 돕기 위해 십진법을 사용하지만, 실제 구현에서는 효율을 위해 이진법을 사용한다.)
| 기호 | 확률 | 구간 |
|---|---|---|
| 가 | 60% | [0, 0.6) |
| 나 | 20% | [0.6, 0.8) |
| 다 | 10% | [0.8, 0.9) |
| 메시지 끝 | 10% | [0.9, 1) |
만약 메시지가 "가다(메시지 끝)"이었다면 부호화는 다음과 같이 진행될 것이다.
첫번째 기호가 "가"이므로 구간으로 [0, 0.6)을 선택한다.
새로운 구간 [0, 0.6)은 다시 부호화를 위해 다음과 같이 더 작은 구간으로 나뉜다.
| 기호 | 확률 | 구간 | |
|---|---|---|---|
| 가 | 60% | [0, 0.36) | [0, 0.6)의 0%~60% |
| 나 | 20% | [0.36, 0.48) | [0, 0.6)의 60%~80% |
| 다 | 10% | [0.48, 0.54) | [0, 0.6)의 80%~90% |
| 메시지 끝 | 10% | [0.54, 0.6) | [0, 0.6)의 90%~100% |
다음 기호는 "다"이므로 이 중에 [0.48, 0.54) 구간을 선택한다. 다시 이 구간을 더 작게 나누면
| 기호 | 확률 | 구간 |
|---|---|---|
| 가 | 60% | [0.48, 0.516) |
| 나 | 20% | [0.516, 0.528) |
| 다 | 10% | [0.528, 0.534) |
| 메시지 끝 | 10% | [0.534, 0.54) |
"메시지 끝"에 해당하는 구간은 [0.534, 0.54)이고 실수 0.537이 이 구간 안에 포함되므로 전체 메시지는 하나의 실수 .537로 부호화된다.
메시지 복호화
이렇게 부호화된 실수와 메시지 모형을 함께 전송하면 복호화 알고리즘은 이 프로세스를 동일하게 진행하여 메시지를 복원한다.
위의 메시지를 다시 예로 들어 보자.
- 부호화된 실수 .537은 첫번째 구간 가운데 [0, 0.6) 사이에 포함되므로 첫 번째 기호는 "가"가 된다.
- 위와 동일하게 [0, 0.6)을 나누면 .537은 다시 이 구간 가운데 [0.48, 0.54) 사이에 포함되므로 두 번째 기호는 "다"가 된다.
- [0.48, 0.54)를 다시 더 작은 구간으로 나누면 .537은 [0.534, 0.54) 사이에 포함된다. 따라서 세 번째 기호는 "메시지 끝"이 된다.
- "메시지 끝"을 복호화하였으므로 복호화 알고리즘은 더 이상 복호화를 진행하지 않아야 함을 알고 종료된다. (만약 "메시지 끝"을 나타내는 기호가 없다면 복호화 알고리즘은 복호화를 무한히 반복할 것이다.)
압축 효율
위 예제에서 같은 메시지가 .534, .535, .536, .537, .538, .539의 어떤 값으로도 부호화될 수 있음을 알 수 있다. 즉 이진수가 아니라 십진수로 부호화하여 약간의 비효율이 포함되었음을 암시한다. 실제로 세 자리 십진수의 정보량은 약 9.966비트이다. 만약에 이 정보를 이진 실수로 부호화했다면 8비트의 실수 .10001010(십진수 .5390625와 같은 값)으로 부호화되었을 것이고 이것은 예제 메시지의 엔트로피인 7.381비트보다 조금 더 많은 정도이다. (이때 부호화된 이진수에서 마지막 0이 빠지면 정확도가 1비트 줄어들어 예제 메시지를 정확히 복호화할 수 없다.)
