제 7 장 어휘분석과 불용어목록 7.2 어휘분석 7.2.1 자동색인작업을 위한 어휘분석 어휘분석: 입력된 문자들을 단어 또는 토큰열로 변환하는 과정 토큰(token): 의미있는 문자들의 모임 자동색인의 첫 단계이자 질의 처리의 첫(기본) 단계 7.2 어휘분석 7.2.1 자동색인작업을 위한 어휘분석 고려사항: 토큰(단어)을 무엇으로 표현? 예)문자들의 모든 결합 문제가 되는 문자들 숫자: 대개 포함 안시킴 (예외) 법령, 기술 DB (B6, ...) 하이픈: state-of-the-art, F-16,... (조회율<->정확도) 구두점: COMMAND.COM, OS/2,... 대소문자: 대개 하나로 통일 (예외) 몇몇 PL

7.2.2 질의처리에 대한 어휘분석 7.2.3 어휘분석 비용 예) 토큰 시작은 숫자가 아니고, 영문자는 모두 소문자로 하고, 구두점/공백/제어문자는 모두 토큰 구별자로 취급 7.2.2 질의처리에 대한 어휘분석 앞 절과의 차이 연산자(논리, 절단, 가중치)/표식자(괄호) 추가 특수 문자(구두점, 제어문자) 처리에 비중 여기서는 토큰 구분자가 아니라 ‘오류’로 처리 토큰: (, ), &, |, ^, ..., 알파벳으로 시작하는 문자열 7.2.3 어휘분석 비용 많이 듬: 전체 IR 시스템 비용의 약 50% (모든 문자 조사)

7.2.4 어휘분석기의 구현 compiler의 어휘분석기(lexical analyzer)와 동일 구현 방법 1. 자동 생성(Unix의 ‘lex’) 어휘분석기가 복잡한 경우에 유리 2. 특정 알고리즘 사용 (수작업) 가장 나쁜 방법: 오류 가능성, 처리 효율 3. ‘유한 상태 기계(오토마타)’ 작성 (수작업) 본 교재에서 채택하고 있는 방법

유한 상태 기계-DFA(상태변이도)의 구현 (그림 7.1) 일련의 문자열 입력으로부터 ‘토큰’을 구분하는 것이 목적 자료구조: 문자(character) 분류, 토큰(token) 분류 128개 “ASCII문자”를 10가지로 분류 CharClassType: 10가지 문자 종류 정의(열거형) 배열 char_class[c]: 128가지 문자를 10가지로 분류 TokenType: 8가지 토큰(token) 종류 정의(열거형) 코드 int main( argc, argv ) 입력 화일 open -> GetToken 호출 -> 결과 출력 static TokenType GetToken( stream, term ) stream(화일)의 각 문자로부터 1개의 토큰 인식 & return 현 상태 유지, 상태 변환(transition) 결정: 변환 테이블 unget 함수 사용: 미리 읽은 문자/숫자 복원 분석기의 출력은 파서(parser)의 입력으로 사용됨

typedef enum { WHITE_CH, DIGIT_CH, LETTER_CH, LFT_PAREN_CH, RGT_PAREN_CH, AMPERSAND_CH, BAR_CH, CARET_CH, EOS_CH, OTHER_CH } CharClassType static CharClassType char_class[128] = { .... /* 9 */ DIGIT_CH, /* ; */ OTHER_CH, ... ... /* K */ LETTER_CH, /* L */ LETTER_CH, ... /* | */ BAR_CH, ... } Term_Token = 1, LEFT_PAREN_TOKEN = 2, RGT_PAREN_TOKEN = 3, AND_TOKEN = 4, OR_TOKEN = 5, NOT_TOKEN = 6, END_TOKEN = 7, NO_TOKEN = 8, } TokenType;

/** 변환 테이블 state | White Letter ( ) & | * EOS digit other 0 | 0 1 -2 -3 -4 -5 -6 -7 -8 -8 1 | -1 1 -1 -1 -1 -1 -1 -1 1 -1 **/ static ToknType GetToken( stream, term ) FILE *stream; char *term; { int next_ch, state, i; state = 0, i = 0; while ( 0 < state ) if (EOF == next_ch = getc(stream))) next_ch = ‘\0’; term[i++] = convert_case[next_ch]; switch( state ) case 0: switch( char_class[next_ch] ) case WHITE_CH : i = 0; break; case LETTER_CH : state = 1; break; case LFT_PAREN_CH : state = -2; break; case RGT_PAREN_CH : state = -3; break; case AMPESAND_CH : state = -4; break; case BAR_CH : state = -5; break; case CARET_CH : state = -6; break; case EOS_CH : state = -7; break; case DIGIT_CH : state = -8; break; case OTHER_CH : state = -8; break; default : state = -8; break; } break;

case 1 : if ( (DIGIT_CH != char_class[next_ch]) && (LETTER_CH != char_class[next_ch]) ) { ungetc ( next_ch, stream ); term[i-1] = ‘\0’; state = -1; } break; default : state = -8; break; return( (TokenType) (-state) ); int main(argc, argv) int argc; char *argv[]; TokenType token char term[128]; FILE *stream; if ( (2 != argc) || ! (stream = fopen(argv[1],”r”)) ) exit(1); do switch ( token = GetToken(stream, term) ) case TERM_TOKEN : (void)printf(“term: ... ... while ( END_TOKEN != token ); fclose ( stream );

7.3 불용어목록 불용어목록(stoplist) 색인용어로 가치가 없는(거의 사용되지 않는) 단어들 빈번히 발생하는 단어가 불용어일 확률이 높다(20~30%) 예) computer, program, machine, ...(컴퓨터 분야 내에서) 반례) time, war, home, life... 구현 (불용 단어의 추출) 1. 어휘분석 출력 후 모든 토큰에 대해 검사: 배열, 트리, ‘해시’... 2. 어휘분석의 한 부분 더 효과적, ‘어휘분석 생성기’로 불용어 목록 여과 어휘분석 생성기: 불용어목록을 검사하는 DFA를 생성 (그림 7.6, 그림 7.7)

create an initial state qi and label it with the input set L0; place q0 in a stae queue Q; while Q is not empty do: { remove state qi from Q; generate the derivative state labels from the label Li for q; for each derivative state label Lj with transition a: if no state qj labeled Lj exists, create qj and put it in Q; create an arc laeled a from qi to qj; } make all states whose label contains final states. 그림 7.6 유한 상태 기계를 생성하기 위한 알고리즘