[C++] Arithmetic Coding(산술 부호화)

안녕하세요 힘법사입니다. 오늘은 제가 Arithmetic Coding에 대해서 대학 강의를 들으면서 이를 C++로 구현해보면 재미있을 것 같아 만든 해당 내용에 대해서 공유하겠습니다.

 

Arithmetic coding

Arithmetic coding은 전체 메시지를 하나의 유닛으로 취급할 수 있게 해 줍니다. 정확히는 실수 하나로 전체 메시지를 나타낼 수 있게 해 줍니다. 그리고 압축 시 손실이 없는 Lossless 방식입니다. 해당 게시물에서는 Encoding만 다룰 것이고 제가 시간이 허락한다면 Decoding도 만들어 보겠습니다.

 

step1

우선 사전에 심볼들에 대해서 확률을 알고 있어야 합니다.

제가 예를 들어보겠습니다.

저는 심볼 A B 그리고 C의 조합으로 메시지를 전송하고자 합니다.

이때 A의 확률이 0.5 B의 확률이 0.4 C의 확률이 0.1일 때

이를 다음과 같은 표로 정리할 수 있습니다.

산술 보호화를 위한 표

확률들을 accumulative 하게 쌓을 때 P Range와 같은 Column을 표에서 만들어 줄 수 있습니다.

자 이제 부호화를 위한 준비는 모두 끝났습니다.

제가 BBB라는 메시지를 보낸다고 가정해보겠습니다.

 

step2

 

그림 인코딩 과정

우선 또 표가 하나 나오는데요 저 표가 인코딩을 위해서 반드시 필요한 표입니다. 저 표가 나오는 원리는 다음과 같습니다.

그림 message의 Low값과 High값 결정 과정

보시는 것처럼 전체 P Range에서 메시지는 항상 심볼 B이기 때문에 상단 값의 0.9를 곱한 값 하단 값에 0.5를 곱한 값으로 계속해서 줄어나가게 됩니다. 이렇게 해서 메시지의 High 값 0.844, Low값 0.78을 알 수 있습니다.

메시지를 만드는 과정은 아주 간단합니다. 메시지는 이진수로 표현되고 이진수를 계속해서 늘려가면서 해당 값이 Low와 High 값 사이에 최초로 들어오게 되면 해당 과정을 종료합니다.

 

규칙은 우선은 0.로 시작할 때 무조건 1을 붙이는 것입니다. 여기서 1을 붙이면 0.1이 되고 이는 10진수로 0.5가 됩니다. 해당 값은 어떤가요? Low(0.78) 보다 낮습니다. 고로 바로 이어서 1을 붙입니다. 그러면 0.11을 획득하게 됩니다. 이는 십진수 값으로 0.75입니다. 어떤가요? Low 보다 작은 값입니다. 고로 또 1을 붙여줍니다. 그럼 0.111이 됩니다. 이는 0.875로 어떤가요? High보다 높습니다. 고로 다시 1을 때고 0을 붙인 후에 다시 1을 붙여줍니다. 그럼 0.1101이 됩니다. 해당 값은 어떤가요? 0.8125입니다. 정확히 High와 Low 사이로 들어왔으므로, 인코딩 과정을 종료해줍니다.

 

자 이렇게 0.1101로 BBB라는 값을 표현할 수 있음을 확인했습니다.

이제 제가 만든 프로그램도 똑같이 돌아가는지 확인해야겠지요?

 

프로그램

#include "Arithmetic.h"

int main() {
	std::vector<char> symbols = {'A','B','C'};
	std::vector<float> p = {0.5,0.4,0.1};
	std::string word = "BBB";
	ArithmeticCoding x_Coding(symbols, p);
	x_Coding.CalcRange();
	x_Coding.ArithmeticAlgorithm(word);
	x_Coding.GenCodeWords();
	x_Coding.PrintCode();
}

네 우선 다음과 같이 심볼들의 종료 그리고 확률 메시지를 적어줬습니다. 이제 실행시켜 보겠습니다.

그림. 결과

위의 손 계산과 일치하게 0.1101이 빠르게 계산되었습니다! 해당 코드는 아래 주소에서 전체 코드를 보실 수 있습니다.

 

2017103030/ArithmeticCoding (github.com)

GitHub - 2017103030/ArithmeticCoding

네 이상입니다! 다음에도 빠르게 더 좋은 내용을 써보겠습니다 감사합니다 ^^