[C++] Arithmetic Coding(2) - Decode

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

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

안녕하세요 이번 게시물은 제가 지난 게시물에서 말씀드린 산술 부호화(Arithmetic Coding)의 Decoding 과정에 대해서 이야기 드리겠습니다. 이 과정에 대해서 제대로 이해하고 싶으신 분은 위의 링크부터 보시면 되시겠습니다.

 

자. 보셨나요? 그럼 가겠습니다.

 

우선 이 Encoding의 역과정으로 Decoding은 진행된다는 사실은 모든 분들이 아실 것입니다. 사실 이 Decode의 경우에는 제가 만들어보니 Encode가 더 많은 노력이 들었지 Decode는 매우 단순 했습니다.

 

과정 1.

이진 수 형태의 binaray 메세지를 decimal 형태로 변환해 줍니다.

char	Probability	Range
A	0.5	0-0.5
B	0.4	0.5-0.9
$	0.1	0.9-1

우선 저는 총 3개의 char에 대한 상황으로 이와같이 가정해주었습니다.

 

이 때 제가 Encoding한 메세지는 AA$로 Coding 결과는 0.110111입니다.

이를 Decimal로 계산하는 함수는 다음과 같습니다.

 

float ArithmeticCoding::GetDecimal() const
{
	float decimal = 0.0;
	for (int i = 0; i < m_code.size(); i++) {
		decimal += m_code[i] * pow(2, -(i + 1));
	}
	return decimal;
}

간단하게 이런 10진수 변화 함수를 작성해주었는데요 이를 이용하면 0.110111은 0.859375입니다. 

 

2. 메세지 복원

우선 해당 0.859375가 위의 표에 어떤 char의 Range에 속하는지 확인합니다. 지금 제가 보기엔 B에 속하네요 그럼 첫 char는 B가 됩니다.

이 이후, 0.859375에서 Range의 Low(0.5)값을 빼줍니다. 그럼 0.359375가 되겠죠?

여기서 다시 해당 char의 Range를 나눠줍니다. 0.4를 나눠주면? 0.8984375가 됩니다. 또 다시 char B의 Range 0.5-0.9 사이에 속하네요 이어지는 char 또한 B임을 알 수 있습니다.

다시 앞선 과정을 반복해주면? 0.99609375가 나옵니다.

이는 메세지의 종결을 뜻하는 $의 Range에 속하네요!

 

즉, 전체 메세지는 BB$임을 알아낼 수 있습니다. 해당 코드는 아래와 같습니다.

 

std::string ArithmeticCoding::Decode()
{
	//get binary cod and convert to decimal
	float decimal = GetDecimal();
	//std::vector<std::string>::iterator itr = ;
	char symbol;
	std::string out = "";
	do {
		for (int i = 0; i < m_ranges.size(); i++) {
			symbol = m_symbols[i];
			if (GetLow(symbol) <= decimal && decimal < GetHigh(symbol)) break;
		}
		out += symbol;
		float low = GetLow(symbol);
		float high = GetHigh(symbol);
		float range = high - low;
		decimal = (decimal - low) / range;
	} while (symbol != '$');

	return out;
}

이렇게 Arithmetic Encoding에 이어서 Decoding도 알아봤습니다! 아래 링크는 이 전체 과정을 실습해볼 수 있는 코드입니다. 다음엔 더 좋은 내용으로 찾아오겠습니다. 감사합니다.

 

https://github.com/2017103030/ArithmeticCoding

GitHub - 2017103030/ArithmeticCoding