본문 바로가기
알고리즘/[EXP] 삼성 SW 역량 테스트 C형

비트 압축 - 허프만 알고리즘 (Simple Huffman Coding Algorithm)

by 피로물든딸기 2023. 9. 2.
반응형

삼성 C형 전체 링크

 

참고

- 카드 섞기 알고리즘

- 비트 단위로 출력하기

- 33% 압축하기

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

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

- 허프만 알고리즘

 

320개의 'A', 160개의 'B', 80개의 'C', 40개의 'D',

그리고 10개의 'E', 'F', 'G', 'H'가 랜덤으로 분포된 크기 640의 배열이 있다.

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

int cnt = 0;
for (int i = 0; i < 320; i++) problem[cnt++] = 'A';
for (int i = 0; i < 160; i++) problem[cnt++] = 'B';
for (int i = 0; i < 80; i++) problem[cnt++] = 'C';
for (int i = 0; i < 40; i++) problem[cnt++] = 'D';
for (int i = 0; i < 10; i++) problem[cnt++] = 'E';
for (int i = 0; i < 10; i++) problem[cnt++] = 'F';
for (int i = 0; i < 10; i++) problem[cnt++] = 'G';
for (int i = 0; i < 10; i++) problem[cnt++] = 'H';

for (int i = 0; i < 100000; i++) /* N번 교환 */
{
	int a = rand() % 640;
	int b = rand() % 640;

	unsigned char tmp = problem[a];
	problem[a] = problem[b];
	problem[b] = tmp;
}

 

위 배열을 크기 160 바이트 배열에 압축하고 다시 복구해보자.

#include <stdio.h>
#include <stdlib.h> 
#include <time.h>

unsigned char original[640 + 1];
unsigned char temp[160 + 1];

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

#if 01
void compress(unsigned char* src, unsigned char* dest)
{

}

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

}
#endif

int main()
{	
	unsigned char problem[640 + 1] = { 0 };

	int cnt = 0;
	for (int i = 0; i < 320; i++) problem[cnt++] = 'A';
	for (int i = 0; i < 160; i++) problem[cnt++] = 'B';
	for (int i = 0; i < 80; i++) problem[cnt++] = 'C';
	for (int i = 0; i < 40; i++) problem[cnt++] = 'D';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'E';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'F';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'G';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'H';

	for (int i = 0; i < 100000; i++) /* N번 교환 */
	{
		int a = rand() % 640;
		int b = rand() % 640;

		unsigned char tmp = problem[a];
		problem[a] = problem[b];
		problem[b] = tmp;
	}

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


	int TIME = 0;
	clock_t start = clock();

	for (int tc = 0; tc < 100000; tc++)
	{
		compress(original, temp);

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

		decompress(temp, original);
	}

	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);
	
	printf("TIME : %d ms\n", TIME); /* ms 단위로 출력 */

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

	return 0;
}

허프만 압축 알고리즘 (Huffman Coding Algorithm)

 

허프만 압축 알고리즘은, 데이터의 빈도가 큰 문자나 기호를 짧은 비트로 표현하고,

낮은 빈도로 나타나는 경우는 큰 비트로 표현해서 전체 데이터를 압축한다.

 

위 예시의 경우라면

 

A = 1 

B = 01 

C = 001 

D = 0001

E = 000011 

F = 000010 

G = 000001

H = 000000 

 

로 표현할 수 있다.

 

예를 들어 1byte = 8bit가 0010111라면, AABC를 의미하게 된다.

4byte로 표현된 AABC를 1byte로 압축하게 되었다.

 

전체 640 byte의 문자를 위의 분포대로라면 160 byte로 압축할 수 있다.

 

이 문제는 빈도수가 정해져 있으므로, 허프만 트리는 구현하지 않는다.

구현

 

1 byte = 8 bit 메모리에 값을 비트 단위로 입력하기 위해 비트 마스크를 정의한다.

unsigned char mask[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

 

그리고 비트 단위로 입력하기 위한 인덱스를 정의한다.

int bitIdx = -1;

 

char 타입인 dest 배열에 비트 단위로 값을 쓴다.

bitIdx를 8로 나눈 값(>> 3)이 dest 배열의 위치를 설정하고, mask와 bitIdx가 해당 byte에서 bit에 값을 입힌다.

	for (int i = 0; i < 640;) 
	{
		unsigned char ch = src[i++];

		if (ch == 'A') // 1
		{
			bitIdx++;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'B') // 01
		{
			bitIdx += 2;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'C') // 001
		{
			bitIdx += 3;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'D') // 0001
		{
			bitIdx += 4;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'E') // 000011
		{
			bitIdx += 5;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
			bitIdx++;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'F') // 000010
		{
			bitIdx += 5;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
			bitIdx++;
		}
		else if (ch == 'G') // 000001
		{
			bitIdx += 6;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else // 000000  
			bitIdx += 6;
	}

 

비트 단위로 출력하는 코드를 추가해서 확인해 보자.

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

 

for문이 종료된 후, 원래 배열 src의 알파벳 14개를 출력하고, dest[0]은 4 byte로 한 번에 출력해보자.

	for (int i = 0; i < 14; i++) printf("%c ", src[i]);
	putchar('\n');
	printBitNumber(*(int*)&dest[0]);

 

char type의 dest[0 ~ 3]을 그림으로 그려보면 아래와 같다. 

 

보기 쉽게 거꾸로 뒤집어보자.

 

1비트가 연속된 구간은 'A'가 될 것이고, 이후 0의 개수에 따라 남은 알파벳이 결정된다.

 

위와 같이 값을 썼기 때문에, decompress는 아래와 같이 구현할 수 있다.

bitIdx를 증가시켜가며 mask를 이용해 첫 비트에 값이 있는 경우 'A'가 된다.

그렇지 않다면 다시 bitIdx가 증가되고, 해당 비트(두 번째 비트)에 값이 있다면 'B'로 판단할 수 있다.

void decompress(unsigned char* dest, unsigned char* src)
{
	unsigned char mask[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

	int bitIdx = -1;
	for (int s = 0; s < 640;) 
	{
		if      (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'A';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'B';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'C';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'D';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7])
		{						
			if  (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'E';
			else                                                 src[s++] = 'F';
		}
		else
		{
			if  (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'G';
			else                                                 src[s++] = 'H';
		}
	}
}

 

전체 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h> 
#include <time.h>

unsigned char original[640 + 1];
unsigned char temp[160 + 1];

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

#if 01
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 compress(unsigned char* src, unsigned char* dest)
{
	unsigned char mask[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

	int bitIdx = -1;
	for (int i = 0; i < 640;) 
	{
		unsigned char ch = src[i++];

		if (ch == 'A') // 1
		{
			bitIdx++;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'B') // 01
		{
			bitIdx += 2;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'C') // 001
		{
			bitIdx += 3;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'D') // 0001
		{
			bitIdx += 4;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'E') // 000011
		{
			bitIdx += 5;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
			bitIdx++;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else if (ch == 'F') // 000010
		{
			bitIdx += 5;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
			bitIdx++;
		}
		else if (ch == 'G') // 000001
		{
			bitIdx += 6;
			dest[bitIdx >> 3] |= mask[bitIdx & 7];
		}
		else // 000000  
			bitIdx += 6;
	}

	//for (int i = 0; i < 14; i++) printf("%c ", src[i]);
	//putchar('\n');
	//printBitNumber(*(int*)&dest[0]);
}

void decompress(unsigned char* dest, unsigned char* src)
{
	unsigned char mask[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

	int bitIdx = -1;
	for (int s = 0; s < 640;) 
	{
		if      (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'A';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'B';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'C';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'D';
		else if (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7])
		{						
			if  (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'E';
			else                                                 src[s++] = 'F';
		}
		else
		{
			if  (bitIdx++, dest[bitIdx >> 3] & mask[bitIdx & 7]) src[s++] = 'G';
			else                                                 src[s++] = 'H';
		}
	}
}
#endif

int main()
{	
	unsigned char problem[640 + 1] = { 0 };

	int cnt = 0;
	for (int i = 0; i < 320; i++) problem[cnt++] = 'A';
	for (int i = 0; i < 160; i++) problem[cnt++] = 'B';
	for (int i = 0; i < 80; i++) problem[cnt++] = 'C';
	for (int i = 0; i < 40; i++) problem[cnt++] = 'D';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'E';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'F';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'G';
	for (int i = 0; i < 10; i++) problem[cnt++] = 'H';

	for (int i = 0; i < 100000; i++) /* N번 교환 */
	{
		int a = rand() % 640;
		int b = rand() % 640;

		unsigned char tmp = problem[a];
		problem[a] = problem[b];
		problem[b] = tmp;
	}

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


	int TIME = 0;
	clock_t start = clock();

	for (int tc = 0; tc < 100000; tc++)
	{
		compress(original, temp);

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

		decompress(temp, original);
	}

	TIME += ((int)clock() - start) / (CLOCKS_PER_SEC / 1000);
	
	printf("TIME : %d ms\n", TIME); /* ms 단위로 출력 */

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

	return 0;
}
반응형

'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글

char 타입 배열을 다른 타입의 메모리로 사용하기  (0) 2023.08.26
타입 캐스팅으로 입력 빨리 받기, 비트 연산으로 메모리 압축하기  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈 with 36^5진법  (0) 2023.08.26
36진법 긴자리 두 수의 곱셈  (0) 2023.08.26

관련글

댓글

티스토리툴바