40. 회문 판별과 N-gram
1. 키워드
- 회문(Palindrome)
- N-gram
2. 회문 판별과 N-gram 만들기
- 문자열을 이용하여 회문을 판별하는 방법과 N-gram을 만드는 방법을 알아보자.
3. 회문 판별
- 회문은 다음과 같이 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말한다.
- 이제 문자열을 배열에 넣은 뒤 반복문으로 각 글자를 검사해 보자.
#define _CRT_SECURE_NO_WARNINGS // scanf 보안 경고로 인한 컴파일 에러 방지
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int main()
{
char word[30]; // 단어를 저장할 배열
int length; // 문자열 길이
bool isPalindrome = true; // 회문 판별값을 저장할 변수, 초깃값은 true
printf("단어를 입력하세요: ");
scanf("%s", word);
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;
}
// 단어를 입력하세요: level (입력)
// 1
// 단어를 입력하세요: hello (입력)
// 0
- 회문 판별에서 가장 중요한 부분은 문자열(단어)의 길이이다.
- 왜냐하면 회문 판별은 문자열의 길이를 기준으로 하기 때문이다.
- 이제 문자열 길이의 절반만큼만 반복하면서 왼쪽 문자와 오른쪽 문자들을 검사한다.
- 만약 문자열의 길이가
5라면5 / 2 = 2(정수 나눗셈)이므로 가운데 글자 바로 앞까지만 검사하게 된다. - 반복문 안에서 왼쪽 문자
word[i]와 오른쪽 문자word[length - 1 - i]를 비교하여 문자가 다르면 회문이 아니므로isPalindrome에false를 넣어주고 반복문을 끝낸다. - 어차피 회문이 아니기 때문에 더 검사할 필요가 없다.
// 0부터 문자열 길이의 절반만큼 반복
for (int i = 0; i < length / 2; i++)
{
// 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
if (word[i] != word[length - 1 - i])
{
// 회문이 아님
isPalindrome = false;
break;
}
}
for반복문의i가0부터1씩 증가하므로word[i]는 왼쪽에서 오른쪽으로 진행하고,word[length - 1 - i]는 오른쪽에서 왼쪽으로 진행한다.- 즉, 문자열의 마지막 문자는
word[length - 1]이므로 여기서 인덱스를i만큼 계속 빼주면 오른쪽에서 왼쪽으로 진행하게 된다.
4. N-gram 만들기
- N-gram은 문자열에서 N개의 연속된 요소를 추출하는 방법이다.
- 만약
"Hello"라는 문자열을 문자(글자) 단위 2-gram으로 추출하면 다음과 같이 된다.
- 즉, 문자열의 처음부터 문자열 끝까지 한 글자씩 이동하면서 두 글자를 추출한다.
- 3-gram은 세 글자, 4-gram은 네 글자를 추출한다.
- 이제 C에서 문자 단위 2-gram을 출력해 보자.
#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
- 2-gram이므로 문자열의 끝에서 한 글자 앞까지만 반복하면서 현재 문자와 바로 그다음 문자 두 글자씩 출력한다.
- 만약 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이 아닌 단어 단위 N-gram도 있다.
- 다음은 문자열을 공백으로 구분하여 단어 단위 2-gram을 출력한다.
- 예를 들어
"this is c language"는"this is","is c","c language"가 된다.
#define _CRT_SECURE_NO_WARNINGS // strtok 보안 경고로 인한 컴파일 에러 방지
#include <stdio.h>
#include <string.h>
int main()
{
char text[100] = "this is c language";
char *tokens[30] = {
NULL,
}; // 자른 문자열의 포인터를 보관할 배열, NULL로 초기화
int count = 0; // 자른 문자열 개수
char *ptr = strtok(text, " "); // " " 공백 문자를 기준으로 문자열을 자름, 포인터 반환
while (ptr != NULL) // 자른 문자열이 나오지 않을 때까지 반복
{
tokens[count] = ptr; // 문자열을 자른 뒤 메모리 주소를 문자열 포인터 배열에 저장
count++; // 인덱스 증가
ptr = strtok(NULL, " "); // 다음 문자열을 잘라서 포인터를 반환
}
// 2-gram이므로 배열의 마지막에서 요소 한 개 앞까지만 반복함
for (int i = 0; i < count - 1; i++)
{
printf("%s %s\n", tokens[i], tokens[i + 1]); // 현재 문자열과 그다음 문자열 출력
}
return 0;
}
// this is
// is c
// c language
- 단어 단위 2-gram도 간단한데,
strtok함수로text를 자른 뒤 각 단어들을tokens배열에 넣는다.
char *ptr = strtok(text, " "); // " " 공백 문자를 기준으로 문자열을 자름, 포인터 반환
while (ptr != NULL) // 자른 문자열이 나오지 않을 때까지 반복
{
tokens[count] = ptr; // 문자열을 자른 뒤 메모리 주소를 문자열 포인터 배열에 저장
count++; // 인덱스 증가
ptr = strtok(NULL, " "); // 다음 문자열을 잘라서 포인터를 반환
}
- 2-gram이므로
tokens배열의 마지막에서 요소 한 개 앞까지만 반복하면서 현재 문자열과 그다음 문자열을 출력하면 된다.
// 2-gram이므로 배열의 마지막에서 요소 한 개 앞까지만 반복함
for (int i = 0; i < count - 1; i++)
{
printf("%s %s\n", tokens[i], tokens[i + 1]); // 현재 문자열과 그다음 문자열 출력
}
N-gram의 활용
- 예를 들어 4-gram을 쓰면
"picked","picks","picking"에서"pick"만 추출하여 단어의 빈도를 세는데 이용된다. - 이런 특성 때문에 검색엔진, 빅데이터, 법언어학 분야에서 주로 활용된다.