KR20020023543A - 자연어 검색 시스템을 위한 한글 스태머와 그 스태밍 방법 - Google Patents

Abstract

본 발명은, 온라인/오프라인 정보검색 시스템 및 웹 환경에서 자연언어 텍스트 데이터베이스에 대한 검색성능을 향상시키기 위해 정보검색 시스템의 주요 모듈로 구현한 한글 스태머 및 그 스태밍 방법을 제공한다.

스태머는, 불용어 제거루틴에 의해 자동적으로 불용어를 제거한 후, 나머지 자연어 형태의 텍스트를 자동 처리한다. 그 처리단계는 크게 2가지 단계로 구분된다. 첫째로, 규칙테이블1과 규칙테이블2와의 매칭을 행한 후, 적용 과정을 순환적으로 진행하고, 고정 어간길이를 적용하는 기본 처리단계와, 둘째로, 2차 처리단계로서 현재 처리되어야 할 자연어 음절조건에 따라 규칙테이블3, 규칙테이블4, 어간사전, 어미파일 등과의 매칭을 순환적으로 진행하면서 규칙을 적용하는 단계로 구분된다. 불규칙 활용조건에 따라서는 다시 쓰기 규칙이 적용되어 자연어 텍스트에서 출현하는 다양한 형태의 어미를 제거한다. 결과적으로, 다양한 곡용에 의하거나, 규칙 또는 불규칙 활용에 의해 발생하는 어미부분이 제거된 어간으로 구성된 텍스트를 생성한다. 본 발명은, 한국어 자연어 처리시에 데이터베이스 및 질의어에 출현하는 단어의 형태적 변이체(word variants)를 시스템에서 자동적으로 스태밍된 형태로 모아 줌으로써, 검색의 재현율 증가, 질의어 확장, 텍스트 클러스터링, 자연어 텍스트 데이터베이스의 압축효과를 갖는다.

Description

자연어 검색 시스템을 위한 한글 스태머와 그 스태밍 방법 {KOREAN LANGUAGE STEMMER FOR NATURAL LANGUAGE SEARCHING SYSTEM AND STEMMING METHOD THEREOF}

본 발명은, 온라인/오프라인 정보검색시스템 및 웹 환경에서 자연언어 텍스트 데이터베이스에 대한 검색성능을 향상시키기 위해 정보검색시스템의 주요 모듈로 구현한 한글 스태머(Korean Language Stemmer), 및 그 스태밍 방법에 관한 것이다.

자연어 검색 시스템에 있어서 색인 및 검색시에 발생하는 주요한 문제 중의 하나는, 텍스트 데이터베이스에서 동일한 의미를 전달하는 단어가 형태적 변이체(word variants)를 갖는다는 점이다. 일반적으로, 한국어에서 단어의 형태적 변이체는 단어가 구성되는 음운적(phonological) 조건과 형태적(morphological) 조건에 의해 생성된다.

본 스태머의 개발은, 텍스트의 변화를 가져오는 형태론적 조건을 고려하여 이루어졌다. 예컨대, 한국어에서 어간의 끝의 조건이나 어미 형태에 따라 도 11에 나타낸 바와 같이 동사의 규칙 또는 불규칙 활용, 명사의 준굴곡에 따라 다양한 변이체를 갖는다. 이것은, 검색시 질의어와 문헌의 색인어가 정확히 일치하지 않으면 적합한 레코드의 검색이 누락되어 재현수준의 저하를 초래한다.

또, 문헌의 적합성 순위에 따른 순위화된 출력을 제공하는 정보검색시스템에 있어서는, 문헌레코드 상에 출현한 형태적 변이체를 검색시에 시스템에서 모두 고려하지 않으면, 출력순위에 영향을 미쳐 검색의 정확도를 현저히 저하시킨다. 사용자 인터페이스에서는, 전문용어에 대한 지식이 제한적인 사용자가 자연언어 질의어를 사용하여 검색하였을 때, 질의어로 사용되는 자연어 형태에 따라 검색결과에차이를 가져온다.

이러한 문제를 해결하기 위해, 온라인 정보검색 시스템에서는 전형적으로 전문탐색자가 탐색식 작성시 탐색전략의 하나로 단어의 우측, 좌측, 양측 절단에 의한 탐색어를 질문식으로 작성하여 이를 탐색에서 사용하여 왔다. 그러나, 이 전략은 시스템에 의한 자동적 지원이 아닌 탐색자의 탐색 및 시스템 사용의 전문성이나 질문식 작성시에 사용하는 다양한 탐색전략에 따라 검색결과의 효과가 결정된다는 한계점을 갖는다.

상술한 바와 같이 통상의 정보검색 시스템에서는, 형태적 변이체를 갖고 출현하는 단어의 검색은 시스템의 색인어 매칭 알고리즘만으로는 해결되지 않는다.

본 발명에서 기초로 하는 가정은, 한 단어에서 의미적으로 유용한 정보는 어간 또는 어근에 존재하고, 어미의 변화는 단지 문법적인 목적을 위해 변화된다는 점이다.

본 발명은, 동일 어간의 변이체는 같은 의미를 전달하는 것으로 표층형태가 다른 한글 단어를 정보검색시스템에서 문헌에 대한 색인작성시, 탐색요구를 위해 자연어 형태의 질의어 작성시에 시스템이 자연어 텍스트 필드를 갖는 레코드와 사용자의 질의어에 대해 효과적으로 자동처리를 실행할 수 있는 한글 스태머 및 그 스태밍 방법을 제공하는 것을 목적으로 한다.

한글 스태머에서 어미란 한글단어에서 체언의 곡용에 따라 접미사와 조사가 사용되는 경우와, 용언 활용에 의해 생성되는 어미를 포함한다. 본 발명에 의한한글 스태머는, 시스템에 구현된 다양한 사전, 규칙 및 알고리즘을 사용하여 어간의 의미를 유지하고 다양한 어미를 제거하는 모듈로 구현되어 시스템에서 스태밍된 색인어를 자연어 정보검색에 사용하여 그 검색효과를 현저히 향상시킨다.

도 1은 본 발명에 따른 한글 스태머의 데이터흐름도,

도 2는 규칙테이블1의 구성예를 나타낸 도면,

도 3은 규칙테이블2의 구성예를 나타낸 도면,

도 4는 규칙테이블3의 구성예를 나타낸 도면,

도 5는 규칙테이블4의 구성예를 나타낸 도면,

도 6은 어간사전의 구성예를 나타낸 도면,

도 7은 어미파일의 구성예를 나타낸 도면,

도 8은 도 2의 규칙테이블1의 '도' 섹션의 예를 나타낸 도면,

도 9는 확장스태밍 1단계의 다시 쓰기 단계까지 진행한 후, 종료처리된 단어의 예를 나타낸 도면,

도 10은 본 발명에 따른 한글 스태머의 스태밍 알고리즘을 구체적으로 나타낸 도면,

도 11은 일반적인 형태적 변이체를 설명하기 위한 도면이다.

상기 목적을 달성하기 위해 본 발명에 따른 한글 스태밍 방법은, 자연어 한글 단어에 대한 스태밍을 하기 위해서 소정 종류의 문맥의존 규칙테이블을 설계하는 단계와, 상기 테이블을 시스템에서 순환적으로 호출하여 프로시쥬어에서 적용하는 단계를 구비하여 이루어진 것을 특징으로 한다.

또, 상기의 한글 스태밍 방법에 있어서, 다양한 불규칙 활용에 대한 처리를 위해서 어간사전 및 어미파일을 준비하는 단계를 더 구비하고, 조건에 따라 하나 이상의 매칭 방법을 적용하는 것을 특징으로 한다.

상기 매칭 방법은, 완전 매칭과 부분 매칭의 적어도 한쪽이다.

더욱이, 본 발명에 따른 한글 스태머는, 한글의 색인어 처리대상을 최소어간 길이 규칙을 적용하여 처리하는 처리수단과, 이 처리수단에 의해 처리된 색인어 처리대상을 현재 처리되어야 할 자연어 음절조건에 따라 소정의 규칙을 적용하여 처리하는 스태밍 수단을 구비하여 구성된 것을 특징으로 한다.

또, 상기의 한글 스태머에 있어서, 한글의 색인어 처리대상은 체언과 용언을 포함한다.

또, 상기 처리수단에서 적용하는 최소어간 길이 규칙이 고정어간 길이 규칙이고, 상기 스태밍 수단에서 적용하는 규칙이 문맥의존 어간길이 규칙이다.

(실시예)

본 발명의 실시예의 설명에 앞서, 본 발명이 청구하는 알고리즘에 포함되지는 않지만, 본 발명에 따른 스태머를 구동하기 전에 실행되는 불용어 제거루틴에 대해 참고적으로 설명하기로 한다.

불용어 제거루틴은, 본 발명의 알고리즘을 실행하기 전에 데이터베이스 탐색시에 적합한 정보를 검색하는데 유용하지 않을 것으로 시스템에서 예측된 단어 및 그 활용형태로 구성된 불용어 파일을 사용하여 본 발명에 따른 스태머를 구동하기 전에 질의어와 데이터베이스에서 제거하는 프로시쥬어이다. 이를 위해, 불용어 파일을 개발하고, 불용어 제거 프로그램을 작성하며, 불용어 제거 프로시쥬어를 호출하면 불용어 파일과 현재의 단어와를 비교하여 완전 매칭이 이루어진 단어를 삭제하는 알고리즘으로 구현되어 있다.

불용어 사전에 포함될 수 있는 후보 불용어의 수집을 위해 다음과 같은 정보원을 사용했다. 즉,

. 한글 문장의 부속성분에 속한 단어그룹

. 한국어 역순 사전에 수록된 해당 품사그룹에 포함된 단어그룹

. 기존 시스템의 불용어 파일의 참조

. 실험문헌 집단으로부터 추출된 후보 불용어

상기의 정보원으로부터 각 파일로 수집된 후보 불용어에서 중복 단어를 제외하고, 곡용 및 활용어미를 갖는 단어에 대해서는 각 용어에 포함되는 굴절형태를 모두 작성하여 최종적인 불용어 사전을 구성했다.

또, 후보 불용어 리스트로부터 최종 불용어로 선택하기 위해서, 다음과 같은 기준을 사용했다. 즉,

. 한글 문장의 부속성분에 속하는 부사, 관형사로서 무의미어: 어느, 저 등,

. 수사, 지정사, 보조동사, 대명사에 속한 단어: 하나, 없다, 아니하다, 그것이 등,

. 한글 문장의 주성분에 속한 품사영역의 단어이나, 주제어로서 유용성이 낮은 단어: 어르신, 여짭다, 저쑵다, 조렇다 등.

반면에, 문헌집단에서 낮은 출현빈도를 보이고 주제어로서의 의미가 적은 단어로서 다음과 같은 단어가 후보 불용어로서 고려될 수 있으나, 일반적인 이용목적의 불용어 사전을 위해 다음과 같은 단어는 불용어 사전에 포함시키지 않았다. 즉,

. 의미의 섬세한 변조나 표현방식에 따라 결정되는 단어유형: 뽀얗다, 보얗

다, 하얗다, 새하얗다, 길다, 기다랗다 등,

. 사물이나 사람의 움직임 강세에 따른 다양한 표현의 단어유형: 끌어안다,

얼싸안다 등,

. 한글문헌의 실험 결과, 한국어 문장에는 한국어 표기에 의한 다수의 한자어가 사용되고 있음을 나타내었고, 이들 중에는 다음의 예에서 보인 바와 같이 다수의 동음이의어가 포함되어 있다. 예컨대, 적(enemy: noun), 적(non content-bearing: suffix); 성(sex: noun), 성(non content-bearing: suffix); 때(time: noun), 때(dirt: noun); 안(inner side: noun), 안(knew: verb) 등이다. 이러한유형의 단어는 불용어 사전에 포함시키지 않았다.

결과적으로, 총 2,469개의 단어로 구성된 최종 불용어사전을 구성했고, 이 사전은 스태밍 알고리즘에서 분석대상 단어그룹으로부터 불용어 후보를 제외하는 루틴에서 사용된다.

이하, 예시도면을 참조하여 본 발명의 실시예를 상세히 설명한다.

본 발명에 따른 한글 스태머는, 1차 처리단계와 2차 처리단계인 확장 스태밍 단계로 구성되어 있다. 입력된 텍스트의 형태론적 표층형태의 규칙 또는 불규칙성에 따라 1차 처리과정만 거친 후에 처리된 결과의 음절을 검색엔진에서 사용할 수 있고, 입력단어가 형태가 복잡한 활용형태인 경우 한글 스태머가 구현한 모든 하부 프로시쥬어를 모두 거친 후에 최종 결과로서의 문자열이 생성되어 검색엔진에서 사용할 수 있다.

본 발명의 상세한 처리과정은 다음과 같다.

먼저, 자연어 형태의 문자열이 시스템에 입력되면, 입력된 단어가 불용어인지를 체크하기 위해 불용어 제거루틴이 불용어 파일을 사용하여 불용어를 삭제한다. 그리고, 불용어 제거루틴이 실행되고 남은 음절에 대해 한글 스태머의 처리단계가 진행된다.

1차 처리단계는, 기본적인 어미 제거루틴으로 규칙테이블1에서 어미가 매칭되면, 고정어간 길이조건을 만족하는 경우에 한하여 규칙테이블1에서 매칭된 규칙이 적용된다. 규칙테이블1을 구성하는 각 규칙은 역순형태의 어미, 제거대상 음절, 규칙테이블2의 활성화, 규칙 적용의 순환적(iterative) 진행 또는 작업종료 등을 나타내는 요소로 코드화되어 있다. 1차 처리단계에서 규칙테이블1의 적용단계가 종료하면, 문맥의존적 처리단계로서 규칙테이블2의 적용단계로 진행된다. 규칙테이블2 의 활성화는, 최초처리 단계에서 어미제거후 남은 어간이 시스템에서 정의한 조건, 즉 축약, 불규칙활용, 어간과 어미간에 또는 용언과 체언간에 음절의 표층형태가 동일한 경우 중 하나에 해당되는 경우로 규칙테이블2를 적용하여 과잉 스태밍 또는 과소 스태밍 결과가 초래되지 않도록 처리된다.

1차 처리단계에 의한 결과음절의 표층형태에 따라 한글 스태머는 확장 스태밍 단계로 진행된다. 확장 스태밍 단계는, 보다 복잡한 처리과정을 요하는 자연어 텍스트에 대해 시스템 알고리즘으로 구현된 조건의 체크와, 시스템에 구축된 다양한 사전의 조회, 다시 쓰기 규칙 등이 적용되어 정확한 스태밍 처리결과의 문자열을 생성한다. 확장 스태밍 단계에서는, 첫번째 단계로서 문맥의존적 최소어간 조건을 체크하여 시스템에서 정의된 다음의 3가지 경우중에 현재의 입력음절이 해당하는 루틴으로 진행한다.

입력음절이 1음절인 경우는, 규칙테이블3과의 매칭을 행한 후, 매칭된 규칙을 적용하여 결과를 찾아낸다. 반면에, 규칙이 탐색되지 않은 경우는, 시스템은 최종 처리결과로 현재의 입력음절을 출력하고, 작업을 종료한다.

기억장소에 있는 음절이 2음절인 경우는, 처리의 순서는 어간사전과의 매칭, 어미파일과 규칙테이블4와의 완전매칭, 규칙테이블5와의 매칭의 순서로 해당 조건에 만족되는 규칙을 적용하여 처리된다.

1차 처리루틴을 거친 후의 음절이 3음절 이상의 경우는, 현 문자열에서 1음절이 증가된 음절수에 해당하는 엔트리를 어간사전에서 부분 매칭기법을 이용하여 탐색을 진행한다. 부분 매칭이 된 엔트리가 탐색되면 현재 매칭된 엔트리에서 마지막 음절을 제외한 엔트리를 최종결과로서 출력하고, 부분 매칭에 실패하면 시스템은 현재의 단어를 최종결과로서 출력하게 된다.

다음에는 도 1을 참조하여 상술한 사용자 자연어 질의어 처리과정을 구체적인 예를 들어 상세히 설명하기로 한다.

본 발명의 스태머가 구현된 시스템에서 검색결과가 출력되기 까지의 질의어처리, 데이터베이스 텍스트 처리, 질의어에 대한 데이터베이스 탐색결과의 과정을 요약하면 다음과 같다.

＜질의어의 처리＞

단계 결과

<최초질의어> ‘멀티미디어나 하이퍼미디어의 개발에 관한, 또는 하이

퍼텍스트 저작을 위한 저작도구에 관한 연구는'

<불용어 제거> 멀티미디어나 하이퍼미디어의 개발에 하이퍼텍스트

저작을 저작도구에

<1차처리>

R1 멀티미디어나 하이퍼미디어에 개발에

하이퍼텍스트 저작을 저작도구에

R2 멀티미디 하이퍼미디 개발 하이퍼텍스트 저작

저작도구

<2차처리>

멀티미디 하이퍼미디 개발 하이퍼텍스트 저작 저작도구

＜데이터베이스상의 다양한 레코드의 처리＞

스태밍전(before stemming) 스태밍후(after stemming)

멀티미디어에서 멀티미디

멀티미디아도

멀티미디어에

멀티미디어인

하이퍼미디어로 하이퍼미디

하이퍼미디어가

하이퍼미디어의

하이퍼미디어로

하이퍼미디어는

하이퍼미디어보다

하이퍼미디어를

개발도 개발

개발하기

개발하여

개발하였고

개발하였는데

개발하였다

개발이지만

개발된

개발은

하이퍼텍스트에서만은 하이퍼텍스트

하이퍼텍스트로

하이퍼텍스트들간의

하이퍼텍스트로서

저작면에서 저작

저작용

저작하기에

저작임을

저작하기도

저작도구상의 저작도구

저작도구까지

저작도구를

저작도구조차도

저작도구들을

데이터베이스 탐색엔진의 구동시에, 접근할 데이터베이스의 각 텍스트 데이터 레코드는 불용어가 제외되고, 자연어 형태의 각 음절이 문장에서의 활용, 곡용을 위해 사용되었던 어미, 접미사, 조사 부분이 모두 처리되어 단어의 핵심의미만을 전달하는 어간으로서 저장되어 압축된 텍스트 데이터베이스를 구축한다.

한편, 질의어와 데이터베이스와의 매칭처리는 다음과 같이 이루어진다.

시스템 탐색시에, 사용자는 탐색시스템에서 지원하는 검색논리(예컨대, 불리언 논리)나 용어에 대한 탐색전략을 잘 알고 있지 못하더라도, 사용자가 일상생활에서 사용하는 형태의 자연어 탐색문을 입력하면, 이에 대해 시스템은 데이터베이스처리시 본 알고리즘에 의한 순환적 처리과정을 거쳐 사용자의 질의어 문장을 각 탐색어의 어간으로 구성된 문자열로 생성한다.

검색 프로시쥬어는, 질의어의 문자열에 일치하는 레코드를 데이터베이스로부터 매칭하여, 시스템에서 채택한 검색알고리즘을 사용하여 사용자가 가장 만족할 것으로 시스템이 예측하는 순서대로 검색된 결과집합을 출력한다.

이상의 설명은, 도 1에 의거 본 발명의 스태머의 동작을 상세히 설명하기 위해 실질적으로 이용가능한 질의어 ‘멀티미디어나 하이퍼미디어의 개발에 관한, 또는 하이퍼텍스트 저작을 위한 저작도구에 관한 연구는’에 대한 검색 예를 보인 것이다.

여기서, 예로 든 해당 질의어내에는 2차 처리의 3.2 단계까지 진행을 필요로 하는 단어가 포함되어 있지 않으므로, 2차 처리의 3.1 단계에서 ‘어간 사전’조회를 통하여 단어를 처리한 후, 이것이 최종형태이므로 이어서 검색프로시쥬어(<질의어와 데이터베이스와의 매칭>)로 진행하는 것을 기술한 것이다.

도 1에는 <데이터베이스 상의 다양한 레코드의 처리>가 없지만, 이 부분이 포함된 것은 본 발명의 알고리즘은 질의어의 텍스트를 처리할 뿐만 아니라 데이터베이스의 텍스트 레코드에 대한 처리를 진행하고, 처리된 질의어와 처리된 텍스트 데이터베이스와의 매칭을 통하여 최종 검색결과가 시스템으로부터 출력되기 때문이다.

다음에는 도 2∼도 5를 참조하여 규칙테이블1∼4의 구성예에 대해 설명한다.

규칙테이블1:

규칙테이블1에 있어서, 각 규칙은 다음의 4가지 요소로 구성되고, 그 예는 도 2에 나타낸 바와 같다.

- 체언의 곡용 또는 용언의 활용시 어간에 부가되는 어미로서 어미사전에 수록된 음절의 역순형태의 어미;

- 선택적으로 채택된 심볼 ‘>>’로서, 본 발명을 위해 조사된 98가지의 경우에 해당하는 어미에 한하여 부가되어 규칙테이블2의 활성화로 진행;

- 제거할 어미의 음절수를 나타내는 0에서 9까지의 숫자;

- 조건을 만족하는 경우에 한하여 규칙의 순환적 적용을 나타내는 심볼 ‘>’;

예1) 도라이지4>까>>

시스템에 입력되어 앞에서부터 순차적으로 읽은 음절이 R1 파일을 탐색하여 찾은 규칙에서 음절의 형태인 ‘도라이지까’와 완전히 일치하면, 처음부터 4음절 [8바이트(byte)]을 삭제하고, R2 파일을 활성화하여 R2 파일에서 ‘까’로 시작하는 규칙을 탐색하라.

예2) 도라이테한5>

입력된 단어의 음절이 R1에서 탐색된 규칙 ‘도라이테한’과 완전히 일치하면, 처음부터 5음절을 삭제한 후, 다시 R1을 활성화하여 삭제되고 남은 음절의 첫 음절과 R1과의 매칭을 계속하라.

규칙테이블2:

규칙테이블2에 있어서, 각 규칙은 다음의 5가지의 요소로 구성되고, 해당 규칙이 매칭되면, 규칙에서 지시한 조건을 체크한 후, 규칙에서 정의한 액션(action)이 해당 프로시쥬어에서 진행된다. 규칙테이블2의 예는 도 5에 나타낸 바와 같다.

- 역순형태의 어미 또는 어미와 어간의 축약형태;

- 제거할 어미의 음절수를 나타내는 0에서 9까지의 숫자;

- 어미 또는 축약형 어미의 첫음절 바로 앞의 음절수를 나타내는 심볼 ‘~’와 ‘!’;

- 규칙테이블의 다른 규칙 적용의 계속 또는 종료를 지시하는 심볼 ‘>’,‘>>’ 및 ‘.’;

- 어미제거 후 대체해야 할 하나 이상의 음절

예1) 라!1>

1차 처리에서 넘어온 단어의 음절중 첫음절이 ‘라’로 시작하고, ‘라’앞의 음절을 읽어 1음절(2byte) 이상인 조건을 만족하면, 현재 읽은 어절의 순차적 첫음절에 해당하는 ‘라’를 삭제하고, R1을 활성화하여 매칭을 계속하라.

예2) 시~0.

1차 처리에서 넘어온 단어 어절의 첫음절이 ‘시’와 일치하고, ‘시’음절 앞에 음절이 없으면, 현재 읽은 음절을 그대로 읽어 임시 기억장소에 저장하라.

규칙테이블3:

이 규칙테이블은, 한국어에서 체언 및 용언이 단음절의 어간을 갖는 어절을 한국어 사전 및 형태론에 관한 저서/보고서 등에서 설명되고 있는 이들의 규칙성과 불규칙성을 조사하여 하나의 텍스트 파일로 포맷한 것이다. 이는 본 발명에 따른 스태머가 과소스태밍, 즉 삭제할 음절이나 철자가 남아 있는 채로 종료하는 오류를 가질 확률을 최소화하기 위해 설계된 것이다. 본 파일은 총 716음절의 한국어 단음절 어간으로 구성되어 있다.

예) 헌1헐.

2차 처리단계(확장 스태밍)로 들어온 단어 어절의 첫음절이 ‘헌’과 일치하면, 읽은 현재의 음절 ‘헌’을 ‘헐’로 변환하여 임시 기억장소에 저장하고, 현재의 프로시쥬어를 종료하라.

규칙테이블4:

이 규칙테이블은, 한국어에서 서로 의미가 다른 어간(예컨대, 풀 solve; 푸 draw)을 갖는 어절임에도 불구하고, 어간이 어미나 접미사를 만날 때 그 활용 형태가 동일한 표층형태를 갖거나(예컨대, 풀 will solve ; 풀 will draw) 또는 어미에 따라 구별되는 형태를 갖는 경우가 발생한다(예컨대, 풀어서 solve and; 퍼서 draw and). 또는, 단어의 클래스가 전혀 달라(예컨대, 체언, 용언), 용언은 활용형태를 갖는 반면, 체언은 그 형태가 활용되지 않는 경우가 있다(풀 will draw; 풀 a gum).

예1) 러누1렇

2차 처리단계로 들어온 단어 어절을 순차적으로 읽어 첫 2음절(4byte)이 ‘러누’와 일치하면, 첫 2바이트에 해당하는 문자열만을 ‘렇’으로 변환한 후, 전체 음절(4byte)을 기억장소에 저장하고, 처리루틴을 종료하라.

예2) 러슬2르스

2차 처리단계로 들어온 단어 어절을 순차적으로 읽어 첫 2음절(4byte)이 ‘러슬’과 일치하면, 읽은 모든 문자열(4byte)을 ‘르스’로 변환한 후, 이 어절(4byte)을 기억장소에 저장하고, 처리루틴을 종료하라.

다음에는 도 7 및 도 8을 참조하여 어간사전 및 어미파일의 구성에 대해 설명한다.

먼저, 어간사전에 대해 설명한다.

이 어간사전은, 어간이 2음절 이상이 되는 단어가 전단계의 처리과정에서 과대스태밍, 즉 삭제해서는 안될 음절이 초과 삭제처리된 경우의 보완을 위해서, 또한 체언이 용언과 동일한 음절을 갖음으로써 용언처럼 처리되는 오류를 발생시키지 않기 위해서 설계된 것이다. 어간사전은 별도의 포맷을 하지 않고, 텍스트 파일로 구성되어 완전 매칭이 가능하도록 하고 있다. 다만, 한국어 복합어의 경우, 해당 복합어를 엔트리에 포함시키는 것 외에 하나의 복합어가 하나 이상의 어간으로 구성된 경우, 이들을 각각의 어간으로 간주하여, 이들 어절도 어간사전에 포함시켰다. 어간사전의 개략적인 예는 도 7에 나타낸 바와 같다.

어미파일은, 시스템에서 어미파일 단독으로는 사용되지 않고, 반드시 규칙테이블3과 함께 사용되므로 처리조건 탐색시 이들 2파일의 조건을 모두 만족하는 경우에 규칙테이블3에서 매칭된 규칙이 해당 프로시쥬어에서 적용된다. 어미파일의 예는 도 8에 나타낸 바와 같다.

다음에는 이들 규칙테이블이 어떻게 작성되고, 또 어떻게 적용되는지에 대해 상세히 설명하고, 더욱이 이들 규칙테이블의 구동에 대해서도 상세히 설명하기로 한다.

본 발명에 따른 한글 스태머 알고리즘의 구현시에, 입력된 단어의 형태적 특성에 따라 5개의 규칙테이블을 순차적으로 모두 사용할 수도 있고, 형태론적 특성이 복잡하지 않은 단어의 경우는 처리에 필요한 단계까지 진행한 후, 현재의 규칙에서 액션으로 처리종료 심볼을 만나면 작업을 종료한다. 매칭된 규칙테이블 상의 규칙 중에서 현재 단어의 형태적 조건과 매칭되는 규칙이 더 이상 없거나, 규칙에서 처리종료를 가리키는 경우에는 처리를 종료하고, 그렇지 않은 경우에는 최소어간 조건이 만족될 때까지 루틴을 계속 진행한 후, 현재의 기억장소에 저장된 단어를 최종 처리결과로서 출력한다.

시스템에서 규칙의 적용을 위해서 컴퓨터가 규칙데이블의 구조를 인식하여 프로그램에서 명령한 대로 구동될 수 있도록, 각 규칙은 C언어의 구조체 타입으로 정의된다. 선언부에서 각 규칙테이블의 구조를 정의하고, 프로그램의 각 하부루틴에서 규칙의 적용조건을 체크한다.

각 규칙테이블(R1, R2, R3, R4), 어간사전 및 어미파일은, 알고리즘의 해당 루틴에서 필요한 처리단계에 적용하기 위해 호출되면, 해당 규칙테이블, 또는 현재 단어의 조건에 따라 하나 이상의 규칙테이블에서 규칙이 탐색되어 조건에 맞는 규칙이 매칭되면 규칙에서 정의된 액션이 실행된다. 실행되는 액션의 종류는, 음절제거, 현재음절의 유지, 음절 다시 쓰기, 처리후 현재의 규칙에서 호출하는 규칙테이블의 활성화, 처리종료 등이다.

형태론적 특성이 복잡하지 않은 단어의 처리를 처리중에 사용한 규칙테이블 중의 하나인 도 8과 관련하여 설명하면 다음과 같다.

입력단어의 마지막 음절과 매칭된 해당 섹션(‘-도’)에서 해당 규칙을 탐색하여 다음과 같이 적용하는 것은, 알고리즘의 1차 단계에서 진행되는 주요한 특성을 보여준다. 즉, 입력된 3단어 ‘전동기라도’, ‘온도’, ‘난로도’에 대해 ‘전동기라도’는 후보어미 ‘-라도’중 어미 ‘-도’를 적용하여 삭제하고, 규칙테이블2가 활성화된 후, 확장 스태밍 단계에서 조건을 조사하며, ‘-라’를 적용하여 어간으로 ‘전동기’를 출력한다. 입력단어 ‘온도’는 어미 제거루틴에서 규칙이적용될 수 있는지 조건을 탐색하는 단계에서, 최소어간 길이조건이 만족되지 않으므로 입력단어의 형태변화 없이 ‘온도’로서 출력된다. 단어 ‘난로도’에 적용가능한 후보어미는 ‘-로도’와 ‘-도’이다. 그러나, 후보어미 ‘-로도’의 적용은 최소어간 길이조건에 맞지 않으므로, 어미 ‘-도’가 채택된다. 규칙테이블1에서 삭제대상 어미 ‘-도’의 적용은 1차 단계가 아닌 규칙테이블2의 활성화(>>)를 지시하므로, 확장 스태밍 단계에서 조건의 만족여부를 조사한 후, 단어 ‘난로도’에 대해 어미 ‘-도’를 삭제하여 어간으로 ‘난로’를 출력한다.

알고리즘의 2차 단계인 확장 스태밍 및 다시 쓰기 루틴은 규칙테이블2의 적용으로 진행되며, 분석대상 단어는 1차 단계에서 단어의 일부 음절이 제거된 형태이거나, 형태를 유지한 입력단어가 된다. 확장 스태밍 및 다시 쓰기 루틴에 포함되는 세부적인 단계는 다음과 같다.

- 규칙테이블2에서 단어의 마지막 음절과 일치하여 매칭된 섹션에 직접 접근 한 후, 후보 규칙을 탐색하기 위해 섹션내에서 순차적으로 분석대상 단어의 음절과 규칙의 음절과를 비교하며 완전히 일치한 규칙이 탐색될 때까지 진행한다.

- 규칙이 탐색되면, 규칙에서 현재의 음절 다음 위치의 문자를 체크한다.

- 다음 위치의 문자가 숫자인 경우는 규칙에서 지시한 수와 동일한 크기의 음절을 분석대상 단어로부터 제거하고, 심볼인 경우는 매칭된 현재 위치의 음절 바로 전 위치의 조건을 조사하여 조건이 만족되는 경우에만 규칙에서 지시된 수만큼의 음절을 삭제한다.

- 해당 어미의 삭제 후에, 규칙에서 대체할 음절이 있는지를 체크하고, 대체할 음절이 있으면 이를 현재의 위치에 삽입한다.

- 음절을 대체하고 난 후, 현재의 규칙에서 대체음절 다음 위치를 읽어 작업의 종료 또는 계속 여부를 결정하고, 스태밍의 순환적 진행은 다음 중 해당하는 경우를 진행하도록 한다. 즉,

1차 단계로 되돌아가 다음 단계의 규칙을 적용하여 과정을 진행하는 경우;

규칙테이블2의 다른 섹션의 탐색을 계속하여 확장 스태밍을 진행하는 경우;

현재 분석중인 단어에 대해 스태밍 작업루틴을 종료하여, 어미의 제거 및 다시 쓰기 과정을 거친 후 현재 남아 있는 음절을 어간으로서 출력하는 경우 등이다.

확장스태밍 1단계의 다시 쓰기 단계까지 진행한 후, 종료처리된 단어의 예는 도 9에 나타낸 바와 같다.

다음에는 도 10의 한글 스태머 알고리즘을 그 번호순서대로 상세히 설명한다.

1. 고정어간 길이의 조건(2음절)을 적용하여 알고리즘에서 규칙테이블 R1 과 R2를 사용하여 처리된 현재의 단어에 대해 현재의 음절수를 조사한다.

2. 현재 처리해야 할 음절수가 1인 경우(case a )에는, 다음 단계(도 10의 3)로 진행하여 해당 규칙테이블에서 매칭되는 규칙을 만나면 규칙을 적용한 결과를 출력하고, 해당 규칙테이블에서 매칭되는 규칙이 없으면 현재의 단어를 출력한다.

현재 처리해야 할 음절수가 2인 경우(case b)에는, 다음 단계(도 10의 3)로 진행한다.

현재 처리해야 할 음절수가 3 이상인 경우(case c)에는, 해당 단계(도 10의4)로 진행한다.

3. 전 단계에서 받아들인 단어와 순차적으로 다음과 같이 진행한다.

만일 받아들인 단어의 문자열과 어간사전과 매칭하여 어간사전 상의 엔트리와 완전 매칭을 하면, 현재의 단어를 가지고 해당 단계(도 10의 7)로 진행한다.

그렇지 않은 경우에는, 즉 받아들인 단어의 문자열과 일치하는 엔트리가 어간사전에 없는 경우에는, 규칙테이블3과 현재 음절의 두번째 철자와, 또한 어미파일과 현재 음절의 첫번째 철자와를 비교하여 이들 2조건이 모두 만족하면, 해당 단계(도 10의 5)로 진행한다.

만일 상기의 조건 중 어느 하나라도 만족하지 않으면, 현 음절의 문자열과 규칙테이블4와의 매칭을 시작한다. 매칭 결과, 규칙테이블4 상에서 해당 규칙이 발견되면, 다음 단계(도 10의 5)로 진행한다. 해당 규칙이 탐색되지 않으면 해당 단계(도 10의 7)로 진행한다.

4. 현재 처리해야 할 음절수가 3 이상이어서 전단계에서 받아들여진 경우에는, 어간사전과의 매칭을 시작한다. 현재 비교하는 음절과 완전 매칭하는 엔트리가 어간사전에 있으면 해당 단계(도 10의 7)로 진행하고, 그렇지 않으면, 즉 해당 엔트리가 없으면, 단계 6(도 10의 6)으로 진행한다.

5. 현재 비교하는 음절과 규칙테이블에서 규칙이 탐색되고, 이것이 규칙에서 정의한 액션으로 문맥의존적 조건을 갖는 규칙인 경우에는, 현재 문자열의 조건을 모두 조사하여 규칙에서 요구하고 있는 조건을 만족하는지를 체크하여(예컨대, 현재 철자 앞의 음절수, 음절형태, 현재 음절의 삭제여부, 현재 음절의 다시쓰기), 조건을 만족하면, 규칙을 적용하고 해당 어미를 삭제한다. 그리고, 해당 단계(도 10의 7)로 진행한다.

현재 매칭된 규칙이 문맥의존조건을 정의하지 않는 규칙이면, 비교하고 있는 음절을 삭제하고, 해당 단계(도 10의 7)로 진행한다.

6. 현재의 음절수가 3 이상(도 10의 4)이어서 루틴으로 이 단계를 호출한 경우에는, 어간사전에서 해당 엔트리의 탐색을 행하기 위해, 2가지 타입의 매칭, 즉 완전매칭이나 부분매칭에 의한 탐색을 시작한다. 먼저, 현재 음절수(3음절)와 완전히 일치하는 엔트리가 있는지 없는지 어간사전을 탐색한다. 엔트리가 탐색되면, 다음 단계(도 10의 7)로 진행한다. 만일 탐색되지 않았으면, 현재 음절수에 1음절을 더한 수를 현재 문자열의 음절수로 저장한 후, 현재 저장된 수의 음절수보다 1음절이 작은 부분까지만 문자열을 비교하는 부분매칭을 실행하고, 조건을 만족하면 매칭된 엔트리를 저장하고 이를 처리된 문자열로서 출력한다.

7. 현재까지 처리되어 최종결과로 저장된 음절을 출력하고, 루틴을 종료한다.

또한, 한국어에 있어서는, 각 음절이 조합되어 하나의 어절을 구성하는 가운데 다양한 음운 및 형태론적 조건에 따라 규칙 및 불규칙 활용, 음절의 축약, 체언과 용언간의 동음이의어, 단음절어의 불규칙 활용 등이 발생할 수 있다. 따라서, 이러한 특성을 고려하여, 규칙테이블의 각 규칙은 처리할 단어의 음절과 각 규칙의 시작 음절이 완전히 일치하더라도, 적용하기 전에 무조건적으로 현재 음절의 앞 음절의 조건, 현재 음절의 음절수, 용언과 체언간의 구별을 위해 설계된 규칙 등의조건을 먼저 체크하도록 구성하고 있다.

이와 같은 조건이 만족되면, 1차 처리단계에서 최소어간 조건을 체크한 후에 규칙테이블 상의 규칙을 적용하며, 2차 처리 단계에서는 현재 처리하는 단어의 음절수를 체크하여 각 조건에 따른 프로시쥬어를 진행하도록 설계되어 있다.

본 발명에서는, 한글 스태머의 구현시에 1차 처리단계에서는 고정어간길이를 적용하고, 확장 스태밍에 해당하는 2차 처리단계에서는 문맥의존 어간길이를 적용하도록 하고 있다.

고정어간 길이의 적용이란, 알고리즘은 입력되어 처리될 단어에 대해 조건을 만족하는 한 순환적으로 해당 루틴(recursive routine)을 호출하여 실행한다. 그 과정에서, 현재 처리를 위해 저장된 음절수가 2이면 순환적 루틴에서 빠져 나와 2차 처리단계로 진행하도록 설계되어 있다. 이러한 설계는, 한국어 체언 음절수의 통계적 특성을 반영하여 1차 처리단계에서 우선적으로 고정어간 길이를 적용하도록 한 것이다.

이후 진행되는 2차 처리단계에서는 문맥의존 어간길이를 적용하는데, 이는 현재 처리해야 할 음절수를 기준으로 하여 해당 프로그램 루틴으로 진행하되, 동일한 음절수라 하더라도 현재 처리할 음절이나 현재 음절의 앞 음절의 형태론적 조건을 먼저 조사하여 이 조건과 규칙에서 정의하고 있는 조건이 완전히 일치하는 경우에만 규칙에서 정의한 액션을 취하도록 한 것으로, 현재 처리하는 단어의 문맥의존적 조건은 전술한 바와 같이 규칙데이블에서 정의되어 있다.

본 발명의 한글 스태머는, 미국 코넬 대학에서 개발한 자연어검색시스템(SMART)의 한글버전을 구현하여 이 시스템의 색인 프로시쥬어로서 테스트를 함으로써, 표준검색효율의 현저한 증대를 통계적으로 검증한 바 있다. 즉, 한글 스태머를 사용한 검색과 사용하지 않은 검색과의 통계적 검증결과, 단측 검증 유의수준 0.05에서 검색의 평균재현율, 평균정확률이 모두 현저히 향상되고 있음이 확인되었다.

한편, 본 발명은 상술한 실시예에 한정되지 않고, 본 발명의 요지를 이탈하지 않는 범위내에서 여러 가지로 변형하여 실시할 수 있음은 물론이다. 예컨대, 본 발명에 따른 한글 스태머는, 현재 일반적으로 사용되고 있는 검색엔진 등에 탑재되어 사용될 수도 있다. 이 경우에도, 전술한 바와 같이 검색효율을 현저히 향상시킬 수 있다.

이상 설명한 바와 같이 본 발명에 의하면, 온라인/오프라인 정보검색 시스템 및 웹 환경에서 자연언어 텍스트 데이터베이스에 대한 검색성능을 현저히 향상시킬 수 있는 한글 스태머를 제공할 수 있다.

Claims (6)

1. 자연어 한글 단어에 대한 스태밍을 하기 위해서 소정 종류의 문맥의존 규칙테이블을 설계하는 단계와,

   상기 테이블을 시스템에서 순환적으로 호출하여 프로시쥬어에서 적용하는 단계를 구비하여 이루어진 것을 특징으로 하는 한글 스태밍 방법.
2. 제1항에 있어서, 다양한 불규칙 활용에 대한 처리를 위해서 어간사전 및 어미파일을 준비하는 단계를 더 구비하고,

   조건에 따라 하나 이상의 매칭 방법을 적용하는 것을 특징으로 하는 한글 스태밍 방법.
3. 제2항에 있어서, 상기 매칭 방법이 완전 매칭과 부분 매칭을 포함하는 것을 특징으로 하는 한글 스태밍 방법.
4. 한글의 색인어 처리대상을 최소어간 길이 규칙을 적용하여 처리하는 처리수단과,

   상기 처리수단에 의해 처리된 색인어 처리대상을 현재 처리되어야 할 자연어 음절조건에 따라 소정의 규칙을 적용하여 처리하는 스태밍 수단을 구비하여 구성된 것을 특징으로 하는 한글 스태머.
5. 제4항에 있어서, 한글의 색인어 처리대상이 체언과 용언을 포함하는 것을 특징으로 하는 한글 스태머.
6. 제4항 또는 제5항에 있어서, 상기 처리수단에서 적용하는 최소어간 길이 규칙이 고정어간 길이 규칙이고, 상기 스태밍 수단에서 적용하는 규칙이 문맥의존 어간길이 규칙인 것을 특징으로 하는 한글 스태머.