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

삼성 C형 전체 링크

 

참고

- 33% 압축하기

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

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

- 허프만 알고리즘

 

알파벳 'a' ~ 'z'로만 이루어진 문자열이 있다고 가정하자.

여기서는 char 1000 byte를 625 byte로 줄여보자.

 

즉, 아래의 문제를 풀어보자.

#include <stdio.h>

unsigned char original[1000 + 1];
unsigned char temp[625 + 1];

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[1000 + 1] = { 0 };

	for (int i = 0; i < 1000; i++) problem[i] = i % 26 + 'a';

	problem[1000] = 0;

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

	compress(original, temp);

	for (int i = 0; i < 1000; 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로 치환이 가능하다.

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

즉, 1byte의 8개 bit 중 5개의 bit만 쓰는 경우라면, 8byte를 5byte로 압축할 수 있다는 말이 된다.

따라서 이 문제의 압축률이 37.5%가 된다.

 

즉 문자열이 최대 32개까지 있는 경우는 앞 3개의 bit를 제거해서 37.5% 압축을 할 수 있다.

 

여기서는 일단 'a' ~ 'z'만 쓴다고 가정하자.

---

char 8 to 5, 5 to 8 구현

 

8개의 char 배열을 5개의 배열로 줄여보자.

void char8to5(unsigned char src[8], unsigned char dest[5])
{
	
}

 

만약 배열 s[0 ~ 7]이 들어온다면, a = 0 ~ z = 25로 변경한다.

그러면 이 배열은 아래의 그림처럼 보이게 된다. 

 

앞 부분의 3비트는 모두 필요 없으므로 d[0 ~ 5]까지를 꽉 채워넣을 수 있다.

 

위의 그림을 비트 연산을 이용해서 그대로 구현하면 아래와 같다.

printBitNumber로 비트가 그림대로 바뀌었는지 확인해보자.

void char8to5(unsigned char src[8], unsigned char dest[5])
{
	printf("src 8 >> dest 5\n");

	for (int i = 0; i < 8; i++) src[i] -= 'a';
	for (int i = 0; i < 8; i++) printBitNumber(src[i]);

	dest[0] = src[0] << 3;
	dest[0] |= ((src[1] >> 2));
	
	dest[1] = (src[1] << 6);
	dest[1] |= (src[2] << 1);
	dest[1] |= (src[3] >> 4);

	dest[2] = (src[3] << 4);
	dest[2] |= (src[4] >> 1);
	
	dest[3] = (src[4] << 7);
	dest[3] |= (src[5] << 2);
	dest[3] |= (src[6] >> 3);

	dest[4] = (src[6] << 5);
	dest[4] |= (src[7]);

	putchar('\n');

	for (int i = 0; i < 5; i++) printBitNumber(dest[i]);
}

 

역방향은 다음과 같다.

void char5to8(unsigned char dest[5], unsigned char src[8])
{
	printf("dest 5 >> src 8 \n");

	for (int i = 0; i < 8; i++) src[i] = 0;

	src[0] = (dest[0] >> 3);
	src[1] = ((dest[0] & 0x07) << 2) | (dest[1] >> 6);
	src[2] = ((dest[1] >> 1) & 0x1F);
	src[3] = ((dest[1] & 0x01) << 4) | (dest[2] >> 4);
	src[4] = ((dest[2] & 0x0F) << 1) | (dest[3] >> 7);
	src[5] = ((dest[3] >> 2) & 0x1F);
	src[6] = ((dest[3] & 0x03) << 3) | (dest[4] >> 5);
	src[7] = (dest[4] & 0x1F);

	for (int i = 0; i < 8; i++) printBitNumber(src[i]);
	for (int i = 0; i < 8; i++) src[i] += 'a';
}

 

전체 코드는 다음과 같다.

#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');
}

void char8to5(unsigned char src[8], unsigned char dest[5])
{
	printf("src 8 >> dest 5\n");

	for (int i = 0; i < 8; i++) src[i] -= 'a';
	for (int i = 0; i < 8; i++) printBitNumber(src[i]);

	dest[0] = src[0] << 3;
	dest[0] |= ((src[1] >> 2));
	
	dest[1] = (src[1] << 6);
	dest[1] |= (src[2] << 1);
	dest[1] |= (src[3] >> 4);

	dest[2] = (src[3] << 4);
	dest[2] |= (src[4] >> 1);
	
	dest[3] = (src[4] << 7);
	dest[3] |= (src[5] << 2);
	dest[3] |= (src[6] >> 3);

	dest[4] = (src[6] << 5);
	dest[4] |= (src[7]);

	putchar('\n');

	for (int i = 0; i < 5; i++) printBitNumber(dest[i]);
}

void char5to8(unsigned char dest[5], unsigned char src[8])
{
	printf("\ndest 5 >> src 8 \n");

	for (int i = 0; i < 8; i++) src[i] = 0;

	src[0] = (dest[0] >> 3);
	src[1] = ((dest[0] & 0x07) << 2) | (dest[1] >> 6);
	src[2] = ((dest[1] >> 1) & 0x1F);
	src[3] = ((dest[1] & 0x01) << 4) | (dest[2] >> 4);
	src[4] = ((dest[2] & 0x0F) << 1) | (dest[3] >> 7);
	src[5] = ((dest[3] >> 2) & 0x1F);
	src[6] = ((dest[3] & 0x03) << 3) | (dest[4] >> 5);
	src[7] = (dest[4] & 0x1F);

	for (int i = 0; i < 8; i++) printBitNumber(src[i]);
	for (int i = 0; i < 8; i++) src[i] += 'a';
}

int main()
{	
	unsigned char a[9] = "axcrztkj";
	unsigned char b[5];
	
	char8to5(a, b);

	for (int i = 0; i < 9; i++) a[0] = 0;

	char5to8(b, a);
	
	printf("%s\n", a);

	return 0;
}

---

이제 원래 문제인 1000개의 문자를 625개로 줄여보자.

모든 배열에 대해 char8to5와 5to8을 적용하면 된다.

void compress(unsigned char* src, unsigned char* dest)
{
	int destIndex = 0;
	for (int i = 0; i < 1000; i += 8)
	{
		char8to5(src + i, dest + destIndex);
		destIndex += 5;
	}
}

void decompress(unsigned char* dest, unsigned char* src)
{
	int srcIndex = 0;
	for (int i = 0; i < 625; i += 5)
	{
		char5to8(dest + i, src + srcIndex);
		srcIndex += 8;
	}
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

unsigned char original[1000 + 1];
unsigned char temp[625 + 1];

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 mystrcmp(unsigned char *a, unsigned char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

void char8to5(unsigned char src[8], unsigned char dest[5])
{
	for (int i = 0; i < 8; i++) src[i] -= 'a';

	dest[0] = src[0] << 3;
	dest[0] |= ((src[1] >> 2));
	
	dest[1] = (src[1] << 6);
	dest[1] |= (src[2] << 1);
	dest[1] |= (src[3] >> 4);

	dest[2] = (src[3] << 4);
	dest[2] |= (src[4] >> 1);
	
	dest[3] = (src[4] << 7);
	dest[3] |= (src[5] << 2);
	dest[3] |= (src[6] >> 3);

	dest[4] = (src[6] << 5);
	dest[4] |= (src[7]);
}

void char5to8(unsigned char dest[5], unsigned char src[8])
{
	for (int i = 0; i < 8; i++) src[i] = 0;

	src[0] = (dest[0] >> 3);
	src[1] = ((dest[0] & 0x07) << 2) | (dest[1] >> 6);
	src[2] = ((dest[1] >> 1) & 0x1F);
	src[3] = ((dest[1] & 0x01) << 4) | (dest[2] >> 4);
	src[4] = ((dest[2] & 0x0F) << 1) | (dest[3] >> 7);
	src[5] = ((dest[3] >> 2) & 0x1F);
	src[6] = ((dest[3] & 0x03) << 3) | (dest[4] >> 5);
	src[7] = (dest[4] & 0x1F);

	for (int i = 0; i < 8; i++) src[i] += 'a';
}

void compress(unsigned char* src, unsigned char* dest)
{
	int destIndex = 0;
	for (int i = 0; i < 1000; i += 8)
	{
		char8to5(src + i, dest + destIndex);
		destIndex += 5;
	}
}

void decompress(unsigned char* dest, unsigned char* src)
{
	int srcIndex = 0;
	for (int i = 0; i < 625; i += 5)
	{
		char5to8(dest + i, src + srcIndex);
		srcIndex += 8;
	}
}

int main()
{
	//for (char i = 0; i < 26; i++)
	//{
	//	printf("%c ", 'a' + i);
	//	printBitNumber(i);
	//}

	unsigned char problem[1000 + 1] = { 0 };

	for (int i = 0; i < 1000; i++) problem[i] = i % 26 + 'a';

	problem[1000] = 0;

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

	compress(original, temp);

	for (int i = 0; i < 1000; 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 형태를 유지해야 하는 것에 주의하자.