산술 부호화

1. 서론

산술 부호화(Arithmetic Coding)에 대해 설명하고 예제 메시지를 부호, 복호화 방법에 대해 설명한다.

2. 사전 연구

2.1 압축 알고리즘

데이터 압축은 데이터를 더 적은 공간에 효율적으로 전송, 저장하기 위한 기술이다. 데이터를 더 작은 크기로 변환시키는 인코딩과 저장된 데이터를 다시 원래의 형태로 복원시키는 디코딩 과정으로 이루어진다. 디코딩한 데이터의 세부 사항 일부를 잃는 손실 알고리즘과 모두 보존하는 무손실 알고리즘이 있다. 무손실 압축 알고리즘에는 반복 길이 부호화와 허프만 부호화, 산술 부호화 등이 있다. 손실 압축 알고리즘은 인간의 느끼지 못하는 정도의 음성, 화상의 변화를 역이용하여 압축률을 높인다[1].

2.2 허프만 부호(Huffman Code)

허프만 부호는 문자의 빈도 또는 확률정보를 이용해 통계적인 방법을 이용하여 압축하는 부호이다. 빈도가 높은 문자는 짧은 코드, 빈도가 낮은 문자는 긴 부호에 매핑한다. 또한 접두부와 최적코드를 사용하여 부호를 구성한다. 허프만 부호화는 각 기호에 정수의 비트 길이를 가지는 코드워드를 부여한다[2].

3. 산술 부호화

3.1 개념

산술부호화는 무손실 압축 방법의 하나로, 다양한 길이를 가지는 부호로 압축하는 방법(Variable-length entropy encoding)이다. 무손실 압축 방법에는 허프만 부호와 산술 부호화가 있는데 공통적으로 가변길이를 가지는 부호를 사용한다. 부호 간 사용 빈도가 차이가 있다는 점에 기반하여 가변 길이를 이용하여 압축을 가능하게 하므로, 무손실 압축이 가능하다. 하지만 최종 부호어의 표현 방법에 차이가 있다. 허프만 부호는 단순히 기호들의 나열을 통해서 표현한다. 하지만 산술 부호화는 부호화하고자 하는 메시지 전체가 하나의 숫자(n, 0.0 ≤ n < 1.0)로 나타난다. 하나의 입력 심볼에 하나의 부호어를 대응시키는 것이 아니라, 여러 심볼들을 묶은 가변길이 심볼열을 ‘고정길이 부호어’로 표현하는 방법이다. 이때 입력 가변 심볼열의 발생 확률이 거의 일정하게 유지되도록 묶게 된다. 입력 가변 스트림의 발생 빈도로부터 확률을 추정하게 된다. 따라서 복잡한 수학적 계산에 의해 부호화를 진행한다[3].

산술 부호화의 특징으로는 소스 데이터의 확률적 성질을 이용하며 이진 데이터 소스처럼 적은 소스 알파벳 심볼{0,1}을 가지며, 각 소스 알파벳 심볼 간에 높은 비대칭적인 확률을 갖는 경우에 부호화하는데 유리하다. 메시지의 확률을 사용하여 부호를 나타내는 데 사용되는 간격을 연속적으로 좁힌다는 특징이 있다. 각 심볼의 빈도에 따라 0.0~1.0 구간을 할당한 후, 인코딩된 신호를 비교한다. 또한 주어진 심볼에 대해 최적의 엔트로피에 가까운 압축률을 보인다[4].

3.2 부호화 알고리즘

산술부호화 알고리즘에 대해 설명한다. 설명에 필요한 기호들은 다음과 같다.

기호	설명
N[x]	x의 확률
Q[x]	x의 누적확률(Q[i]=N[0]+N[1]+...+N[i])

산술부호화 인코딩 알고리즘은 다음과 같다.

L =0.0; H =1.0;
While((x = getc(input))!=EOF)
{
	R = (H-L);
	H = L + R * Q[x];
	L = L + R * Q[x-1];
}
Output(L); 

R은 반복의 주기 범위(interval range)를 뜻하고, H와 L은 현재 코드의 양 끝을 의미한다. x는 인코딩된 새로운 심볼을 의미한다. H와 L은 0과 1로 초기화 되어 있다.

다음은 산술부호화를 위한 메시지 모형이다.(부호화 심볼 : ABCD)

Symbol, x	Probability, N[x]	[Q[x-1], Q[x])
A	0.4	0.0, 0.4
B	0.3	0.4, 0.7
C	0.2	0.7, 0.9
D	0.1	0.9, 1.0

 

 

각각의 부호화 단계는 다음의 세 가지 정보에 따라 실행된다.

1. 부호화할 다음 기호

2. 현재의 구간

3. 각각의 단계에서 다음에 올 수 있는 기호들의 확률

아래 [그림 1]은 스트링 [표 2]의 모형을 가지는 스트링 데이터 “BCAB”를 산술 부호화한 것이다.

[그림 1] 메시지 심볼에 대한 누적확률 구간의 확대 표현

현재의 구간을 다음에 올 수 있는 기호들에 해당하는 더 작은 구간으로 나눈다. 구간의 크기는 기호가 나타날 확률에 비례한다. 그리고 이 구간들 가운데 메시지에 실제로 나타나는 기호에 대해 해당하는 구간을 골라 다시 이 구간으로 다음 단계를 진행한다.

Symbol	Low	high	Range
	0	1.0	1.0
B	0.4	0.7	0.3
C	0.61	0.67	0.06
A	0.61	0.634	0.024
B	0.6196	0.6286	0.0009

[표 3] 산술부호화 과정 중 생성된 고, 저 영역

심볼열 “BCAB”에 대응하는 누적확률 구간은 [0.6286, 0.6196)이다.

부호화를 위해서는 누적확률 구간 내의 값을 전송하면 된다. 설명에서는 Low 값인 을 전송한다.

산술 부호화 디코딩 알고리즘은 다음과 같다.

v = input_code();
for(;;){
	x=find_symbol_straddling_this_range(v);
	putc(x);
	R = Q[x] - Q[x-1];
	v = (v – Q[x-1])/R;
}

부호화된 실수와 메시지 모형을 함께 전송하면 복호화 알고리즘은 위와 같이 프로세스를 진행하여 메시지를 복원한다.

을 전송받으면 다음 과정을 통해 복호화한다.

1. 부호화된 스트림이 포함된 구간을 찾는다.

은 [0.4, 0.7)구간 내에 속한다.

2. 구간 내에 속한 심볼을 구한다.

[0.4, 0.7)은 ‘B’의 심볼이다. ‘B’로 복호된다.

3. 다음 구간을 구하기 위해 전송 값에서 해당하는 구역의 Low 값을 빼고 Range로 나눈다.

구간 [0.7, 0.9)에 속하는 “C”로 복호된다. 이를 반복수행하여 복호화한다. 복호화 과정은 다음 표와 같다.

v	Output char x	Q[x-1]	Q[x]	R
0.6196	B	0.4	0.7	0.3
0.732	C	0.7	0.9	0.2
0.16	A	0.0	0.4	0.4
0.4	B	0.4	0.7	0.3
0.0

[표 4] 복호화 과정

위의 과정을 통해 메시지 “BCAB”을 복호한다.

4. 산술 부호화의 단점

산술 부호화의 단점은 각 부호를 압축할 때마다 구간을 계산해 주어야 한다는 복잡함 때문에 허프만 부호화에 비하여 연산량이 매우 크다는 점이다. 그리고 “메시지 끝”을 나타내는 별도의 기호를 사용해야 한다는 “The EOF problem”이 있다. 간격의 마지막 끝을 암호화 코드로 선택했을 때, 만약 하나의 메시지가 다른 부호어의 접두사(prefix)로 사용될 수 있기 때문에 일의 부호가 되지 않을 가능성이 있다(e.g. BCAB, BCABAA, BCABA). 몇 개의 기호가 들어있는지에 대한 부가적인 정보가 필요하다는 문제도 존재한다[5].

5. 결론

산술 부호화의 개념, 알고리즘에 대해 분석하고 손실압축 알고리즘인 허프만 코드와 비교하였다. 산술 부호화는 입력 신호의 발생 빈도로부터 입력 신호의 확률을 추정하는 방식으로 유사하지만 허프만 부호보다 압축률이 좋다는 특징이 있으나 복잡한 수학적 계산을 수행해야 하므로 연산 시간이 오래 걸린다는 차이점이 있다. 산술 부호화는 이진 데이터처럼 적은 심볼을 갖고, 비대칭적인 확률분포를 갖는 소스를 압축하는데 유리하다.

통신 채널의 발달로 멀티미디어 컨텐츠들은 더욱 많이 만들어지고 유통되고 있다. 여기에 사용되는 통신 채널은 대역폭의 제약을 받기 때문에 제한된 대역폭 내에서 보다 많은 데이터를 전송하기 위한 방법이 연구되어 왔다. 통신 기술의 발달로 사용 가능한 대역폭 또한 계속 증가하고는 있지만 컨텐츠 또한 그에 따라 대용량의 고품질 데이터를 사용하게 되므로 부호화는 멀티미디어 컨텐츠의 전송 및 저장에 있어 없어서는 안 될 중요한 기술이다[6].

---

References

[1] 데이터압축. 위키백과. Available:https://ko.wikipedia.org/wiki/데이터_압축

[2] 산술부호화. 위키백과. Available:https://ko.wikipedia.org/wiki/산술_부호화

[3] Text Compression. Slideshare. Available:https://slideplayer.com/slide/8721705/

[4] Huffman Coding 호프만 부호화. 정보통신기술용어해설. [Online] Available: http://www.ktword.co.kr/word/abbr_view.php?m_temp1=1443

[5] Arithmetic Coding. https://thinkpiece.tistory.com/2

[6] 윤성용. 컨텍스트 기반 산술부호화를 이용한 “USAC에서의 엠펙 서라운드 모듈의 부호화 효율 개선.” Ph.D. 서울대학교. 2012.