KR20010107113A - 자연어 정보 검색 시스템에서 구문 트리를 이용한 자연어질의의 불린 질의 및 벡터 질의 변환 방법 - Google Patents

Abstract

본 발명은 특히 한국어 자연어 질의에 대해 구문 분석을 한 구문 트리로부터 불린 질의 및 벡터 질의로 변환하는 방법을 사용하는 보다 정확한 자연어 정보 검색 방법에 관한 것이다. 본 발명은 사용자 질의에 대해 구문을 분석하여 구문 트리로 분류하는 단계; 상기 분류된 구문 트리의 단말 노드에 위치하는 각 형태소의 어휘와 품사 정보를 키워드 또는 연산자로 결정하는 단계; 상기 결정된 키워드를 복합명사 분할 및 복합 명사 합성을 사용하여 질의 확장시키는 단계; 상기 각 형태소의 어휘와 품사 정보에 의해 결정된 각 연산자들의 적용 순서를 결정하는 단계; 상기 각 연산자들의 적용 순서가 결정된 구문 트리를 포스트 픽스(Post-fix)형태의 불린식으로 변환하는 단계를 포함한다.

Description

자연어 정보 검색 시스템에서 구문 트리를 이용한 자연어 질의의 불린 질의 및 벡터 질의 변환 방법{Reduction of Natural Language Queries into Boolen and Vector Queries Using Syntactic Tree in a Natural Language Information Retrieval System}

본 발명은 한국어 자연어 질의 정보 검색 방법에 관한 것으로, 특히 한국어 자연어 질의에 대해 구문 분석을 한 구문 트리로부터 불린 질의 및 벡터 질의로 변환하는 방법을 사용하는 정보 검색 방법에 관한 것이다.

현재 전체 텍스트를 대상으로 하는 자연어 질의 정보 검색 방법에서는 텍스트의 내용을 대표하는 주제어로 명사와 복합 명사로 구성된 키워드를 사용하여 텍스트에 대한 색인과 사용자 질의 처리에 이용하고 있다.

그 과정은 먼저 텍스트내의 키워드들의 빈도수를 계산하고 키워드 색인 파일을 작성한다. 그리고 나서 사용자의 자연어 질의어에 포함된 키워트 리스트를 가지고 색인 파일의 키워드들의 빈도수에 따라 중요도를 계산하여 순위를 매겨 해당 문서 리스트를 사용자에게 보여주게 된다.

그러나 한국어 자연어 질의 정보 검색 방법에서는 한글 키워드가 가진 대표성의 한계와 동음이의어로 인한 모호성 때문에 사용자의 자연어 질의에 대한 부정확한 결과가 많이 발생하였다. 즉, 종래의 자연어 질의 정보검색은 구문분석을 사용하지 않고 형태소 분석만을 이용하여 불린 및 벡터질의를 뽑아내고 또 복합명사에 대한 체계적인 처리가 미흡하기 때문에 그 검색의 정확도가 많이 떨어져 사용자는 원하는 문서를 제대로 얻을 수가 없었다. 따라서 이러한 자연어 질의 정보검색 방법은 정확도가 요구되는 버티칼(vertical)검색 시장에 적용하기가 불가능했다.

본 발명의 목적은 자연어 질의에 대한 정보 검색 분야에서 키워드 기반 질의 검색의 한계를 극복하고 사용자에게 보다 쉬운 인터페이스를 제공하기 위해 한국어자연어 질의를 구문 분석하여 얻은 구문 트리로부터 불린 질의 및 벡터 질의로 변환하는 방법을 사용하는 버티칼 검색 시장을 위하여 고정밀 검색을 가능하게 하는 자연어 질의방법을 제공하는 데 있다.

이 기술은 기본적으로 자연어 질의에 대한 형태소 분석 및 태깅, 구문 분석의 기술을 이용하고 있으며, 또 복합명사의 체계적인 처리를 위하여 복합명사의 단위명사로의 분할, 부분복합명사 추출, 그리고 문장에서 복합명사의 자동 합성등의 기술을 포함하고 있으며 현재까지의 구문 분석 방법의 불완전한 성능을 감안하여 상위 N 개의 구문 분석 결과로부터 가장 나은 하나의 불린 질의 및 벡터 질의를 선택하는 과정이 특히 포함된다.

도 1은 자연어 질의가 불린 질의 및 벡터 질의로 변환되는 과정에 대한 흐름도.

도 2는 구문 분석의 결과인 구문 트리의 예시도.

도 3은 키워드 및 연산자 결정의 예시도.

도 4는 복합 명사 분할을 적용한 예시도.

도 5는 복합 명사 합성을 적용한 예시도.

도 6은 불린 연산자의 우선 순위 결정의 예시도.

도 7은 변환된 후치 불린식의 예시도.

도 8은 복합 명사 분할 음절 패턴 도시도.

도 9는 N-best 질의 변환의 예시도.

상기한 바와 같은 목적을 달성하기 위하여, 본 발명은 사용자 질의에 대해 구문을 분석하여 구문 트리로 분류하는 단계; 상기 분류된 구문 트리의 단말 노드에 위치하는 각 형태소의 어휘와 품사 정보를 키워드 또는 연산자로 결정하는 단계; 상기 결정된 키워드를 복합명사 분할 및 복합 명사 합성을 사용하여 질의 확장시키는 단계; 상기 각 형태소의 어휘와 품사 정보에 의해 결정된 각 연산자들의 적용 순서를 결정하는 단계; 상기 각 연산자들의 적용 순서가 결정된 구문 트리를 포스트 픽스(Post-fix)형태의 불린식으로 변환하는 단계를 포함하는 것을 특징으로 한다.

이하, 첨부된 도면을 참조하여 본 발명을 상세히 설명하기로 한다.

자연어 질의가 불린 질의 및 벡터 질의로 변환되는 과정에 대해 도 1과 같은흐름도가 도시된다. 입력된 사용자 질의에 대해 구문을 분석하여 구문 트리로 분류하고(S1), 이것은 도 2에 도시된 바와 같다. 이 분석된 구문 트리에서 단말 노드에 위치하는 각 형태소의 어휘와 품사 정보를 활용하여 각 단말 노드를 키워드 및 연산자로 결정하게 되는데(S2), 이렇게 구문 트리 단말 노드가 키워드 및 연산자로 결정된 형태가 도 3에 도시된다. 결정된 키워드를 복합명사 분할 과정을 통해 질의가 확장되는데(S3), 이 복합 명사 분할 과정에 대한 예는 도 4에 도시된다. 또한 어휘 규칙에 의한 복합 명사 합성을 사용하여 질의가 확장되고(S3), 이 복합 명사 합성 과정에 대한 예는 도 5에 도시된다. 품사 정보와 어휘 정보에 의해 결정된 각 연산자들이 실제 적용되는 적용 순서를 결정하고(S4), 이것에 대한 예가 도 6에 도시된다. 각 연산자들의 적용 순서가 결정된 구문 트리를 컴퓨터에서 처리하기 편리하도록 포스트 픽스(Post-fix)형태의 불린식으로 변환하고(S5), 이 불린식에 대한 예가 도 7에 도시된다. 변환된 불린식에서 불린 연산자를 제거함에 의해 벡터 질의로 변환할 수 있다(S6).

우선, 자연어 질의가 불린 질의 및 벡터 질의로 변환되는 과정을 설명하기 위하여, 하나의 자연어 질의어 "복합명사의 분할과 합성"이라는 구문을 분석하여 구문 트리로 분석된 예가 도 2에 도시된다. "복합명사의 분할과 합성" 이라는 구문에 대해 각 형태소간의 결합 구조를 분석하여 구문 트리로 표현한다면, 도 2에 도시한 바와 같이, "복합명사", "의", "분할", "과", "합성"과 같은 구조를 이룸을 알 수 있다.

이 분석된 구문 트리의 단말 노드에 위치하는 각 형태소의 어휘와 품사 정보를 활용하여 각 단말 노드가 키워드가 되는지 또는 연산자가 되는지가 결정된 질의로 변환한다. 여기서 키워드가 될 수 있는 형태소에는 보통 명사, 고유 명사, 수사, 영어 단어, 숫자 등이 있고, 연산자가 될 수 있는 형태소는 조사, 부사(예를 들면, "또는"과 같은), 관형사형 전성어미 등이 있다. 따라서, 도 2에서 예제로서 도시한 "복합명사의 분할과 합성"에 대한 구문 트리를 상기의 키워드와 연산자로 구분하면 [도 3에] 도시된 바와 같이, 키워드 "복합명사", 연산자 "AND", 키워드 "분할", 연산자" AND", 키워드 "합성"으로 구분된다.

또한, 도 3 에는 도시되지 않았지만, 연산자 NOT의 경우에는 용언과 보조 용언에 의해 결정된다. 즉, "-를 빼다", "-를 제외하다", "-가 없다","-가 아니다","-를 포함하지 않다","-가 포함되지 않다","-가 들어 있지 않다","-가 나타나지 않다"등이 연산자 NOT이 될 수 있는 것이다. 더욱 구체적으로 예를 들면, "삼성을 제외한 IBM에 관한 문서"라는 구문은 키워드 "삼성", 연산자 "NOT", 키워드"IBM"으로 변환된다.

단말 노드가 키워드로 결정되면 이 키워드는 복합명사 분할 과정을 통해 질의가 확장될 수 있다. 복합 명사 분할은 단위 명사 리스트와 음절 길이에 따른 복합 명사 분할 패턴(도 8에 도시됨)에 의해 분할 후보를 생성하고, 둘 이상의 후보가 생성될 경우에 복합 명사에 대한 상호 정보를 이용하여 하나의 분할 결과를 얻는다. 예를 들면, 불린 질의는 복합 명사 분할 과정을 거치면서 도 4와 같이, 키워드 "복합명사" 가 "복합","명사"로 분할될 수 있다.

또한, 상기 상호 정보는 부분 복합 명사를 생성하기 위해 사용되기도 한다.복합 명사가 3개 이상의 단위 명사로 분할될 경우에는 상호 정보를 이용하여 2개의 단위 명사로 구성된 부분 복합 명사를 생성시킬 수 있다. 예를 들면, 질의 키워드"복합명사분할"을 분할하면 "복합","명사","분할"과 같은 분할결과와 "복합명사","명사분할"과 같은 부분 복합 명사 생성결과를 얻을 수 있다.

어휘 규칙에 의한 복합 명사 합성을 사용하여 질의를 확장시킬 수 있다. 여기서 사용되는 5가지 어휘 규칙이 대표적인 예제와 함께 다음에 설명된다.

1)명사 + 명사 : (예제)정보 검색

2)명사+"의"+명사 : (예제)정보의 검색

3)명사+"를"+...+명사-"하"/"시키" 또는 명사+"가"++...+명사"되" :(예제)정보를 검색하

4)명사-"하"/"시키"/"되"+관계형어미+...+명사 : (예제)검색하는 시스템

5)명사+조사상당용언+관형형어미+...+명사 :(예제)사용자에 대한 인증

여기서, 조사 상당 용언이란 "~에 대하", "~에 관하","~을 위하", "~로 인하", " ~에 인하","~에 의하"와 같은 것을 일컫는다.

구문 트리에서 이러한 어휘 규칙을 적용함으로써 단어간의 거리에 관계없이 보다 정확한 복합 명사 합성이 가능할 수 있다. 또한 복합 명사 합성은 점진적으로 반복하여 적용될 수 있다. 예를 들면, 질의가 "복합 명사의 분할과 합성을 실험한..."일 경우에 한 번의 복합 명사 합성에 의해 "명사합성"을 얻을 수 있고 상기의 어휘 규칙에 의해 다시 키워드 "실험"과 합성시켜 "명사합성실험"이라는 새로운 합성 키워드를 생성할 수 있다. 다만, 한국어 복합 명사 합성 길이에 관한 통계치를 조사한 결과 대부분의 복합 명사는 그 합성 개수가 3개 이하라는 점을 감안하여 복합명사 합성을 적용함에 있어 그 합성의 개수를 3개 이하로 제한한다.

따라서, 복합 명사 분할이 적용된 후에 복합 명사는 대부분이 수식 구조라는 점을 이용하여 복합 명사 분할에서 얻은 마지막 오른쪽 명사는 복합 명사 합성의 후보로 사용되는데 이것에 대한 예가 도 5에 도시된다. 도 4에서 도시된 바와 같이 "복합명사"에 대해 "복합"과 "명사"로 복합 명사 분할이 적용된 후에 도 5에 도시된 바와 같이, 분할된 복합 명사중 가장 마지막 명사인 "명사"가 복합 명사 합성의 후보로 사용되어 새로운 키워드 "명사분할", "명사합성"을 생성시킬 수 있다.

한편, 도 3에서 설명된 바와 같이, 품사 정보와 어휘 정보에 의해 결정된 각 연산자들은 실제 적용될 때에 적용 순서가 결정되어야 한다. 연산자 적용의 우선 순위는 구문 트리의 구조적 모양을 그대로 반영하여 결정한다. 즉, 구문 트리에서의 내부 구조에 속하는 연산자가 외부 구조에 속하는 연산자를 우선한다. 따라서, 질의 "복합명사의 분할과 합성"은 도 6에 도시된 바와 같은 불리 트리 형태로 변환된다.

이 불린 트리는 다시 컴퓨터에서 처리하기 편리하도록 포스트 픽스(Post-fix)형태의 불린식으로 변환되는데, 이에 대한 예가 도 7에 도시된다. 벡터 질의는 이 불린식에서 불린 연산자를 제거함으로써 얻어질 수 있다.

종래의 구문 분석 시스템의 불완전성을 고려하기 위해 상위 N개의 구문 트리를 이용하는 방법을 제안한다. N개의 구문 트리 각각을 불린식으로 변환하고 이들 중에서 하나를 선택하기 위한 수단으로 다음의 선호도를 적용한다.

구문 트리 자체의 확률 값이 높은 것을 선호한다.

합성된 복합 명사가 존재할 가능성이 큰 것, 즉 합성된 복합 명사의 상호 정보 없이 복합 명사가 존재할 가능성이 큰 것을 선호한다.

합성된 복합 명사가 색인된 문서에 많이 나타나는 것, 즉 복합 명사의 TF(Term Frequency)가 큰 것을 선호한다.

단일 키워드 수가 많은 것을 선호한다.

이 4가지의 선호도를 1 차 결합하여 가장 큰 선호도를 가지는 불린식으로 변환된 불린 질의를 선택하고, 이 불린식에서 불린 연산자를 제거하여 변환된 벡터 질의를 얻는다.

결론적으로, 자연어 질의 "복합 명사의 분할과 합성"에 대해서 도 9a 및 9b 와 같은 2가지의 구문 분석 결과를 얻을 수 있다면, 위에서 설명한 바와 같이 합성된 복합 명사의 존재 가능성과 TF에 의해 올바른 분석결과를 선택할 수 있다. 즉, 구문 트리 9a가 구문 트리 9b에 비해 2개의 복합 명사 "복합명사합성","명사합성"을 더 가질 수 있고, 이들 사이의 상호 정보 값과 색인된 문서에서의 출현 빈도가 일반적으로 0보다 크다고 가정한다면 9a를 올바른 분석 결과로 선택할 수 있다.

본 발명은 고정밀 자연어 정보검색을 위하여 종래의 형태소 분석과 키워드 빈도수에 의한 자연어질의 처리와는 달리 구문분석과 체계적인 복합명사 분할 및 합성을 이용하여 불린/벡터질의로 변환하는 자연어 정보 검색 방법이다. 또 현재의 구문 분석의 불완전성을 고려하여 N개의 구문분석 결과로부터 최적의 질의를 선택할 수 있다.

Claims (2)

1. 사용자 질의에 대해 구문을 분석하여 구문 트리로 분류하는 단계; 상기 분류된 구문 트리의 단말 노드에 위치하는 각 형태소의 어휘와 품사 정보를 키워드 또는 연산자로 결정하는 단계; 상기 결정된 키워드를 복합명사 분할 및 복합 명사 합성을 사용하여 질의 확장시키는 단계; 상기 각 형태소의 어휘와 품사 정보에 의해 결정된 각 연산자들의 적용 순서를 결정하는 단계; 상기 각 연산자들의 적용 순서가 결정된 구문 트리를 포스트 픽스(Post-fix)형태의 불린식으로 변환하는 단계; 상기 불린식에서 불린 연산자를 제거하여 벡터 질의로 변환하는 단계를 포함하는 자연어 정보 검색 시스템에서 구문 트리를 이용한 자연어 질의의 불린 질의 및 벡터 질의 변환 방법.
2. 제 1항에 있어서, 사용자 질의에 대한 구문을 N개의 구문 트리로 분류하고, 상기 N 개의 구문 트리 각각을 불린식으로 변환하여,

   구문 트리 자체의 확률 값이 높은 것;

   합성된 복합 명사의 상호 정보없이 복합 명사가 존재할 가능성이 큰 것;

   합성된 복합 명사가 색인된 문서에 많이 나타나는 것;

   단일 키워드 수가 많은 것을 우선적으로 선택하는 것을 특징으로 하는 자연어 정보 검색 시스템에서 구문 트리를 이용한 자연어 질의의 불린 질의 및 벡터 질의 변환 방법.