UNIT 47 회문 판별과 N-gram 만들기(문자열 응용) + 핵심정리

핵심정리

https://dojang.io/mod/page/view.php?id=733

 

회문은 유전자 염기서열 분석에서 많이 쓰고, N-gram은 빅 데이터 분석, 검색 엔진에서 많이 쓰임. 특히 구글은 책들을 스캔해서 N-gram viewer를 만들었는데 사람들의 언어 패턴을 시대별로 분석하기도 했음.

47.1 회문 판별

회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 뜻함.

ex) levele SOS rotator nurses run

회문은 첫 번째 글자와 마지막 글자가 같고, 안쪽으로 한글자씩 좁혔을때도 글자가 서로 같음.

즉, 가운데를 기준으로 왼쪽과 오른쪽의 문자가 같음.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 
#include <string.h>
#include <stdbool.h>


int main()
{
	char word[1000]; 
	bool isPalindrome = true; //회문 판별값을 저장할 변수, 초깃값은 true
	printf("단어를 입력하세요: ");
	scanf("%s", word);

	int length = strlen(word);

	// 0부터 문자열 길이의 절반만큼 반복
	for (int i = 0; i < length / 2; i++)
	{
		// 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
		if (word[i] != word[length - 1 - i])
		{
			//회문이 아님
			isPalindrome = false;
			break;
		}
	}
	
	printf("%d\n", isPalindrome); //회문 판별값 출력

	return 0;
	
}

만약 문자열 길이가 5라면 5/2 = 2(정수나눗셈) 이므로 가운데 글자 바로 앞까지만 검사하게 됨

47.2 N-gram 만들기

N-gram은 문자열에서 N개의 연속된 요소를 추출하는 방법

"Hello"라는 문자열을 문자(글자) 단위 2-gram으로 추출하면 다음과 같이 됨.

He
el
ll
lo

#include <stdio.h> 
#include <string.h>


int main()
{
	char text[30] = "Hello";
	int length;
	
	length = strlen(text); //문자열의 길이를 구함

	//2-gram이므로 문자열의 끝에서 한글자 앞까지만 반복함
	for (int i = 0; i < length - 1; i++)
	{
		printf("%c%c\n", text[i], text[i + 1]); //현재 문자와 그 다음 문자 출력
	}
	

	return 0;
}

실행결과
He
el
ll
lo

만약 3-gram이라면 조건식은 i < length - 2와 같이 되고, 문자열 끝에서 두 글자 앞까지 반복하면 됨. 문자열을 출력할 때는 printf("%c%c%c\n", text[i], text[i + 1], text[i + 2]);가 됨. 여기서 문자열의 끝까지 반복하면 text[i + 1], text[i + 2]는 문자열의 범위를 벗어난 접근을 하게 되므로 주의.

 

단어 단위 N-gram 

"this is c language"를 2-gram으로

#define _CRT_SECURE_NO_WARNINGS //strtok 보안 경고로 인한 컴파일 에러 방지
#include <stdio.h> 
#include <string.h>


int main()
{
	char text[100] = "this is c language";
	char *arr[100] = { NULL, }; //자른 문자열의 포인터를 보관할 배열, NULL로 초기화
	//왜 문자열 포인터에 저장해야하는걸까

	int count = 0; //자른 문자열의 개수

	char* ptr = strtok(text, " "); //" " 공백 문자를 기준으로 문자열을 자름, 포인터 반환

	while (ptr != NULL) 
	{
		arr[count] = ptr;
		count++;
		ptr = strtok(NULL, " ");
	}

	for (int i = 0; i < count - 1 ; i++)
	{
		printf("%s %s\n", arr[i], arr[i + 1]);
	}

	return 0;
	
}

 

읽을거리 | N-gram의 활용

4-gram을 쓰면 picked, picks, picking에서 pick만 추출하여 단어의 빈도를 세는데 이용됩니다. 이런 특성 때문에 검색엔진, 빅데이터, 법언어학 분야에서 주로 활용됩니다.