n-gram이란 입련된 문자열을 n개의 음절단위로 절단하는 방법입니다.
예를 들어 "정보검색" 이란 문자열을 절단할 때..
1-gram : 정, 보, 검, 색 으로 분리
2-gram : 정보, 보검, 검색 으로 분리
3-gram : 정보검, 보검색 으로 분리
...
^_^ 간단하죠?
이 방식은 초기 검색엔진들에서 키워드 추출하는 방식으로 많이 애용되었습니다.
단순한 방식과 빠른 키워드 추출로 인기가 좋았죠.
특히나 미국의 검색엔진들이 CJK(중국,일본,한국)의 언어들을 처리하기 위해 형태소분석기를 만들수 없는 상황에서 많이 애용되었습니다.
부산물로 "사오정검색"이란 단어가 생겨나기도 했구요.. "보검"을 검색하면 정보검색이 나타나니까요..
서론이 길어졌습니다.
다음은 소스코드입니다.
=============================================================================
/******************************************************************************
N-Gram module
화일명: ngram.h
작성자:
작성일: 2001.12.03
내 용:
******************************************************************************/
#ifndef __N_GRAM_H__
#define __N_GRAM_H__
#define MAX_N_GRAM_NUM 10
#define MAX_ONE_WORD_SIZE ((MAX_N_GRAM_NUM + 1) * 2)
#define MAX_N_GRAM_WORD 10000
#define MIN_N_GRAM_NUM 1
// n-gram을 사용하여 string을 분해한다.
int NGram(unsigned char *str, int min, int max, unsigned char value[][MAX_ONE_WORD_SIZE]);
// n-gram으로 분해된 term들에 대해 중복을 제거하고 중복 갯수를 저장한다.
// 중복갯수는 각 단어의 처음에 한바이트로 기입된다.
int AvoidDuplicationTerm4NGram(unsigned char value[][MAX_ONE_WORD_SIZE], int num);
#endif
/******************************************************************************
N-Gram module
화일명: ngram.c
작성자:
작성일: 2002.12.03
내 용:
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ngram.h"
/******************************************************************************
AvoidDuplicationTerm4NGram
N_Gram 함수로 stem된 term들의 중복 여부를 검사하여 중복된 term들을 배제시킨다.
이 때 value 변수의 각 단어들은 첫번째 바이트로 중복된 갯수를 가진다.
input : unsigned char value[][MAX_ONE_WORD_SIZE]
int num 현재 item의 갯수
output: unsigned char value[][MAX_ONE_WORD_SIZE]
return: 중복 배제시킨 term의 갯수
******************************************************************************/
int AvoidDuplicationTerm4NGram(unsigned char value[][MAX_ONE_WORD_SIZE], int num)
{
int cnt;
int i;
int j;
unsigned char tmp[MAX_ONE_WORD_SIZE];
strcpy(tmp, value[0]);
value[0][0] = 1;
strcpy(value[0] + 1, tmp);
for(i = 1, cnt = 1; i < num; i ++)
{
for(j = 0; j < cnt; j ++)
{
if(strcmp(value[i], value[j] + 1) == 0)
{
if(value[j][0] < 255)
value[j][0] ++;
break;
}
}
if(j == cnt)
{
strcpy(tmp, value[i]);
value[cnt][0] = 1;
strcpy(value[cnt] + 1, tmp);
cnt ++;
}
}
return cnt;
}
/******************************************************************************
NGram
입력된 문자열을 min~max 사이의 n-gram으로 절단한다.
ascii code 128글자와 한글(ksc5601)코드에 대한 지원만을 한다.
stem 된 각 term들의 최대 갯수는 10000개로 제한한다.
한글 stem시 2byte씩 한글자를 이루므로 한 단어에 대한 버퍼의 크기는 두배로
잡아야 한다.
한글 정보검색에서 사용할 때는 1-gram과 bi-gram을 사용하는 것이 효율상 바람직.
필요에 따라서는 3-gram도 적용해 볼만 함
대소문자 구별을 한다.
input : char *str
int min n-gram 시작값
int max n-gram 마지막값
output: char value[][MAX_ONE_WORD_SIZE]
return: value count
******************************************************************************/
int NGram(unsigned char *str, int min, int max, unsigned char value[][MAX_ONE_WORD_SIZE])
{
int cnt;
unsigned char *p;
unsigned char *src;
int i;
int j;
int start;
int end;
int nletter;
start = (min > 0) ? min : 1;
end = (max < MAX_N_GRAM_NUM) ? max : MAX_N_GRAM_NUM;
cnt = 0;
for(i = start; i <= end; i ++)
{
src = str;
while(*src)
{
p = src;
nletter = 0;
for(j = 0, nletter = 0; nletter < i && *p != 0; j ++)
{
// 한글인지 영문인지 검사
if(*p < 0x80)
{
// 제어문자일 경우 중지
if(*p <= 0x20)
break;
value[cnt][j] = *p;
p ++;
nletter ++;
}
else
{
value[cnt][j++] = *p++;
value[cnt][j] = *p;
p ++;
nletter ++;
}
/*
else if(*p >= 0xa1 && *p <= 0xfe) // 한글코드 영역이면
{
value[cnt][j++] = *p++;
value[cnt][j] = *p;
p ++;
nletter ++;
}
*/
}
if(nletter == i) // 정상 추출
{
value[cnt][j] = 0;
cnt ++;
// stem한 term의 갯수가 MAX_N_GRAM_WORD보다 크거나 같으면 종료
if(cnt >= MAX_N_GRAM_WORD)
break;
}
if(*src >= 0xa1 && *src <= 0xfe)
src += 2;
else if(*src < 0x80)
src ++;
else
src ++;
}
}
return cnt;
}
==============================================================================
Copy&Paste했더니 엉망이네요. 
리눅스에서 gnu c를 사용했던 소스입니다만 윈도에서도 잘 돌아가네요.