http://imjuni.springnote.com/pages/529741


저작자표시
http://coreapython.hosting.paran.com/tutor/tutfctnl.htm



저작자표시
http://www.kucuny.com/tc/55


저작자표시
[출처 : http://irgroup.org/zbxe/5022]



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를 사용했던 소스입니다만 윈도에서도 잘 돌아가네요.

저작자표시
[출처 : http://latest.tistory.com/entry/Dices-coefficient]


키워드간의 유사성을 측정하는 수학 공식이다.



nx  와 ny 에 대한 각 bigrams 의 개수를 구하고 그 중에 중복된 bigrams의 개수를 nt 라고 한다.

예를 들면 아래와 같다.

night => {ni,ig,gh,ht}
nacht  => {na,ac,ch,ht}

공식에 대입하면 아래와 같은 결과를 얻을 수 있다.

s = (2 · 1) / (4 + 4) = 0.25.


참고 url : http://en.wikipedia.org/wiki/Dice's_coefficient

저작자표시
[출처 : http://adnoctum.tistory.com/298]


   구글이나 네이버에서 검색을 할 때, 영어 단어를 '정확히' 입력하지 않았을 경우, '비슷한' 단어로 검색할 것을 추천하는 것을 본 경험이 있을 것이다. 그와 같이, 두 단어가 정확히 같은 것인가를 판단하는 것이 아니라, 대충 비슷한 것인가를 판단할 수 있는 방법을 살펴 보자. 즉, '비슷한 정도'를 수치화 할 수 있는 방법을 살펴 보자. 

   기본적인 아이디어는 단어를 잘게 자른 조각(그것을 shingle 이라 하자)들을 모은 후, 그 조각들이 많이 비슷하면 비슷할수록 두 단어가 비슷하다는 것이다. 예를 들어 보자. adenophorae radix  와  adenophora 를 비교하는 모습을 살펴 보자. 논의의 편의를 위하여 shingle 의 길이를 2 개로 제한하자. 

adenophorae radix --> ad
adenophorae radix --> de
adenophorae radix --> en
adenophorae radix --> op
...
adenophorae radix --> di
adenophorae radix --> ix

따라서 adenophorae radix 의 shingle 은 { 'ad', 'de', 'en', ..., 'ix' } 가 된다. 같은 식으로 adenophora 에 대한 shingle도 구할 수 있다. 주어진 단어에 대한 shingle 의 집합을 S라 하자. 즉,

S('adenophorae radix', 2) = { 'ad', 'de', 'en', ..., 'ix' },
S('adenophora', 2) = { 'ad', ..., 'ra' }

가 된다. 쉽게 생각을 해보자. 위와 같이 shingle 을 정의한 상태에서, 두 단어가 '비슷하다'면? 즉, 두 집합이 비슷하다면? 그렇다면 두 집합을 교집합 시킨 것과 합집합 시킨 것이 유사할 것이다. 즉 두 집합 A 와 B에 대하여 

n( A ∩ B ) ≒ n( A ∪ B )

일 것이다. 다시 표현하면, 

n( A ∩ B ) ÷ n( A ∪ B ) ≒ 1.0

일 것이다. 따라서, 위의 경우에 대하여, resemblance R 을, 

R(A,B) = n( A ∩ B ) ÷ n( A ∪ B )    --------------------------------- (1)

로 정의하면, 우리가 생각하는 것을 수학적으로 적절히 표현할 수 있게 된다. 극단적인 경우, R(A,A) = 1.0 인 것이다. 위 식을 C++ 코드로 간단히 표현해 보자. 

접기

std::set<std::string> get_shingle(const std::string& str, int size)

{

        std::set<std::string> shingle;

        int length = (int)(str.size());

        int max_pos = length - size;

        int i = 0;

        for(i = 0; i<=max_pos; i++){

                shingle.insert(str.substr(i, size));

        }

        return shingle;

}

 

bool get_resemblance(

const std::string& str1, 

const std::string& str2, 

double *r, double *c1, double *c2)

{

        std::set<std::string> s1 = get_shingle(str1, 2);

        std::set<std::string> s2 = get_shingle(str2, 2);

        if(s1.empty() == true || s2.empty() == true) return false;

        std::set<std::string> com;

        std::set<std::string> all;

        std::set_intersection(s1.begin(), s1.end(), 

s2.begin(), s2.end(), 

std::inserter(com, com.begin()));

        std::set_union(s1.begin(), s1.end(), 

s2.begin(), s2.end(), 

std::inserter(all, all.begin()));

 

 

        double com_size = (double)(com.size());

        double union_size = (double)(all.size());

 

        *r = com_size/union_size;

        *c1 = com_size/s1.size();

        *c2 = com_size/s2.size();

 

        return true;

}


(최대한 명시적 코드를 작성하기 위해 성능은 거의 고려하지 않음)

접기




get_shingle 함수는 주어진 단어를 주어진 길이로 자른 조각 집합을 반환해 준다. get_resemblance 함수는 위의 식에 따라 계산한 값들을 반환한다. containment, 즉, 한 단어가 다른 단어에 '포함'되어 있는가 역시 '비슷한' 단어가 포함되어 있는가로 생각해 볼 수 있고, 쉽게 계산할 수 있다. get_resemblance 함수는 containment 까지 반환한다. 위 코드로 adenophorae radix 와 adenophora 의 resemblace 와 containment 를 구해 보면, 

resemblance : 0.642857 
containment of 'adenophora' in 'adenophorae radix' : 1.0
containment of 'adenophorae radix' in 'adenophora' : 0.642857

가 나온다. 어느 정도 합당한 값으로 보인다. 


위의 알고리즘은 Syntactic Clustering of the Web(pdf임)에서 소개된 것으로, 인터넷에서 두 '문서'의 유사도를 계산하기 위하여 제안된 것이다. 위처럼 결과적으로 방법은 간단해도 그것은 어느 정도 수학적으로 뒷받침된다. 본 문서에서는, 두 문서의 유사도를 계산할 때, shingle 을 섞은 후1 s 개를 선택해서 위의 식(1)처럼 계산하거나, m 번째 요소를 선택해서 식(1)처럼 계산하면 resemblance 에 대한 unbiased estimator 가 된다는 것이다. 또, shingle 은 자갈, 작은 돌, 로 해석할 수 있겠는데, 문서들을 단어들로 나눠서 단어들이 얼마나 비슷하게 본다는 개념에서 단어들을 '자갈'이라고 표현한 것이다. 하여튼 이와 같은 알고리즘을, 단어의 유사도를 찾기 위하여 나는 위처럼 다소 간단히 적용해 보았다. 음... 저 알고리즘을 적용해야 할 데이터가 결국은 사람이 눈으로 다시 한 번 확인을 해야만 하는 것이라서 대충 구현해도 되기 때문에... 




  1. 원래 문서에 permutation 으로 표현된 π 라는 operator 를 적용하는 것이 곧 배열을 무작위로 섞는 것을 의미한다.[본문으로]
저작자표시
[출처 : http://sp0ngee.tistory.com/51]


어느날 strtok() 함수의 메뉴얼 페이지를 보게 되었는데 다음과 같은 내용이 있었습니다.

버그
이 함수를 사용해서는 안된다. 만일 사용해야 한다면, 다음을 주의하라:
이 함수는 처음 인자를 수정한다.
구분자의 원본은 잃게 된다.
이 함수는 상수 문자열에서는 사용해서는 안된다.
strtok() 함수는 파싱하는 동안 정적 버퍼를 사용한다. 그래서 thread safe가 아니다. 만일 이것이 문제라면 strtok_r() 를 사용해라.

여기서 말하는 thread safe란 것은 여러 thread가 동시에 사용되어도 안전하단 말입니다.
thread safe에 대해서 더 자세히 알고 싶으시면 출처의 링크를 참고하시거나, 구글에서 검색해 보세요.
[ 'thread safe' 출처: http://kldp.org/node/36904 ]

그래서 앞으로 문자열 파싱을 할 일이 생기거든 strtok_r() 함수를 사용해 보려고 합니다.
머리가 좋지 못한 저는 여기에 정리해 놓고, 필요할 때 가져다 쓸려구요...-_ㅜ
혹시 필요하신 분들도 가져다가 사용하시길 바랍니다.

또한, 코드 내용 중에 잘못된 부분이나, 수정하면 더~ 좋은 프로그램이 되겠다라는 곳이 있으면 주저하지 마시고 답변 달아주세요! 다른 분들이 잘못된 정보를 알아가면 안되니까요. ^^

사용 예제를 보기 전에 간단하게 메뉴얼 페이지 내용을 적어봤습니다.

이름
strtok, strtok_r - 문자열에서 토큰들을 뽑아낸다.

사용법
#include <string.h>
char *strtok(char *s, const char *delim);
char *strtok_r(char *s, const char *delim, char **ptrptr);

설명
`토큰`이란 문자열 delim에 속하지 않는 문자들로 이루어진 비어 있지 않은 문자열이며 \0 이나 delim에 있는 문자가 뒤따른다.

strtok() 함수는 문자열 s를 토큰으로 파싱하기 위해 사용된다. strtok()의 첫번째 인자로 s를 주면, 가장 앞에 있는 토큰을 구하고, 그 문자열안의 다음 토큰을 구하고자 할 때에는 첫번째 인자를 NULL로 설정하여야 한다. 각 호출은 다음 토큰에 대한 포인터를 반환하거나 더이상  토큰이  발견되지  않는다면 NULL을 반환한다. 토큰이 구분자로 끝난다면, 이 구분자는 \0 로 겹쳐 쓰여지며 다음 문자에 대한 포인터가 strtok()에 대한 다음 호출을 위해 저장된다. 구분 문자열 delim는 각 호출 시 다를 수 있다.

strtok_r() 함수는 strtok() 와 동일하게 작동한다. 그러나 정적 버퍼를 사용하는 대신에 이 함수는 char * 포인터로 할당된 유저에 대한 포인터를 사용한다. 이 포인터, ptrptr 파라미터는 같은 문자열을 파싱하는 동안 같아야만 한다.

다음은 예제 소스코드 입니다.
01.#include <stdio.h>
02.#include <string.h>
03.#define DELIM "_"
04. 
05.int main(void)
06.{
07.char buf[] = "My_name_is_ubuntu";
08.char tmp[4][10] = {};
09.char *token;
10.char *ptr[2];
11.int i = 0;
12. 
13.token = strtok_r(buf, DELIM, &ptr[0]);
14.while( token )
15.{
16.strcpy(tmp[i], token);
17.token = strtok_r(tmp[i], DELIM, &ptr[1]);
18.while( token )
19.{
20.strcpy(tmp[i], token);
21.token = strtok_r(NULL, DELIM, &ptr[1]);
22.}
23.token = strtok_r(NULL, DELIM, &ptr[0]);
24.i++;
25.}
26. 
27.for(i=0; i<4; i++)
28.printf("tmp[%d]: %s\n", i, tmp[i]);
29. 
30.return 0;
31.}

실행 결과 입니다.




*참고로 delim은 delimiter의 약자입니다. 단어의 뜻은 '구분 문자'입니다.
이 단어는 자기 테이프 등에서 데이터의 시작(끝)을 나타내는 문자나 기호를 말합니다.
저작자표시
[출처 : http://www.jamsun2.com/zbxe/?mid=study&document_srl=94602&page=6&sort_index=readed_count&order_type=desc]


char* strtok(char* src, const char* delim)
{
  // src, delim 이 NULL 인지, delim 이 "" 인지 체크하는 코드는 생략
  char* tok;
  static char* next;     // 분석을 시작할 위치
  if (src != NULL)
    next = src;
  tok = next;

  // boundary condition check
  if (*next == '\0')
    return NULL;

  // 분석 시작
  for (; *next != '\0'; ++next)
  {
    if (*next in delim) // pseudo code
    {
      *next = '\0';
      ++next;
      break;
    }
  }

  return tok;
}



char* strtok(char* src, const char* delim, char** start)
{
  // src, delim 이 NULL 인지, delim 이 "" 인지 체크하는 코드는 생략
  char* tok;
  char* next;     // 분석을 시작할 위치. static 을 없애고 start 라는 입력
                  // 으로 초기화함
  if (src != NULL)
    next = src;
  else
    next = *start;

  // boundary condition check
  if (*next == '\0')
    return NULL;

  // 분석 시작
  tok = next;
  for (; *next != '\0'; ++next)
  {
    if (*next in delim) // pseudo code
    {
      *next = '\0';
      ++next;
      break;
    }
  }

  *start = next;
  return tok;
}

저작자표시

+ Recent posts

티스토리툴바