비트 압축 - 33% 압축하기

삼성 C형 전체 링크

 

참고

- 33% 압축하기

- 37.5% 압축하기 1 (8bit : 5bit)

- 37.5% 압축하기 2 (16bit : 10bit ~)

- 허프만 알고리즘

 

'a' ~ 'z' 까지만 사용되는 문자열이 있는 경우, 이 문자열을 33% 압축해보자.

---

아래 문제를 PASS 시켜보자.

#include <stdio.h>

unsigned char original[100];
unsigned char temp[67];

int mystrcmp(unsigned char *a, unsigned char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

void compress(unsigned char* src, unsigned char* dest)
{

}

void decompress(unsigned char* dest, unsigned char* src)
{

}

int main()
{	
	unsigned char problem[100] = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstu";

	int len;
	for (len = 0; problem[len]; len++);

	for (int i = 0; i < len; i++) original[i] = problem[i];

	compress(original, temp);

	for (int i = 0; i < len; i++) original[i] = 0;

	decompress(temp, original);

	printf("%s\n", original);
	if (mystrcmp(problem, original) == 0) printf("PASS!!\n");
	else printf("FAIL!!\n");

	return 0;
}

 

문제는 다음과 같다.

 

1. problem 배열에는 99개의 문자열이 'a' ~ 'z'까지 존재한다.

2. original[100]에 problem[100]을 복사한다.

3. compress에서 original[100]을 temp[67]로 압축하고, original은 모두 0으로 초기화된다.

4. decompress에서 temp[67]을 보고 original[100]으로 복구한다.

---

먼저 'a' ~ 'z' 문자열은 0 ~ 25로 치환이 가능하다.

이러면 char 비트는 0000 0000 [= 0] ~ 0001 1001 [= 25] 으로 바꿀 수 있다.

앞 3개의 bit는 사용되지 않기 때문에 압축이 가능하다.

 

예를 들어 'z' 'z' 'z'는 0 ~ 25로 치환 가능하므로 26진법을 이용하여 아래와 같이 표현할 수 있다.

→ 25 * 26² + 25 * 26¹ + 25 * 26⁰ = 25 * 676 + 25 * 26 + 25 * 1 = 17575가 된다.

 

따라서 'z' 'z' 'z'는 17575 ( < 65536 ) → 2비트로 표현이 가능하다.

 

실제 src를 dest로 압축하는 구현은 아래와 같다. 

unsigned short changeInt
	= table[src[s]] * 676 + table[src[s + 1]] * 26 + table[src[s + 2]];

dest[d++] = changeInt >> 8;
dest[d++] = changeInt & 0xff;

table['a'] = 0, table['z] = 25가 된다.

 

이제 dest를 다시 src로 돌려보자.

2개의 비트를 이전에 했던 연산을 역으로 하면 아래와 같이 되돌릴 수 있다.

unsigned short changeChar = 0;
changeChar = dest[d++] << 8;
changeChar |= dest[d++];

 

26진법으로 3번 연산해주면 원래대로 복구할 수 있다.

src[s] = changeChar / 676 + 'a';
src[s + 1] = changeChar % 676 / 26 + 'a';
src[s + 2] = changeChar % 26 + 'a';

 

전체 코드는 다음과 같다.

#include <stdio.h>

unsigned char original[100];
unsigned char temp[67];

int mystrcmp(unsigned char *a, unsigned char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

void compress(unsigned char* src, unsigned char* dest)
{
	char table['z' + 1];
	for (int i = 'a'; i <= 'z'; i++) table[i] = i - 'a';

	int s, d;

	s = d = 0;

	for (s = 0; s < 99; s += 3)
	{
		unsigned short changeInt
			= table[src[s]] * 676 + table[src[s + 1]] * 26 + table[src[s + 2]];

		dest[d++] = changeInt >> 8;
		dest[d++] = changeInt & 0xff;
	}

	dest[d] = 0;
}

void decompress(unsigned char* dest, unsigned char* src)
{
	int s, d;

	s = d = 0;

	for (s = 0; s < 99; s += 3)
	{
		unsigned short changeChar = 0;
		changeChar = dest[d++] << 8;
		changeChar |= dest[d++];

		src[s] = changeChar / 676 + 'a';
		src[s + 1] = changeChar % 676 / 26 + 'a';
		src[s + 2] = changeChar % 26 + 'a';
	}

	src[99] = 0;
}

int main()
{	
	unsigned char problem[100] = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstu";

	int len;
	for (len = 0; problem[len]; len++);

	for (int i = 0; i < len; i++) original[i] = problem[i];

	compress(original, temp);

	for (int i = 0; i < len; i++) original[i] = 0;

	decompress(temp, original);

	printf("%s\n", original);
	if (mystrcmp(problem, original) == 0) printf("PASS!!\n");
	else printf("FAIL!!\n");

	return 0;
}

---

응용

 

'a' ~ 'z'만 사용하는 문자열이라면 0 ~ 25로 표현이 가능하기 때문에 최대 17575로 변형이 가능했다.

→ 25 * 26² + 25 * 26¹ + 25 * 26⁰ = 25 * 676 + 25 * 26 + 25 * 1 = 17575

 

이 방식대로라면 40진법까지는 해결할 수 있다.

→ 39 * 40² + 39 * 40¹ + 39 * 40⁰ = 39 * 1600 + 39 * 40 + 39 * 1 = 63999

 

63999는 unsigned short 최대값인 65535보다 작기 때문에 마찬가지로 압축이 가능하다.

 

위의 문제를 변형하여

 

'0' ~ '9' (10개) 

+ 'a' ~ 'z' (26개)

+ [ '+', '-', '/', '*' ] (4개) = 40개의 문자로 이루어진 문자열을 압축해보자.

 

각각의 문자는 아래의 숫자로 치환된다.

 

'0' ~ '9' → 0 ~ 9

'a' ~ 'z' (26개) → 10 ~ 35

[ '+', '-', '/', '*' ] → 36 ~ 39

 

따라서 table을 아래와 같이 바꿀 수 있다.

char table[256];

for (int i = '0'; i <= '9'; i++) table[i] = i - '0';
for (int i = 'a'; i <= 'z'; i++) table[i] = i - 'a' + 10;
	
table['+'] = 36;
table['-'] = 37;
table['/'] = 38;
table['*'] = 39;

 

decompress에는 복구를 위한 table을 아래와 같이 만든다.

char table[256];

for (int i = 0; i <= 9; i++) table[i] = i + '0';
for (int i = 10; i <= 35; i++) table[i] = 'a' + i - 10;

table[36] = '+';
table[37] = '-';
table[38] = '/';
table[39] = '*';

 

전체코드는 다음과 같다.

#include <stdio.h>

unsigned char original[100];
unsigned char temp[67];

int mystrcmp(unsigned char *a, unsigned char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

void compress(unsigned char* src, unsigned char* dest)
{
	char table[256];

	for (int i = '0'; i <= '9'; i++) table[i] = i - '0';
	for (int i = 'a'; i <= 'z'; i++) table[i] = i - 'a' + 10;
	
	table['+'] = 36;
	table['-'] = 37;
	table['/'] = 38;
	table['*'] = 39;

	int s, d;

	s = d = 0;

	for (s = 0; s < 99; s += 3)
	{
		unsigned short changeInt
			= table[src[s]] * 1600 + table[src[s + 1]] * 40 + table[src[s + 2]];

		dest[d++] = changeInt >> 8;
		dest[d++] = changeInt & 0xff;
	}

	dest[d] = 0;
}

void decompress(unsigned char* dest, unsigned char* src)
{
	char table[256];

	for (int i = 0; i <= 9; i++) table[i] = i + '0';
	for (int i = 10; i <= 35; i++) table[i] = 'a' + i - 10;

	table[36] = '+';
	table[37] = '-';
	table[38] = '/';
	table[39] = '*';

	int s, d;

	s = d = 0;

	for (s = 0; s < 99; s += 3)
	{
		unsigned short changeChar = 0;
		changeChar = dest[d++] << 8;
		changeChar |= dest[d++];

		src[s]     = table[changeChar / 1600];
		src[s + 1] = table[changeChar % 1600 / 40];
		src[s + 2] = table[changeChar % 40];
	}

	src[99] = 0;
}

int main()
{	
	unsigned char problem[100] = "abcdefghijklmnopqrstuvwxyz0123456789+-/*abcdefghijklmnopqrstuvwxyz0123456789+-/*abcdefghijklmnopqrs";

	int len;
	for (len = 0; problem[len]; len++);

	for (int i = 0; i < len; i++) original[i] = problem[i];

	compress(original, temp);

	for (int i = 0; i < len; i++) original[i] = 0;

	decompress(temp, original);

	printf("%s\n", original);
	if (mystrcmp(problem, original) == 0) printf("PASS!!\n");
	else printf("FAIL!!\n");

	return 0;
}

---

주의

 

압축을 할 때는 unsigned char 형태를 유지해야한다.

아래 코드를 실행해보자.

#include <stdio.h>

template <typename T>
void printBitNumber(T number)
{
	unsigned int bitSize = sizeof(number) * 8;
	T mask = (1ull) << (bitSize - 1);

	printf("%d", (number & mask) == mask);

	mask = (1ull) << (bitSize - 2);
	for (int i = 1; i < bitSize; i++)
	{
		printf("%d", (number & mask) == mask);
		mask >>= 1;
		if (i % 8 == 7) printf(" ");
	}
	putchar('\n');
}

int main()
{	
	char a = 128;
	unsigned char b = 128;

	int c = a << 1;
	int d = b << 1;

	printBitNumber(c);
	printBitNumber(d);

	printf("%d %d\n", c, d);

	return 0;
}

 

unsigned char인 b는 의도대로 비트연산이 이루어졌지만, char a는 1이 앞으로 채워지게 된다.

따라서 위의 문제는 모두 unsigned로 가정하였다.