KR100725664B1

KR100725664B1 - 2단계 ｎ-ｇｒａｍ 역색인 구조 및 그 구성 방법과 질의처리 방법 및 그 색인 도출 방법

Info

Publication number: KR100725664B1
Application number: KR1020050078687A
Authority: KR
Inventors: 황규영; 김민수; 이재길; 이민재
Original assignee: 한국과학기술원
Priority date: 2005-08-26
Filing date: 2005-08-26
Publication date: 2007-06-08
Also published as: KR20070024105A; JP2007080259A; JP4414989B2; DE102006039484A1; US7792840B2; DE102006039484B4; US20070050384A1

Abstract

본 발명은 n-gram 역색인에 존재하는 위치 정보의 중복을 제거하여 n-gram에 비해 그 크기를 줄이고 질의 처리 성능을 향상시킬 수 있는 2단계 n-gram 역색인 구조 및 그 구성 방법과 질의 처리 방법 및 그 색인 도출 방법을 제공한다.

본 발명의 역색인은 문서로부터 추출된 서브시퀀스들을 용어로 사용하는 백-엔드 역색인 및 상기 서브시퀀스로부터 추출된 n-gram들을 용어로 사용하는 프런트-엔드 역색인으로 구성되며,상기 백-엔드 역색인은 문서로부터 서로 n-1(n : n-gram의 길이)씩 겹치도록 추출된 소정 길이의 서브시퀀스들을 용어로서 사용하고, 각 서브시퀀스에 대한 포스팅 리스트에는 그 서브시퀀스가 문서상에서 나타난 위치 정보들을 저장하며, 상기 프런트-엔드 역색인은 상기 서브시퀀스로부터 1-슬라이딩 방식으로 추출된 소정 길이의 n-gram들을 용어로서 사용하고, 각 n-gram에 대한 포스팅 리스트에는 그 n-gram이 서브시퀀스 상에서 나타난 위치 정보들을 저장하는 것을 특징으로 한다.

역색인, n-gram, 데이터베이스, 문자열, 서브시퀀스, 프런트-엔드 역색인, 백-엔드 역색인

Description

2단계 ｎ-ｇｒａｍ 역색인 구조 및 그 구성 방법과 질의 처리 방법 및 그 색인 도출 방법{A TWO-LEVEL n-gram INVERTED INDEX STRUCTURE AND METHODS FOR INDEX BUILDING AND QUARY PROCESSING AND INDEX DERIVING OF IT}

도 1은 일반적인 역색인의 구조를 나타낸 도.

도 2a 및 도 2b는 n-gram 역색인을 나타낸 예시도.

도 3은 n-gram 역색인에 존재하는 위치 정보의 중복과 그 중복을 제거하는 방법을 나타낸 예시도.

도 4는 본 발명을 구현하기 위한 하드웨어 구성도.

도 5는 본 발명에 따른 2단계 n-gram 역색인의 구조를 나타낸 도.

도 6은 본 발명에 따른 2단계 n-gram 역색인의 색인 구성 알고리즘에 대한 흐름도.

도 7은 본 발명에 따른 2단계 n-gram 역색인의 구성을 나타낸 예시도.

도 8a 및 도 8b는 m-서브시퀀스 S가 질의 Q를 커버하는 예와 커버하지 않은 예를 나타낸 예시도.

도 9a 내지 도 9c는 m-서브시퀀스들의 집합이 질의 Q를 포함하는 경우들을 나타낸 예시도.

도 10은 본 발명에 따른 2단계 n-gram 역색인의 질의 처리 알고리즘에 대한 흐름도.

도 11은 본 발명에 따른 2단계 n-gram 역색인 구조를 도출하기 위한 알고리즘에 대한 흐름도.

도 12는 SNDO₁O₂ 릴레이션에 의미 있는 다치 종속성이 존재함을 보이는 예시도.

도 13은 SNDO₁O₂ 릴레이션이 두 개의 릴레이션으로 분해된 결과를 나타낸 예시도.

<도면의 주요 부분에 대한 부호의 설명>

100 : n-gram/2L 서버 110 : 색인 구성기

120 : 질의 처리기 200 : 데이터베이스 관리 시스템

300 : 데이터터베이스 310 : 텍스트 정보 DB

320 : n-gram/2L 역색인 정보 DB

본 발명은 역색인 구조 및 그 구성방법에 관한 것으로, 특히 n-gram 역색인에 존재하는 위치 정보의 중복을 제거하여 n-gram에 비해 그 크기를 줄이고 질의 처리 성능을 향상시킬 수 있도록 한 2단계 n-gram 역색인 구조 및 그 구성 방법과 질의 처리 방법 및 그 색인 도출 방법에 관한 것이다.

텍스트 문서 데이타에 대한 검색은 매우 기본적이고 중요한 연산으로서 일상 생활에서 널리 사용되고 있다. 그 예는 정보 검색, 단백질과 DNA의 시퀀스에 대한 유사 시퀀스 매칭 등이 있다.

단백질과 DNA의 시퀀스는 특별한 알파벳(예를 들어, DNA의 경우에는 {A,C,G,T})에 대한 텍스트 문서 데이타로 간주된다. 이러한 텍스트 문서 데이타에 대한 검색 연산을 효율적으로 처리하기 위해 다양한 색인 구조들이 연구되었으며, 그 중 실용적으로 가장 널리 사용되는 색인 구조는 역색인(Inverted Index)이다(Ricardo Baeza-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval, ACM Press, 1999.).

역색인은 질의로 주어진 용어를 포함하고 있는 문서들을 빠르게 검색하는 색인이다. 여기서 문서는 문자들의 한정된 시퀀스이고, 용어는 문서의 서브시퀀스이다. 역색인은 기본적으로 용어들에 대한 포스팅 리스트들로 구성된다(I. Witten, A. Moffat, and T. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, Los Altos, California, 2nd ed., 1999.).

하나의 포스팅 리스트는 하나의 용어와 연관되며, 그 용어를 포함하는 문서의 식별자와 용어가 문서에서 나타난 위치 정보들이 리스트 구조로 관리된다. 여기서, 리스트를 구성하는 각 엘리먼트인 문서 식별자와 위치 정보들을 묶어서 포스팅 이라고 부른다.

용어 t에 대한 포스팅 리스트를 구성하는 과정은 각 문서들에 대해 용어 t가 문서 식별자가 d인 문서에서 오프셋 o_1,...,o_f에 f번 발생할 때, 용어 t의 포스팅 리스트에 포스팅 <d, [o_1,...,o_f]>을 추가함으로써 수행된다( Falk Scholer, Hugh E. Williams, John Yiannis and Justin Zobel, "Compression of Inverted Indexes for Fast Query Evaluation," In Proc. Int'l Conf. on Information Retrieval, ACM SIGIR, Tampere, Finland, pp. 222-229, Aug. 2002.).

일반적으로 질의 처리를 용이하게 하기 위해 포스팅 리스트 내에서 포스팅들은 문서 식별자 d가 증가하는 순서대로 정렬되며, 포스팅 내에서 오프셋들은 오프셋 o가 증가하는 순서대로 정렬된다. 또한, 포스팅 리스트를 빠르게 검색하기 위해 B+-트리 등의 색인이 용어들에 대해 구성된다. 도 1은 이러한 역색인의 구조를 보여주고 있다.

역색인은 용어의 종류에 따라 단어를 용어로 사용한 단어 기반의 역색인과 n-gram을 용어로 사용한 n-gram 기반의 역색인으로 구분된다(I. Witten, A. Moffat, and T. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, Los Altos, California, 2nd ed., 1999.)

이중 n-gram 역색인은 n-gram을 용어로서 추출하여 구성된 역색인이다. n-gram은 문서 d가 문자의 시퀀스 c_0,c_1,...,c_N-1로 주어졌을 때, d로부터 추출된 n개의 연속적인 문자들로 이루어진 문자열이다.

n-gram 역색인을 구성하기 위해 주어진 문서 d로부터 n-gram을 빠짐없이 추출하는 방법은 n개의 연속적인 문자들로 이루어진 윈도우를 1-슬라이딩 방식으로 c₀부터 c_N-n까지 슬라이딩시키면서 윈도우 내에 위치한 문자열을 추출하는 것이다. 따라서 d의 i번째 n-gram은 문자열 c_i,c_i+1,...,c_i+n-1이 된다.

도 2는 주어진 문서들의 집합으로부터 n-gram 역색인을 구성한 예이다. 여기에서 n = 2이이다. 도 2a는 주어진 문서 집합을 나타내고, 도 2b는 그에 대해 구성된 n-gram 역색인을 나타낸다.

n-gram 역색인을 사용하여 질의를 처리하기 위해서는 우선 질의 문자열을 n-gram들로 분할한 후, 역색인에서 그 n-gram들의 포스팅 리스트들을 찾아 병합(Merge)한다 (Ricardo Baeza-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval, ACM Press, 1999.).

예를 들어, 도 2의 n-gram 역색인에서 문자열 "BCDD"을 포함하고 있는 문서들을 찾는 질의는 다음의 두 단계를 따른다.

첫 번째 단계에서는 질의 문자열을 "BC", "CD", "DD" 의 세 개의 2-gram들로 분할한 후, 역색인에서 각 2-gram들을 찾는다.

두 번째 단계에서는 각 2-gram에 대한 포스팅 리스트를 문서 식별자로 머지 조인(Merge Join)하면서, "BC", "CD", "DD"와 같이 세 개의 2-gram들이 연속해서 나타나 "BCDD"을 구성하는 문서를 구한다. 스캔한 포스팅 리스트 상의 문서 0, 2에 서 세 개의 2-gram들이 연속해서 나타나므로 질의 결과는 문서 식별자 0, 2가 된다.

n-gram 역색인은 언어 중립적(Language-neutral)이고 에러 허용적(Error Tolerant)인 장점들을 가진다(Ricardo Baeza-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval, ACM Press, 1999.).

언어 중립적이란 색인 용어를 기계적인 방식으로 추출하므로 언어적인 지식을 필요로 하지 않는다는 것을 의미한다.

이러한 특성으로 인해 n-gram 역색인은 복잡한 언어적인 지식을 필요로 하는 일부 아시아권 언어에 대한 정보 검색이나 단어의 개념이 명확하지 않은 단백질과 DNA의 시퀀스에 대한 검색에 많이 사용된다.

에러 허용적이란 색인 용어를 1-슬라이딩 방식으로 추출하므로 어떤 문서에 약간의 철자 에러가 있어도 그 문서를 검색할 수 있다는 것을 의미한다.

이러한 특성으로 인해 n-gram 역색인은 근사 문자열 매칭처럼 에러를 허용하여 문서를 검색하는 응용에 유용하게 사용된다.

그러나, n-gram 역색인은 색인의 크기가 크고 질의 처리 시간이 오래 걸리는 등 공간적, 시간적 비용이 크다는 단점을 가진다(Ricardo Baeza-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval, ACM Press, 1999.).

이는 n-gram을 1-슬라이딩 방식으로 추출하는 용어 추출 방법의 특성 때문이다.

1-슬라이딩 방식으로 추출하므로 매우 많은 수의 n-gram들이 추출되고, 따라 서 색인의 크기가 커지는 단점이 있다.

또한, 질의 처리시 읽어 들여야 하는 포스팅들의 개수가 많아져 질의 처리 시간도 오래 걸리는 단점이 있다.

본 발명은 이러한 문제점을 해결하기 위한 것으로, 본 발명의 목적은 n-gram 역색인에 존재하는 위치 정보의 중복을 제거하여 n-gram에 비해 그 크기를 줄이고 질의 처리 성능을 향상시킬 수 있는 2단계 n-gram 역색인 구조 및 그 구성 방법과 질의 처리 방법 및 그 색인 도출 방법을 제공함에 있다.

상기 목적을 달성하기 위한 본 발명에 따른 2단계 n-gram 역색인 구조는, 문서로부터 추출된 서브시퀀스들을 용어로 사용하는 백-엔드 역색인; 및 상기 서브시퀀스로부터 추출된 n-gram들을 용어로 사용하는 프런트-엔드 역색인;으로 된 것을 특징으로 한다.

상기 백-엔드 역색인은 문서로부터 서로 n-1(n : n-gram의 길이)씩 겹치도록 추출된 소정 길이의 서브시퀀스들을 용어로서 사용하고, 각 서브시퀀스에 대한 포스팅 리스트에는 그 서브시퀀스가 문서상에서 나타난 위치 정보들을 저장하며, 상기 프런트-엔드 역색인은 상기 서브시퀀스로부터 1-슬라이딩 방식으로 추출된 소정 길이의 n-gram들을 용어로서 사용하고, 각 n-gram에 대한 포스팅 리스트에는 그 n- gram이 서브시퀀스 상에서 나타난 위치 정보들을 저장하는 것을 특징으로 한다.

또한, 상기 목적을 달성하기 위한 본 발명의 2단계 n-gram 역색인 구성방법은, 데이터베이스의 각 문서로부터 길이 m의 m-서브시퀀스들을 서로 일정 부분씩 겹치도록 추출하면서 m-서브시퀀스가 문서상에서 나타난 위치 정보들를 기록하는 제 1 단계; 상기 제 1 단계에서 기록한 각 위치 정보에 대해, 소정의 m-서브시퀀스가 소정 문서의 오프셋에서 나타났다면 상기 소정의 m-서브시퀀스에 해당하는 백-엔드 역색인의 용어에 대한 포스팅 리스트에 해당 포스팅을 추가하여 백-엔드 역색인을 구성하는 제 2 단계; 상기 제 1 단계에서 얻어진 m-서브시퀀스 집합의 각 m-서브시퀀스로부터 n-gram들을 추출하면서 n-gram이 m-서브시퀀스 상에서 나타난 위치 정보들을 기록하는 제 3 단계; 및 상기 제 3 단계에서 기록한 각 위치 정보에 대해, 소정의 n-gram이 소정의 m-서브시퀀스의 오프셋에서 나타났다면 상기 소정의 n-gram에 해당하는 프런트-엔드 역색인의 용어에 대한 포스팅 리스트에 해당 포스팅을 추가하여 프런트-엔드 역색인을 구성하는 제 4 단계;로 이루어짐을 특징으로 한다.

상기 제 1 단계에서는 상기 m-서브시퀀스들을 n-1(n : n-gram의 길이)씩 겹치도록 추출하며, 또한 마지막 m-서브시퀀스의 길이가 m보다 작을 경우, 문자열의 뒷부분에 공백 문자들을 덧붙여서 길이가 m이 되도록 함이 바람직하다.

상기 목적을 달성하기 위한 본 발명의 2단계 n-gram 역색인을 이용한 질의 처리 방법은, 문서로부터 추출된 서브시퀀스들을 용어로 사용하는 백-엔드 역색인 및 상기 서브시퀀스로부터 추출된 n-gram들을 용어로 사용하는 프런트-엔드 역색인 을 사용하여 질의를 처리하는 방법에 있어서, 소정 질의를 n-gram들로 분할하는 제 1 단계; 상기 프런트-엔드 역색인을 사용하여 상기 제 1 단계에서 구한 각 n-gram들에 대한 포스팅 리스트들을 m-서브시퀀스 식별자로 머지-아우터-조인(merge-outer-join)하면서, 상기 질의를 커버 하는 m-서브시퀀스들을 소정 집합에 추가하는 제 2 단계; 및 상기 백-엔드 역색인을 사용하여 상기 제 2 단계에서 구한 소정 집합에 포함된 m-서브시퀀스들에 대한 포스팅 리스트들을 문서 식별자로 머지-아우터-조인하면서, 소정의 동일한 문서로부터 추출된 m-서브시퀀스들의 집합이 상기 질의를 포함하는지를 검사하여 질의에 포함되면 상기 소정의 동일한 문서를 질의 결과로 반환하는 제 3 단계;로 이루어짐을 특징으로 한다.

상기 m-서브시퀀스가 질의를 커버하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인하며, 상기 제 3 단계에서의 집합이 질의를 포함하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인함이 바람직하다.

또한, 상기 목적을 달성하기 위한 2단계 n-gram 역색인 도출 방법은, n-gram 역색인으로부터 프런트-엔드 역색인과 백-엔드 역색인으로 구성되는 역색인을 도출하는 방법에 있어서, n-gram 역색인을 제1정규형(1NF : First Normal Form)을 따르는 릴레이션으로 표현하는 제 1 단계; 상기 제 1 단계에서 구한 릴레이션에 의미 있는 다치 종속성으로 인한 위치 정보의 중복이 존재함을 확인하는 제 2 단계; 상기 제 2 단계에서 확인된 위치 정보의 중복을 제거하기 위해 상기 제 1 단계에서 구한 릴레이션을 제4정규형(4NF : Fourth Normal Form)을 따르도록 두 개의 릴레이 션으로 분해하는 제 3 단계; 및 상기 제 3 단계에서 구한 두 개의 릴레이션을 각각 프런트-엔드 역색인과 백-엔드 역색인으로 표현하는 제 4 단계;로 이루어짐을 특징으로 한다.

이하, 본 발명의 바람직한 실시 예를 첨부된 도면을 참조하여 보다 상세하게 설명한다. 단, 하기 실시 예는 본 발명을 예시하는 것일 뿐 본 발명의 내용이 하기 실시 예에 한정되는 것은 아니다.

본 발명은 n-gram 역색인의 크기가 커지는 원인을 분석하고, 그 주요 원인이 n-gram의 위치 정보의 중복 때문임을 밝히며, 그 중복을 제거하는 방안에 대해 설명한다.

도 3은 n-gram 역색인에 존재하는 위치 정보의 중복과 그 중복을 제거하기 위한 본 발명의 2단계 n-gram 역색인 일명, "n-gram/2L "역색인을 나타낸 것이다.

도 3의 (a)는 N개의 문서들로 구성되어 있는 문서 집합의 예이다. 문자열 ＂a₁a₂a₃a₄＂를 서브시퀀스 A라 할 때, 서브시퀀스 A는 문서 1, 2, N의 오프셋 o₁, o₃, o₅에 나타나고, 문자열 "b₁b₂b₃b₄"를 서브시퀀스 B라 할 때, 서브시퀀스 B는 문서 1, N의 오프셋 o₂, o₄에 나타난다.

따라서, 세 개의 연속적인 2-gram "a₁a₂", "a₂a₃", "a₃a₄"가 문서 1, 2, N에 나타나고, 세 개의 연속적인 2-gram "b₁b₂", "b₂b₃", "b₃b₄"가 문서 1, N에 나타난다.

도 3의 (b)는 도 3의 (a)로부터 구성된 2-gram 역색인을 나타내며, 회색으로 칠해진 부분은 위치 정보의 중복을 나타낸다.

즉, 도 3의 (b)의 2-gram 역색인에서 2-gram "a₁a₂", "a₂a₃", "a₃a₄"의 포스팅 리스트에는 2-gram "a₂a₃", "a₃a₄"의 오프셋이 2-gram "a₁a₂"의 오프셋보다 각각 1, 2만큼씩 크다는 정보가 문서 1 외에 문서 2, N에도 반복해서 나타난다.

2-gram "b₁b₂", "b₂b₃", "b₃b₄"의 포스팅 리스트에도 마찬가지이다.

즉, 문서에서 자주 발생하는 서브시퀀스가 있을 경우 그 서브시퀀스로부터 추출되는 n-gram들의 서브시퀀스 내에서의 상대적인 위치 정보들이 여러 번 반복되어 색인된다.

만약, 자주 발생하는 서브시퀀스로부터 추출되는 n-gram들의 상대적인 위치 정보들을 단 한 번만 나타낼 수 있다면 n-gram 역색인에 존재하는 이러한 중복을 제거하여 색인의 크기를 줄일 수 있다.

도 3의 (c)는 본 발명에 따른 2단계 n-gram 역색인을 나타낸다. 세 개의 2-gram "a₁a₂", "a₂a₃", "a₃a₄"의 문서 상에서의 위치 정보는 도 3의 (c)의 오른쪽과 같이 서브시퀀스 A의 문서 상에서의 위치 정보와 도 3의 (c)의 왼쪽과 같이 2-gram ""a₁a₂", "a₂a₃", "a₃a₄" 서브시퀀스 A 상에서의 위치 정보로 두 단계에 걸쳐 표현함으로써 중복된 정보를 제거할 수 있다.

이와 같이 n-gram 역색인을 두 개의 역색인으로 분해하는 것은 이론적으로 릴레이션에 의미 있는(non-trivial) 다치 종속성(MVD: Multivalued Dependency)이 존재할 때 정규화를 통해 두 개의 릴레이션으로 분해하여 중복을 제거하는 것과 동일하다.

도 4는 본 발명을 구현하기 위한 시스템 구성도를 도시한 것으로, 크게 n-gram/2L(Two-level n-gram) 서버(100), 데이터베이스 관리 시스템(200) 및 데이터베이스(300)로 구성된다.

상기 n-gram/2L 서버(100)는 2단계 n-gram 역색인을 생성하기 위한 색인 구성기(110)와 2단계 n-gram 역색인을 사용하여 질의를 처리하는 질의 처리기(120)로 구성된다. 상기 데이터베이스(300)는 각종 텍스트 정보가 저장되는 텍스트 정보 DB(310) 및 2단계 n-gram 역색인이 저장되는 n-gram/2L 역색인 정보 DB(320)로 구성된다.

상기 n-gram/2L 서버(100)는 데이터베이스 관리 시스템(200)과 연동하여 데이터베이스(300)의 n-gram/2L 역색인 정보 DB(320)에 2단계 n-gram 역색인을 생성하고 이를 사용하여 질의를 처리한다.

상기 데이터베이스 관리 시스템(200)은 데이터베이스(300)에 저장된 텍스트 정보DB(310)를 관리한다.

이와 같은 시스템에서 구현되는 본 발명의 2단계 n-gram 역색인의 구조에 대해 살펴본다.

본 발명의 2단계 n-gram 역색인은 프런트-엔드 역색인과 백-엔드 역색인으로 구성되며, 도 5는 본 발명에 따른 2단계 n-gram 역색인의 구조를 나타낸 것이다.

본 발명에서는 길이 m의 서브시퀀스를 m-서브시퀀스라 하고, 또한, n-gram 의 길이를 n으로, m-서브시퀀스의 길이를 m으로 표기한다.

백-엔드 역색인은 문서로부터 추출된 m-서브시퀀스들을 용어로서 사용하고, 각 m-서브시퀀스에 대한 포스팅 리스트에는 그 m-서브시퀀스가 문서상에서 나타난 위치 정보들을 저장한다.

프런트-엔드 역색인은 m-서브시퀀스로부터 추출된 n-gram들을 용어로서 사용하고, 각 n-gram에 대한 포스팅 리스트에는 그 n-gram이 m-서브시퀀스 상에서 나타난 위치 정보들을 저장한다.

다음은 2단계 n-gram 역색인의 색인 구성 방법에 대하여 살펴본다.

본 발명에서는 데이터베이스(300)의 텍스트 정보 DB(310)로부터 주어진 텍스트 정보로부터 2단계 n-gram 역색인을 구성하기 위해서 m-서브시퀀스 추출 과정, 백-엔드 역색인 구성 과정, n-gram 추출 과정, 프런트-엔드 역색인 구성 과정을 거지며, 이는 상기 n-gram/2L 서버(100)의 색인 구성기(110)에서 행하게 된다.

상기 m-서브시퀀스 추출 과정에서는 m-서브시퀀스의 길이를 m으로 고정하고, m-서브시퀀스들이 서로 n-1(n : n-gram의 길이)만큼씩 겹치도록 추출한다. m-서브시퀀스들을 서로 n-1만큼씩 겹치도록 하는 이유는 n-gram 추출 과정에서 n-gram이 누락되거나 중복되는 것을 방지하기 위해서이며, 이 방법의 정확성은 다음의 정리 1에서 증명한다.

정리 1. m-서브시퀀스 추출 과정에서 m-서브시퀀스들을 서로 n-1만큼씩 겹치도록 하면 n-gram 추출 과정에서 누락되거나 중복되는 n-gram이 발생하지 않는다.

이에 대한 증명은 다음과 같다.

문서 d가 문자의 시퀀스 c₀,c₁,...,c_N-1로 주어졌을 때, 문서 d로부터 추출되는 n-gram들의 개수는 N-n+1개 이고, 각 n-gram의 시작 문자는 c_i이다(0 ≤ i < N-n+1).

또한, m-서브시퀀스의 길이가 m으로 주어졌을 때, 문서 d로부터 추출되는 m-서브시퀀스들의 개수는 (N-n+1)/(m-n+1)개 이고, 각 m-서브시퀀스의 시작 문자는 c_j이다(0 ≤ j < (N-n+1)/(m-n+1)). 설명의 편의상 c_i를 시작 문자로 하는 n-gram을 N_i로 표기하고, c_j를 시작 문자로 하는 m-서브시퀀스를 S_j로 표기한다.

문서 d로부터 추출되는 인접한 임의의 두 m-서브시퀀스를 S_p, S_q라 할 때, S_p로부터 추출되는 n-gram들은 N_p,...,N_p+m-n이고, S_q로부터 추출되는 n-gram들은 N_q,...,N_q+m-n이다.

m-서브시퀀스들끼리 서로 겹치는 구간의 길이를 l이라 할 때, 길이 l은 l = n-1, l < n-1, l > n-1의 세 가지 경우로 나뉘는데, 각각의 경우들에 대해 두 m-서브시퀀스 S_p, S_q로부터 추출되는 n-gram들 중 누락되거나 중복되는 n-gram이 있는지를 검사함으로써 정리를 증명한다.

＊ Case l = n-1 : 서로 n-1만큼씩 겹치므로 q=p+m-n+1이고, S_q로부터 추출되는 n-gram들은 다시 N_p+m-n+1,...,N_p+2m-2n+1로 표현된다. S_p로부터 추출되는 n-gram들은 N_p,...,N_p+m-n이므로, 두 m-서브시퀀스 S_p, S_q로부터 N_p,...,N_p+m-n, N_p+m-n+1,...,N_p+2m-2n+1의 n-gram들이 누락되거나 중복되지 않고 한 번씩만 추출된다.

＊ Case l < n-1 : l = n-2이라고 가정하자. 서로 n-2만큼씩 겹치므로 q=p+m-n+2이고, 따라서 S_q로부터 추출되는 n-gram들은 다시 N_p+m-n+2,...,N_p+2m-2n+2로 표현된다. 두 m-서브시퀀스 S_p, S_q로부터 n-gram N_p+m-n+1이 한 번도 추출되지 않으므로, 누락되는 n-gram이 발생한다.

＊ Case l > n-1 : l = n이라고 가정하자. 서로 n만큼씩 겹치므로 q=p+m-n이고, 따라서 Sq로부터 추출되는 n-gram들은 다시 N_p+m-n,...,N_p+2m-2n로 표현된다. 두 m-서브시퀀스 S_p, S_q로부터 n-gram N_p+m-n이 각각 한 번씩, 총 두 번 추출되므로, 중복되는 n-gram이 발생한다.

따라서, m-서브시퀀스 추출 과정에서 인접한 두 m-서브시퀀스들이 서로 n-1만큼씩 겹치도록 해야만 n-gram들의 누락이나 중복을 방지할 수 있다.

다음, 2단계 n-gram 역색인의 색인 구성 과정에서는 문서 데이터베이스와 m-서브시퀀스의 길이 m, 그리고 n-gram의 길이 n을 입력으로 받아서 n-gram/2L 역색인을 구성한다. 도 6은 색인 구성 과정의 상세한 알고리즘에 대한 흐름도를 나타낸 것이다.

도 6을 참조하면, 단계(S110)에서는 데이터베이스(300)의 텍스트 정보 DB(310)의 각 문서로부터 m-서브시퀀스들을 서로 n-1씩 겹치도록 추출하면서 m-서 브시퀀스가 문서상에서 나타난 위치 정보들을 기록한다.

즉, 각 문서가 문자의 시퀀스 c₀,c₁,...,c_N _-1로 이루어질 때, 0 ≤ i < (N-n+1)/(m-n+1)인 모든 i에 대해 문자 c_i*(m-n+1)을 시작으로 하는 길이 m의 서브시퀀스들을 추출한다. 만약, 마지막 m-서브시퀀스의 길이가 m보다 작다면 문자열의 뒷부분에 공백 문자들을 덧붙여서 길이가 m이 되도록 만든다.

단계(S120)에서는 상기 단계(S110)에서 기록한 각 위치 정보에 대해, m-서브시퀀스 s가 문서 d의 오프셋 o₁,...,o_f에서 나타났다면 백-엔드 역색인의 용어 s에 대한 포스팅 리스트에 <d, [o₁,...,o_f]>를 추가함으로써 백-엔드 역색인을 구성한다.

그리고 단계(S130)에서는 단계(S110)에서 구한 m-서브시퀀스 집합의 각 m-서브시퀀스로부터 n-gram들을 1-슬라이딩 방식으로 추출하면서 n-gram이 m-서브시퀀스 상에서 나타난 위치 정보들을 기록한다.

단계(S140)에서는 상기 단계(S630)에서 기록한 각 위치 정보에 대해, n-gram g가 m-서브시퀀스 v의 오프셋 o₁,...,o_f에서 나타났다면 프런트-엔드 역색인의 용어 g에 대한 포스팅 리스트에 <v, [o₁,...,o_f]>를 추가함으로써 프런트-엔드 역색인을 구성한다.

도 7은 주어진 문서들의 집합으로부터 2단계 n-gram 역색인을 구성한 예이다. 여기에서 n = 2이며, m = 4이다.

도 7의 (a)는 주어진 문서 집합을 나타내며, 도 7의 (b)는 상기 단계(S110)에 따라 도 7의 (a)에 나타낸 문서 집합으로부터 추출된 4-서브시퀀스들의 집합을 나타낸다. 문서들은 길이가 4이고 서로 1(즉, n-1)만큼씩 겹치는 4-서브시퀀스들로 나눠지므로 문서 0으로부터 추출되는 4-서브시퀀스들은 "ABCD", "DDAB", "BBCD"이다.

도 7의 (c)는 상기 단계(S120)에서 추출된 4-서브시퀀스 집합으로부터 구성된 백-엔드 역색인이다. 4-서브시퀀스 "ABCD"는 문서 0, 3, 4에서 각각 0, 3, 6인 오프셋에서 나타났으므로 4-서브시퀀스 "ABCD"와 연관된 포스팅 리스트에는 포스팅 <0, [0]>, <3, [3]>, <4, [6]>이 추가된다.

그리고 도 7의 (d)는 도 7의 (b)에 나타낸 4-서브시퀀스에 부여된 식별자이고, 도 7의 (e)는 단계(S130)에서 4-서브시퀀스 집합으로부터 추출된 2-gram 집합을 나타낸다. 1-슬라이딩 방식으로 2-gram들을 추출하므로 4-서브시퀀스 0으로부터 추출되는 2-gram들은 "AB", "BC", "CD"이다.

도 7의 (f)는 상기 단계(S140)에서 2-gram 집합으로부터 구성된 프런트-엔드 역색인이다. 2-gram "AB"는 4-서브시퀀스 0, 3, 4, 5에서 각각 0, 2, 1, 2인 오프셋에서 나타났으므로 2-gram "AB"와 연관된 포스팅 리스트에는 포스팅 <0, [0]>, <3, [2]>, <4, [1]>, <5,[2]>가 추가된다.

다음은 2단계 n-gram 역색인의 질의 처리 방법에 대하여 살펴본다.

본 발명에서 2단계 n-gram 역색인을 사용한 질의 처리는 n-gram/2L 서버(100)의 질의 처리기(120)에서 수행되며, 두 단계로 이루어진다.

먼저, 프런트-엔드 역색인을 검색하여 얻어진 결과에 한해서, 다시 백-엔드 역색인을 검색하여 최종 결과를 얻는다.

첫 번째 단계에서는 질의 문자열을 분할하여 얻은 n-gram들을 가지고 프런트-엔드 역색인을 검색함으로써 주어진 질의 문자열을 커버하는 m-서브시퀀스들을 찾아낸다. 이 단계에서 질의 문자열을 커버하지 않는 m-서브시퀀스들은 필터링 된다.

두 번째 단계에서는 첫 번째 단계에서 얻은 m-서브시퀀스들을 가지고 백-엔드 역색인을 검색함으로써 질의 문자열을 포함하는 m-서브시퀀스들의 집합 {S_i}를 가지는 문서들을 찾아낸다.

이에 대하여 다음의 정의 1에서 커버(Cover)를 정형적으로 정의하고, 정의 3에서 포함(Contain)을 정형적으로 정의한다.

정의 1. m-서브시퀀스 S가 질의 문자열 Q에 대해 다음의 네 가지 조건 중 하나를 만족하면 S가 Q를 커버한다고 정의한다: (1) S의 서픽스가 Q의 프리픽스와 일치하거나, (2) S 전체가 Q의 서브스트링과 일치하거나, (3) S의 프리픽스가 Q의 서픽스와 일치하거나, (4) S의 서브스트링이 Q전체와 일치한다.

정의 2. 문자열들의 시퀀스를 하나의 문자열로 전개하는 함수 익스팬드(expand)를 다음과 같이 정의한다: (1) 두 개의 문자열 S_i, S_p가 각각 문자열 c_i...c_j와 c_p...c_q로 주어지고, S_i의 서픽스와 S_p의 프리픽스가 c_j-k+1...c_j = c_p...c_p+k-1과 같이 k만큼 겹쳐져 있다고 하자 (k ≥0). 이때, expand(S_iS_p) = c_i...c_jcp+k...c_q 이다. (2) 두 개 이상의 문자열 S₁, S_l+1,..., S_m에 대해 expand(S₁S_l+1...S_m) = expand(expand(S_lS_l+1),S_l+2...S_m)이다.

정의 3. m-서브시퀀스들의 집합 {S_i}가 다음의 조건을 만족하면, {S_i}가 Q를 포함한다고 정의한다: {S_i}에 속한 m-서브시퀀스들이 겹치도록 연속적으로 연결된 시퀀스를 S₁S_l+1...S_m이라 할 때, expand(S₁S_l+1...S_m)의 서브스트링이 질의 문자열 Q 전체와 일치한다.

도 8은 질의 문자열 Q를 커버하는 m-서브시퀀스의 예와 커버하지 않는 m-서브시퀀스의 예를 나타낸 것이다.

도 8a에서는 S의 서픽스가 Q의 프리픽스와 일치하므로 S는 Q를 커버한다. 도 8b에서는 S의 서브스트링 "BCD"가 정의 1의 네 가지 조건을 모두 만족하지 않기 때문에 S는 Q를 커버하지 않는다.

보조정리 1. 질의 문자열 Q를 포함하는 m-서브시퀀스들의 집합 {S_i}가 추출된 문서는 Q를 커버하는 m-서브시퀀스를 하나 이상 포함한다.

이에 대한 증명은 다음과 같다

우선, m-서브시퀀스들의 집합 {S_i}가 Q를 포함하는 모든 경우들을 나타내면 도 9와 같다. 이때, Q의 길이 Len(Q)가 m보다 크거나 같은 경우인 도 9a와 작은 경우인 도 9b, 도 9c로 나누어서 고려한다.

도 9a에서는 (j-i+1)개의 m-서브시퀀스들의 집합 {S_i,...,S_j}가 Q를 포함한 다. 도 9b에서는 한 개의 m-서브시퀀스 S_k가 Q를 포함한다. 도 9c에서는 두 개의 m-서브시퀀스들의 집합 {S_p,S_q}이 Q를 포함한다.

이와 같이 m-서브시퀀스들의 집합 {S_i}가 Q를 포함한다면, {S_i}에 속한 각 m-서브시퀀스는 Q를 커버함을 알 수 있다.

따라서, 그러한 m-서브시퀀스들의 집합 {S_i}가 추출된 문서는 Q를 커버하는 m-서브시퀀스를 최소한 하나 이상 포함하게 된다.

다음, 2단계 n-gram 역색인의 질의 처리과정에서는 2단계 n-gram 역색인과 질의 Q를 입력으로 받아서 질의를 만족하는 문서 식별자들을 찾아서 반환하는 작업을 수행한다.

도 10은 2단계 n-gram 역색인에서의 질의 처리 알고리즘에 대한 흐름도를 나타낸 것이다.

도 10을 참조하면, 단계(S210)에서는 우선 질의 Q를 n-gram들로 분할한 후, 프런트-엔드 역색인을 사용하여 각 n-gram들에 대한 포스팅 리스트들을 m-서브시퀀스 식별자로 머지 아우터 조인(Merge Outer Join)하면서, 상기 질의 처리 과정에서의 정의 1에 따라 Q를 커버하는(즉, 보조정리 1의 필요 조건을 만족하는) m-서브시퀀스들을 집합 Scover에 추가한다.

Q를 커버하는 m-서브시퀀스는 일반적으로 Q로부터 추출된 모든 n-gram들을 가지고 있지 않기 때문에 질의 처리 과정의 단계(S210)에서 머지 아우터 조인(Merge Outer Join)을 수행한다.

이때, m-서브시퀀스가 Q를 커버하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인한다.

그리고 단계(S220)에서는 백-엔드 역색인을 사용하여 상기 단계(S210)에서 구한 Scover에 포함된 m-서브시퀀스들에 대한 포스팅 리스트들을 문서 식별자로 머지 아우터 조인하면서, 동일한 문서 d_i로부터 추출된 m-서브시퀀스들의 집합 {S_i}가 정의 3에 따라 Q를 포함하는지를 검사한다.

만약, 포함하면 d_i를 질의 결과로 반환한다. 이때, 집합 {S_i}가 Q를 포함하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인한다.

다음은 2단계 n-gram 역색인 구조를 도출하는 방법에 대하여 살펴본다.

본 발명에서는 n-gram 역색인으로부터 2단계 n-gram 역색인 도출시 도 11과 같이, n-gram 역색인을 제1정규형(1NF: First Normal Form)을 따르는 릴레이션으로 표현하는 단계(S310), 상기 단계(S310)에서 구한 릴레이션에 의미 있는 다치 종속성으로 인한 위치 정보의 중복이 존재함을 확인하는 단계(S320), 상기 단계(S320)에서 확인된 위치 정보의 중복을 제거하기 위해 상기 단계(S310)에서 구한 릴레이션을 제4정규형(4NF: Fourth Normal Form)을 따르도록 두 개의 릴레이션으로 분해하는 단계(S330), 상기 단계(S330)에서 구한 두 개의 릴레이션을 각각 프런트-엔드 역색인과 백-엔드 역색인으로 표현하는 단계(S340)의 순서를 따르는 기법을 사용한다.

먼저, 상기 단계(S310)에서는 n-gram 역색인을 제1정규형으로 바꾼 릴레이션을 고려한다. 이러한 릴레이션을 NDO 릴레이션이라 부른다. 이 릴레이션은 N, D, O 세 개의 애트리뷰트(attribute)로 구성된다. 여기서, N은 n-gram을, D는 문서 식별자를, O는 오프셋을 나타낸다.

그리고 NDO 릴레이션에 애트리뷰트 S를 추가하고, 애트리뷰트 O를 애트리뷰트 O₁, O₂로 나누어 총 다섯 개의 애트리뷰트 S, N, D, O₁, O₂를 가지도록 표현한 릴레이션을 SNDO₁O₂ 릴레이션이라고 부른다.

여기에서 S는 n-gram이 추출되는 길이 m의 m-서브시퀀스를, O₁은 n-gram이 나타난 m-서브시퀀스 상에서의 오프셋을, O₂는 m-서브시퀀스가 나타난 문서 상에서의 오프셋을 나타낸다.

SNDO₁O₂ 릴레이션의 애트리뷰트 S, O₁, O₂의 값은 NDO 릴레이션의 애트리뷰트 N, D, O의 값에 의해 자동으로 결정된다. 주어진 문서 집합의 각 문서가 m-서브시퀀스들로 n-1만큼씩 겹치도록 나누어져 있다고 가정하자. 그러면, 상기 정리 1에 의해 문서 집합으로부터 추출되는 임의의 n-gram은 하나의 m-서브시퀀스에만 속하게 된다.

NDO 릴레이션의 임의의 투플(tuple)(n, d, o)로부터 자동으로 결정되는 SNDO₁O₂ 릴레이션의 투플(s, n, d, O₁, O₂)에서, s는 문서 d의 오프셋 o에 있는 n-gram n이 속해 있는 m-서브시퀀스다. 그리고, O₁은 s상에서 n-gram n이 나타난 오프 셋이며, O₂는 문서 d상에서 s가 나타난 오프셋이다.

도 12의 좌측은 도 2b의 2-gram 역색인을 NDO 릴레이션으로 표현한 예이며, 도 12의 우측은 m = 4일때, 도 12의 좌측의 NDO 릴레이션을 SNDO₁O₂ 릴레이션으로 표현한 후, 애트리뷰트 S의 값에 의해 정렬한 예이다.

도 12의 우측의 SNDO₁O₂ 릴레이션에서 검정색 마커로 표시된 투플은 도 12의 좌측의 NDO 릴레이션에서 검정색 마커로 표시된 투플로부터 자동으로 결정된다.

상기 도 7의 (a)의 문서 집합에서 문서 0의 오프셋 1에 나타나는 2-gram "BC"가 속해 있는 4-서브시퀀스는 "ABCD"이므로, 애트리뷰트 S의 값은 "ABCD"로 결정된다.

애트리뷰트 O1, O2의 값은 각각 4-서브시퀀스 "ABCD"에서 2-gram "BC"가 나타난 오프셋 1과 문서 0에서 4-서브시퀀스 "ABCD"가 나타난 오프셋 0으로 결정된다.

다음 상기 단계(S320)에서는 다음의 보조정리 2를 통해 상기 단계(S310)에서 구한 SNDO₁O₂ 릴레이션에 의미 있는 다치 종속성이 존재함을 보인다.

보조정리 2. SNDO₁O₂ 릴레이션에는 S→→NO1와 S→→DO2의 의미 있는 다치 종속성이 존재한다. 이때, S는 수퍼키가 아니다.

이에 대한 증명은 다음과 같다.

다치 종속성의 정의(Jeffery D. Ullman, Principles of Database and Knowledge-Base Systems Vol. I, Computer Science Press, USA, 1988., Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems, Addison Wesley, 4th ed., 2003., Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, Database Systems Concepts, McGraw-Hill, 4th ed., 2001.)에 따르면 스키마 R을 따르는 임의의 릴레이션 r에서 μ, ν∈ｒ, μ[X] = ν[X]인 두 개의 투플 μ, ν가 존재할 때, 다음의 세 가지 조건을 만족하는 두 개의 투플 φ,Ψ도 반드시 존재하면, X→→Y의 다치 종속성이 성립한다(X, Y는 R의 부분 집합).

그리고, Y

X이고, X∪Y≠ R(즉, R-X-Y≠Ø)(Y와 R-X-Y가 애트리뷰트 공집합이 아니다)이면, 다치 종속성 X→→Y는 의미 있는 다치 종속성이다(Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems, Addison Wesley, 4th ed., 2003., Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, Database Systems Concepts, McGraw-Hill, 4th ed., 2001.).

즉, 애트리뷰트 X의 임의의 값에 대해 애트리뷰트 Y의 값들과 애트리뷰트 R-X-Y의 값들이 카테시안 곱(Cartesian product) 형태를 이루면 의미 있는 다치 종속성이 성립한다(Raghu Ramakrishnan, Database Management Systems, McGraw-Hill, 1998.)

1. φ[X] = Ψ[X] = μ[X] = ν[X]

2. φ[Y] = μ[Y] and φ[R-X-Y] = ν[R-X-Y]

3. Ψ[Y] = ν[Y] and Ψ[R-X-Y] = μ[R-X-Y]

주어진 문서 집합으로부터 추출되는 m-서브시퀀스들의 집합을 {S_1,...,S_r}라 할때, m-서브시퀀스 S_i로부터 추출되는 n-gram들의 집합 {N_i1,...,N_iq}은 S_i가 나타나는 문서들의 집합 {D_i1 _,...,D_ip}로부터도 항상 추출된다(1≤ i≤ r).

따라서, SNDO₁O₂ 릴레이션에서 애트리뷰트 S의 값이 m-서브시퀀스 S_i인 투플들에 대해, S_i로부터 추출된 n-gram들을 나타내는 애트리뷰트 NO₁의 값들과 S_i가 출현한 문서들을 나타내는 애트리뷰트 DO₂의 값들은 항상 카테시안 곱 형태를 이룬다.

R = SNDO₁O₂, X = S, Y = NO₁, R-X-Y = DO₂이라고 하면, 애트리뷰트 X의 임의의 값에 대해 애트리뷰트 Y의 값들과 애트리뷰트 R-X-Y의 값들이 카테시안 곱 형태를 이루므로 위의 세 가지 조건이 만족된다. Y = DO₂라고 하여도 마찬가지의 사실이 성립한다.

또한, NO1

S, DO2

S, NO1 ∪ S ≠ SNDO₁O₂, DO₂ ∪ S ≠ SNDO₁O₂이다.

따라서, SNDO₁O₂ 릴레이션에는 S→→NO₁과 S→→DO₂의 의미 있는 다치 종속성이 존재한다. 이때, 도 12의 우측의 반대 예제에서 보여지듯이 S는 수퍼키가 아니다.

SNDO₁O₂ 릴레이션에 의미 있는 다치 종속성이 존재하는 이유를 직관적으로 설 명하면 임의의 m-서브시퀀스가 어떤 문서들에 나타나는가와 그 m-서브시퀀스로부터 어떤 n-gram들이 추출되는가는 서로 무관계이기 때문이다.

이와 같이 서로 무관계인 애트리뷰트들이 하나의 릴레이션에 같이 있을 경우에는 다치 종속성이 존재하게 된다( Jeffery D. Ullman, Principles of Database and Knowledge-Base Systems Vol. I, Computer Science Press, USA, 1988., Raghu Ramakrishnan, Database Management Systems, McGraw-Hill, 1998., Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems, Addison Wesley, 4th ed., 2003., Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, Database Systems Concepts, McGraw-Hill, 4th ed., 2001.)

SNDO₁O₂ 릴레이션에서는 문서와 n-gram 사이의 무관계성으로 인해 문서 식별자와 n-gram의 가능한 모든 조합을 표현하는 투플들이 각 m-서브시퀀스마다 유지된다.

도 12의 우측은 SNDO₁O₂ 릴레이션에 의미 있는 다치 종속성 S→→NO₁와 S→→DO₂가 존재하는 예이다. 도 12의 우측은 SNDO₁O₂ 릴레이션에서 애트리뷰트 S의 값이 "ABCD"인 회색으로 칠해진 부분을 보면, 두 애트리뷰트 N, O₁의 값 ("AB", 0), ("BC", 1), ("CD", 2)에 대해 두 애트리뷰트 D, O₂의 값 (0, 0), (3, 3), (4, 6)이 반복해서 나타나는 중복이 있다. 즉, S="ABCD"일때 NO₁과 DO₂가 카테시안 곱을 이룬다. 애트리뷰트 S의 나머지 값들에 대해서도 이러한 반복이 나타남을 볼 수 있다. 상기 단계(S330)에서는 상기 단계(S320)에서 확인된 위치 정보의 중복을 제거하기 위해 상기 단계(S310)에서 구한 릴레이션을 제4정규형을 따르도록 두 개의 릴레이션으로 분해한다.

우선, 다음의 정리 2를 통해 SNDO₁O₂ 릴레이션이 제4정규형이 아님을 보이고, 다음으로 보조정리 3을 통해 SNDO₁O₂ 릴레이션을 분해한 SNO₁과 SDO₂ 두개의 릴레이션이 각각 제4정규형이 됨을 보인다.

정리 2. SNDO₁O₂릴레이션은 제4정규형이 아니다.이에 대한 증명은 다음과 같다.

의미 있는 다치 종속성 S→→NO₁가 존재하며, S가 수퍼키가 아니다.

보조정리 3. SNDO₁O₂ 릴레이션을 SNO₁과 SDO₂의 두 개의 릴레이션으로 분해 했을 때, 각각의 릴레이션은 제4정규형이다. 이에 대한 증명은 다음과 같다.

SNO₁ 릴레이션에 있는 다치 종속성은 SO₁→→N와 SNO₁→→S|N|O₁이다. 또한, SDO₂ 릴레이션에 있는 다치 종속성은 DO₂→→S와 SDO₂→→S|D|O₂이다. 이 다치 종속성들은 모두 무의미 다치 종속성이므로 제4정규형을 위배하지 않는다.

다음은 상기 단계(S340)에 대하여 살펴본다.

상기 단계(S340)에서는 상기 단계(S330)에서 SNDO₁O₂ 릴레이션을 제4정규형을 따르도록 분해함으로써 얻게 되는 두 개의 릴레이션이 각각 2단계 n-gram 역색인의 프런트-엔드 역색인과 백-엔드 역색인으로 표현됨을 다음의 정리 3를 통해 보인다.

이로 인해 2단계 n-gram 역색인에는 의미 있는 다치 종속성에 의한 중복이 제거됨이 이론적으로 증명된다(Jeffery D. Ullman, Principles of Database and Knowledge-Base Systems Vol. I, Computer Science Press, USA, 1988.).

정리 3. SNDO₁O₂ 릴레이션을 제4정규형을 따르도록 분해한 SNO₁ 릴레이션과 SDO₂ 릴레이션은 각각 2단계 n-gram 역색인의 프런트-엔드 역색인과 백-엔드 역색인이 된다. 이에 대한 증명은 다음과 같다.

SNO₁ 릴레이션은 애트리뷰트 N, S, O₁이 각각 용어, m-서브시퀀스 식별자, 위치정보인 프런트-엔드 역색인 형태로 표현될 수 있고, SDO₂ 릴레이션은 애트리뷰트 S, D, O₂가 각각 용어, 문서 식별자, 위치정보인 백-엔드 역색인 형태로 표현될 수 있다.

따라서, SNDO₁O₂ 릴레이션을 SNO₁ 릴레이션과 SDO₂ 릴레이션으로 분해한 결과는 2단계 n-gram 역색인의 프런트-엔드 역색인과 백-엔드 역색인이 된다.

도 13은 도 12의 SNDO₁O₂ 릴레이션이 두 개의 릴레이션 SNO₁과 SDO₂로 분해된 결과이다. SDO₂ 릴레이션의 애트리뷰트 S의 값에서 괄호안의 값은 m-서브시퀀스에 부여된 식별자를 나타낸다.

도 12의 SNDO₁O₂ 릴레이션에서 회색으로 칠해진 투플들은 도 13의 SNO₁ 릴레이션과 SDO₂ 릴레이션에서의 회색으로 칠해진 투플들로 분해된다. 도 12에서 보이는 NO₁과 DO₂ 사이의 카테시안 곱이 도 13에서는 제거됨을 알 수 있다.

SNO₁ 릴레이션을 역색인 형태로 표현하면 도 7의 프런트-엔드 역색인과 동일해짐을알 수 있고, SDO₂ 릴레이션을 역색인 형태로 표현하면 도 7의 백-엔드 역색인과 동일해짐을 알 수 있다.

상기와 같은 본 발명의 2단계 n-gram 역색인 구조는 n-gram 역색인에 비해 색인의 크기가 크게 줄어들고 질의 처리 성능이 향상되는데, 이에 대하여 분석해 보면 다음과 같다.

먼저, 색인 크기에 대하여 분석한다.

2단계 n-gram 역색인의 크기에 영향을 미치는 파라미터는 n-gram의 길이인 n과 m-서브시퀀스의 길이인 m이다. 이 중에서 n의 값은 일반적으로 응용에 따라 결정되는 수치인 반면, m의 값은 본 발명에서 2단계 n-gram 역색인의 구성을 위해 도입한 수치로서 자유롭게 조절할 수 있다.

따라서, 2단계 n-gram 역색인의 크기를 최소로 만드는 최적 길이 m(이하, m_o라 칭한다)의 값을 결정하기 위한 방법을 제시하고, 그에 따른 2단계 n-gram 역색인의 크기를 분석한다.

다음의 표 1에서 m_o를 구하기 위해 사용되는 표기법을 정의한다. 여기에서, n-gram 역색인과 2단계 n-gram 역색인의 크기로는 색인에 저장된 오프셋들의 개수를 사용한다.

이는 역색인의 크기가 문서상에서 용어가 나타난 오프셋들의 개수에 대체적으로 비례하기 때문이다(I. Witten, A. Moffat, and T. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, Los Altos, California, 2nd ed., 1999.)

표 1. 최적 길이 m_o를 구하기 위해 사용되는 표기법

기 호	정의/의미
size_ngram	n-gram 역색인의 크기
size_front	2단계 n-gram 역색인에서의 프런트-엔드 역색인의 크기
size_back	2단계 n-gram 역색인에서의 백-엔드 역색인의 크기
S	문서 집합으로부터 추출되는 유일(unique)한 m-서브시퀀스들의 집합
k_ngram(s)	m-서브시퀀스 s에서 추출된 n-gram들의 개수
k_doc(s)	m-서브시퀀스 s가 문서 집합에서 나타난 횟수
αvg_ngram(S)	s ∈ S일때, k _ngram (s)의 평균값 (= (∑ _{s ∈ S} k _ngram (s)) / \| S \| )
αvg_doc(S)	s ∈ S일때, k _doc(s)의 평균값 (= (∑ _{s ∈ S} k _doc (s)) / \| S \| )

이제 분할(Decomposition)을 통해 색인의 크기가 감소하는 비율이 최대가 되는 m_o의 값을 결정하고자 하며, 이를 위해 다음의 정의 4에서 분할 효율을 정의한다.

정의 4. n-gram 역색인의 크기에 대한 2단계 n-gram 역색인의 크기의 비율의 역수를 분할 효율이라고 정의한다. 이를 표 1의 표기법으로 나타내면 아래와 같다.

정의 4의 분할 효율은 수식 (1)~(5)와 같이 계산할 수 있다. 여기에서, SNDO₁O₂ 릴레이션을 이용하여 n-gram 역색인 혹은 2단계 n-gram 역색인에서의 오프셋 개수를 계산한다. SNDO₁O₂ 릴레이션은 n-gram 역색인을 제1정규형으로 표현한 릴 레이션이므로, 오프셋의 개수가 곧 투플의 개수가 된다.

n-gram 역색인을 나타내는 SNDO₁O₂ 릴레이션에서 애트리뷰트 S의 값이 s인 투플들의 개수는 k_ngram (s) × k_doc (s)이다.

이는 상기 보조정리 2에서 보인 바와 같이 SNDO₁O₂ 릴레이션에서 애트리뷰트 S의 값에 대해 애트리뷰트 NO₁과 애트리뷰트 DO₂의 값들이 카테시안 곱 형태를 이루기 때문이다. 따라서, n-gram 역색인의 전체 크기는 모든 m-서브시퀀스에 대한 k_ngram (s) × k_doc (s)의 합계인 수식 (2)가 된다.

프런트-엔드 역색인에 해당하는 SNO₁ 릴레이션에서 애트리뷰트 S의 값이 s인 투플들의 개수는 k_ngram(s)이다. 따라서, 프런트-엔드 역색인의 전체 크기는 모든 m-서브시퀀스에 대한 k_ngram(s)의 합계인 수식 (3)이 된다.

백-엔드 역색인에 해당하는 SDO₂ 릴레이션에서 애트리뷰트 S의 값이 s인 투플들의 개수는 k_doc(s)이다. 따라서, 백-엔드 역색인의 전체 크기는 모든 m-서브시퀀스에 대한 k_doc(s)의 합계인 수식 (4)가 된다. 그 결과로서 수식 (1)~(4)로부터 수식 (5)를 얻는다.

분할 효율은 문서 집합을 전처리하여 S, k_ngram(s), k_doc(s)를 구함으로써 계산할 수 있다. 이는 문서 집합을 순차적으로 한 번 스캔함으로써 처리할 수 있다(O(data size)). 이와 같이 m_o의 후보가 될만한 m값들에 대해 분할 효율을 구하고, 그 중 최대 분할 효율을 가지는 m_o를 찾는다.

수식 (5)에서 알 수 있듯이 n-gram 역색인의 공간 복잡도는 O(|S| × (αvg_ngram×αvg_doc))이고, 2단계 n-gram 역색인의 공간 복잡도는 O(|S|×(αvg_ngram + αvg_doc))이다. 수식 (5)에서 분할 효율이 최대가 되는 조건은 주어진 데이타에 대해 αvg_ngram과 αvg_doc이 같아지는 경우이다.

그런데, αvg_doc은 데이타가 커지면 자연히 증가하는 반면, αvg_ngram은 m이 커져야 증가한다. 따라서, 주어진 데이타를 전처리하여 m_o를 구해보면 데이타가 클 수 록 m_o도 더 큰 값으로 결정되는 경향이 있다.

즉, 주어진 데이타가 커질 때 αvg_ngram과 αvg_doc도 증가하고, 이때 (αvg_ngram + αvg_doc)보다 (αvg_ngram × αvg_doc)이 더 많이 증가하므로 분할 효율도 더 커진다. 따라서, n-gram/2L 역색인은 더 큰 데이타에서 색인의 크기를 보다 더 효과적으로 줄여주는 좋은 특성을 가진다.

다음은 질의 처리 성능의 분석에 대하여 살펴본다.

2단계 n-gram 역색인의 질의 처리 성능에 영향을 미치는 파라미터는 질의 문자열 Q의 길이인 Len(Q)와 m, n이다. 따라서 이하에서는 이들 파라미터의 변화에 따른 2단계 n-gram 역색인의 질의 처리 성능의 경향을 알기 위한 개략적인 분석을 한다.

먼저, 분석을 단순화하기 위해 다음 두 가지 가정을 한다.

첫째, 역색인에서의 질의 처리 시간은 액세스하는 오프셋들의 개수와 액세스하는 포스팅 리스트의 개수에 비례한다고 가정한다.

포스팅 리스트를 액세스할 때에는 디스크 헤드를 옮기는 시크 타임(seek time) 등이 발생하므로 액세스하는 포스팅 리스트의 개수가 많아질수록 추가적으로 소요되는 질의 처리 시간이 커진다.

둘째, 알파벳을 ∑라 할때, 문서 데이타가 매우 커서 모든 가지 수(=│∑│ⁿ)의 n-gram들이 n-gram 역색인 및 프런트-엔드 역색인에 색인되고, 마찬가지로 모든 가지 수(=│∑│^m)의 m-서브시퀀스들이 백-엔드 역색인에 색인된다고 가정한다(예를 들어, │∑│=26, m=5이면, │∑│^m= 11,881,376). 질의 처리 성능은 특히 대용량 데이타에서 중요하므로 이러한 가정은 합리적이라고 할 수 있다.

2단계 n-gram 역색인의 질의 처리 시간에 대한 n-gram 역색인의 질의 처리 시간의 비율은 수식 (6)~(9)와 같이 계산할 수 있다.

포스팅 리스트당 오프셋들의 평균 개수를 k_offset이라 하고, 질의 처리를 위해 액세스하는 포스팅 리스트들의 개수를 k_plist라 할때, 질의 처리를 위해 액세스하는 오프셋들의 개수는 k_offset × k_plist이다.

n-gram 역색인에서 k_offset은 (size_ngram /│∑│ⁿ)이고, k_plis는 (Len(Q) - n + 1)이므로, n-gram 역색인의 질의 처리 시간은 수식(6)이 된다.

2단계 n-gram 역색인의 프런트-엔드 역색인에서 k_offset은 (size_front / │∑│ ⁿ)이고, k_plist는 n-gram 역색인에서와 마찬가지로 (Len(Q) - n + 1)이므로, 질의 처리 시간은 수식 (7)이 된다.

2단계 n-gram 역색인의 백-엔드 역색인에서 k_offset은 (size_back / │∑│^m)이고, k_plist는 Q를 커버하는 m-서브시퀀스들의 개수인데, 그 개수는 Len(Q) < m인 경우와 Len(Q) ≥ m인 경우가 서로 다르다.

Len(Q) ≥ m인 경우, 도 9a의 S_i _+1,...,S_j _-1의 경우에 해당하는 m-서브시퀀스들의 개수는 (Len(Q) - m + 1)이고, S_i 또는 S_j의 경우에 해당하는 m-서브시퀀스들의 개수는 각각

│∑│^m-n-i이다. Len(Q) < m인 경우, 도 9b의 S_k의 경우에 해당하는 m-서브시퀀스들의 개수는 ((m - Len(Q) + 1)×|∑|^m-Len(Q))이고, S_p 또는 S_q의 경우에 해당하는 m-서브시퀀스들의 개수는 각각

│∑│^m-n-i이다.

따라서, 백-엔드 역색인에서의 질의 처리 시간은 수식 (8)이 된다. 수식 (9)은 2단계 n-gram 역색인의 질의 처리 시간에 대한 n-gram 역색인의 질의 처리 시간의 비율을 나타낸다.

size_ngram = |S| (αvg_ngram ×αvg_doc)이므로 수식 (9)로부터 n-gram 역색인의 질의 처리 시간의 복잡도는 O(|S|(αvg_ngram ×αvg_doc))이고, 마찬가지로 2단계 n-gram 역색인의 질의 처리 시간의 복잡도는 O(|S| (αvg_ngram +αvg_doc))이다.

즉, n-gram 역색인과 2단계 n-gram 역색인의 시간 복잡도는 공간 복잡도와 같다. 따라서, 2단계 n-gram 역색인은 n-gram 역색인에 비해 더 큰 데이타에서 질의 처리 성능을 보다 더 향상시켜주는 좋은 특성을 가진다.

상기 수식 (6)~(9)에서 알 수 있듯이 n-gram 역색인에서는 Len(Q)가 길어지는 것에 비례하여 질의 처리 시간이 증가한다. 그러나, 2단계 n-gram 역색인에서는 Len(Q)가 길어져도 질의 처리 시간이 거의 증가하지 않는다.

프런트-엔드 역색인의 경우 Len(Q)가 길어지는 것에 비례하여 질의 처리 시간이 증가하나 그 색인의 크기가 매우 작고, 백-엔드 역색인의 경우 ∑^m-n이 매우 커서(예를 들어, |∑|=26, m=6, n=3이면, |∑|^m-n=17,576) Len(Q)가 거의 영향을 미치지 못한다.

프런트-엔드 역색인의 크기가 작은 이유는 문서 집합보다 크기가 훨씬 작은 m-서브시퀀스들의 집합에 대해 색인이 구성되기 때문이다(예를 들어, 문서 집합의 크기가 1GByte이고 m=5일때, m-서브시퀀스 집합의 크기는 13 ~ 27MByte).

n-gram 역색인은 질의의 길이가 매우 긴 경우 질의 처리 시간도 매우 크다는 것이 문제점으로 지적되므로(Hugh E. Williams, "Genomic Information Retrieval," In Proc. the 14th Australasian Database Conferences, 2003.), Len(Q)가 길어질 때 질의 처리 성능이 좋은 것은 중요하다.

2단계 n-gram 역색인과 n-gram 역색인의 질의 처리 시간에 대한 더 자세한 분석을 하려면 포스팅 리스트를 액세스하는 시간을 고려해야 한다. 한 개의 포스팅 리스트를 액세스하는 시간을 α라 할 때, 추가적으로 소요되는 질의 처리 시간은 k_plist에 α를 곱하여 계산한다.

수식 (6)~(8)에 있는 k_plist 항을 이용하여 포스팅 리스트를 액세스하는 시간 plist_time을 구하면 수식 (10)~(12)가 된다.

수식 (10), (12)에서 알 수 있듯이 plist_time_ngram = plist_time_front이며, 따라서 2단계 n-gram 역색인은 포스팅 리스트 액세스 시간에 있어서 n-gram 역색인에 비해 plist_time_back만큼의 시간이 더 소요된다.

수식 (12)에서 k_plist는 Len(Q) ≥ m의 경우 (2

|∑|^m-n-i)가 지배적(dominant)이고, Len(Q) < m의 경우 (2

|∑|^m-n-i)가 지배적인데, 각각의 값은 m이 증가함에 따라 지수적으로 커진다.

그러므로, m-서브시퀀스의 길이로 m_o 대신 (m_o - 1)을 사용하면 색인 크기 측면에서 약간 손해를 보긴 하지만 질의 처리 성능 측면에서 크게 이득을 볼 수 있다.

또한, 본 발명에 의한 실험 결과 2단계 n-gram 역색인은 실제 1GByte의 텍스 트 데이터(TREC-1G)와 단백질 시퀀스 데이터(PROTEIN-1G)에 대한 실험을 통하여, m-서브시퀀스의 길이로 (m_o-1)을 사용했을 때, 2단계 n-gram 역색인은 n-gram 역색인에 비해 최대 1.9배(PROTEIN-1G, m=4) ~ 2.7배(PROTEIN-1G, m=5) 더 작은 크기를 가지면서, 동시에 3~18 범위의 길이를 가지는 질의들에 대해 질의 처리 성능을 최대 13.1배(PROTEIN-1G, m=4) 향상시켰다.

상술한 바와 같이, 본 발명의 바람직한 실시 예를 참조하여 설명하였지만, 해당 기술 분야의 숙련된 당업자는 하기의 특허청구범위에 기재된 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 또는 변형하여 실시할 수 있다.

이상에서 설명한 바와 같이, 본 발명은 n-gram 역색인에 존재하는 의미 있는 다치 종속성으로 인한 위치 정보의 중복을 제거함으로써 n-gram 역색인에 비해 그 크기를 크게 줄이고 질의 처리 성능을 향상시키는 효과를 가진다.

또한, 2단계 n-gram 역색인은 색인의 크기 측면에서 색인하려는 데이타의 크기가 클수록 n-gram 역색인에 비해 유리하다. 즉, 기존의 n-gram 역색인의 크기에 비한 2단계 n-gram 역색인의 상대적 크기는 데이타의 크기가 커질수록 작아진다.

또한, 질의 처리 성능 측면에서도 2단계 n-gram 역색인은 색인하려는 데이타의 크기가 클수록 n-gram 역색인에 비해 유리하다. 즉, 기존의 n-gram 역색인에 비 한 2단계 n-gram 역색인의 상대적인 질의 처리 성능은 데이타의 크기가 커질수록 좋아진다.

뿐만 아니라, 2단계 n-gram 역색인은 질의 문자열의 길이가 길어져도 질의 처리 시간이 거의 증가하지 않는다.

Claims

다수의 텍스트 정보가 저장되는 텍스트 정보 DB와 2단계 n-gram 역색인이 저장되는 역색인 정보 DB를 포함한 데이터 베이스부;

상기 데이터 베이스부에 저장된 텍스트 정보 DB를 관리하는 데이터 베이스 관리부; 및,

상기 데이터 베이스 관리부와 연동하여 상기 데이터 베이스부의 역색인 정보 DB에 2단계 n-gram 역색인을 생성하고, 상기 2단계 n-gram 역색인을 사용하여 질의를 처리하는 서버

를 포함하는 것을 특징으로 하는 2단계 n-gram 역색인을 구비한 색인 시스템.
제 1 항에 있어서,

상기 서버는 상기 2단계 n-gram 역색인을 생성하기 위한 색인 구성기와 상기 2단계 n-gram 역색인을 사용하여 질의를 처리하는 질의 처리기를 포함하는 것을 특징으로 하는 2단계 n-gram 역색인을 구비한 색인 시스템.
제 1 항에 있어서,

상기 2단계 n-gram 역색인은 문서로부터 추출된 서브시퀀스들을 용어로 사용하는 백-엔드 역색인, 및 상기 서브시퀀스로부터 추출된 n-gram들을 용어로 사용하는 프런트-엔드 역색인으로 된 것을 특징으로 하는 2단계 n-gram 역색인을 구비한 색인 시스템.
제 3 항에 있어서,

상기 백-엔드 역색인은 문서로부터 서로 일정 부분씩 겹치도록 추출된 소정 길이의 서브시퀀스들을 용어로서 사용하고, 각 서브시퀀스에 대한 포스팅 리스트에는 그 서브시퀀스가 문서상에서 나타난 위치 정보들을 저장하고,

상기 프런트-엔드 역색인은 상기 서브시퀀스로부터 1-슬라이딩 방식으로 추출된 소정 길이의 n-gram들을 용어로서 사용하고, 각 n-gram에 대한 포스팅 리스트에는 그 n-gram이 서브시퀀스 상에서 나타난 위치 정보들을 저장하는 것을 특징으로 하는 2단계 n-gram 역색인을 구비한 색인 시스템.
데이터베이스의 각 문서로부터 길이 m의 m-서브시퀀스들을 서로 일정 부분씩 겹치도록 추출하면서 m-서브시퀀스가 문서상에서 나타난 위치 정보들를 기록하는 제 1 단계;

상기 제 1 단계에서 기록한 각 위치 정보에 대해, 소정의 m-서브시퀀스가 소정 문서의 오프셋에서 나타났다면 상기 소정의 m-서브시퀀스에 해당하는 백-엔드 역색인의 용어에 대한 포스팅 리스트에 해당 포스팅을 추가하여 백-엔드 역색인을 구성하는 제 2 단계;

상기 제 1 단계에서 얻어진 m-서브시퀀스 집합의 각 m-서브시퀀스로부터 n-gram들을 추출하면서 n-gram이 m-서브시퀀스 상에서 나타난 위치 정보들을 기록하는 제 3 단계; 및

상기 제 3 단계에서 기록한 각 위치 정보에 대해, 소정의 n-gram이 소정의 m-서브시퀀스의 오프셋에서 나타났다면 상기 소정의 n-gram에 해당하는 프런트-엔 드 역색인의 용어에 대한 포스팅 리스트에 해당 포스팅을 추가하여 프런트-엔드 역색인을 구성하는 제 4 단계;

로 이루어짐을 특징으로 하는 2단계 n-gram 역색인 구성방법.
제 5 항에 있어서, 상기 제 1 단계에서는 상기 m-서브시퀀스들을 n-1(n : n-gram의 길이)씩 겹치도록 추출하는 것을 특징으로 하는 2단계 n-gram 역색인 구성방법.
제 5 항에 있어서, 상기 제 1 단계에서는 마지막 m-서브시퀀스의 길이가 m보다 작을 경우, 문자열의 뒷부분에 공백 문자들을 덧붙여서 길이가 m이 되도록 하는 것을 특징으로 하는 2단계 n-gram 역색인 구성방법.
제 5 항에 있어서, 상기 제 3 단계에서 상기 서브시퀀스로부터 n-gram들의 추출은 1-슬라이딩 방식으로 행하는 것을 특징으로 하는 2단계 n-gram 역색인 구성방법.
문서로부터 추출된 서브시퀀스들을 용어로 사용하는 백-엔드 역색인 및 상기 서브시퀀스로부터 추출된 n-gram들을 용어로 사용하는 프런트-엔드 역색인을 사용하여 질의를 처리하는 방법에 있어서,

소정 질의를 n-gram들로 분할하는 제 1 단계;

상기 프런트-엔드 역색인을 사용하여 상기 제 1 단계에서 구한 각 n-gram들에 대한 포스팅 리스트들을 m-서브시퀀스 식별자로 머지-아우터-조인(merge-outer-join)하면서, 상기 질의를 커버 하는 m-서브시퀀스들을 소정 집합에 추가하는 제 2 단계; 및

상기 백-엔드 역색인을 사용하여 상기 제 2 단계에서 구한 소정 집합에 포함된 m-서브시퀀스들에 대한 포스팅 리스트들을 문서 식별자로 머지-아우터-조인하면서, 소정의 동일한 문서로부터 추출된 m-서브시퀀스들의 집합이 상기 질의를 포함하는지를 검사하여 질의에 포함되면 상기 소정의 동일한 문서를 질의 결과로 반환하는 제 3 단계;

로 이루어짐을 특징으로 하는 2단계 n-gram 역색인을 이용한 질의 처리 방법.
제 9 항에 있어서, 상기 m-서브시퀀스가 질의를 커버하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인하는 것을 특징으로 하는 2단계 n-gram 역색인을 이용한 질의 처리 방법.
제 9 항에 있어서, 상기 제 3 단계에서의 집합이 질의를 포함하는지는 머지 아우터 조인되는 포스팅들이 가지고 있는 오프셋 정보를 이용하여 확인하는 것을 특징으로 하는 2단계 n-gram 역색인을 이용한 질의 처리 방법.
n-gram 역색인으로부터 프런트-엔드 역색인과 백-엔드 역색인으로 구성되는 역색인을 도출하는 방법에 있어서,

n-gram 역색인을 제1정규형(1NF : First Normal Form)을 따르는 릴레이션으로 표현하는 제 1 단계;

상기 제 1 단계에서 구한 릴레이션에 의미 있는 다치 종속성으로 인한 위치 정보의 중복이 존재함을 확인하는 제 2 단계;

상기 제 2 단계에서 확인된 위치 정보의 중복을 제거하기 위해 상기 제 1 단계에서 구한 릴레이션을 제4정규형(4NF : Fourth Normal Form)을 따르도록 두 개의 릴레이션으로 분해하는 제 3 단계; 및

상기 제 3 단계에서 구한 두 개의 릴레이션을 각각 프런트-엔드 역색인과 백-엔드 역색인으로 표현하는 제 4 단계;

로 이루어짐을 특징으로 하는 2단계 n-gram 역색인 도출 방법.