산술 부호화

산술 부호화(算術符號化, 영어: 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이 빠지면 이 후에 나오는 데이터에 따라서 10001011이 되어 정확하게 복호화 하지 못할 가능성이 생긴다.

단점

산술 부호화 알고리즘은 압축 대상 부호의 개수가 많을 수록 압축의 한계를 나타내는 정보 엔트로피에 근접하게 되지만, 각 부호를 압축할 때마다 구간을 계산 해 주어야 한다는 복잡함 때문에 허프만 부호화에 비하여 연산량이 매우 크다.

또한 "메시지 끝"을 나타내는 별도의 기호를 사용하거나, 몇개의 기호가 들어있는지에 대한 부가적인 정보가 필요하다는 문제가 있기 때문에, 단문의 단순한 메시지의 경우에는 오히려 허프만 부호화보다 효율이 떨어질 수 있다. 위의 예제를 허프만 부호화를 통해 부호화 하게 되면, "메시지 끝" 기호가 필요없기 때문에 단지 3비트 만을 소모할 뿐이다.