KR100414236B1

KR100414236B1 - 데이터의 검색을 위한 서치 시스템 및 방법

Info

Publication number: KR100414236B1
Application number: KR10-2001-7000436A
Authority: KR
Inventors: 너트 매그니 리즈빅
Original assignee: 패스트 서치 & 트랜스퍼 에이에스에이
Priority date: 1998-07-10
Filing date: 1999-07-09
Publication date: 2004-01-07
Also published as: PT1095326E; PL345714A1; DE69900854T2; DE69900854D1; US6377945B1; NO983175L; CN1317114A; CA2337079C; AU4937099A; DK1095326T3; KR20010071841A; JP2002520712A; EP1095326A1; WO2000003315A3; WO2000003315A2; HK1040784A1; CA2337079A1; BR9912015B1; IS5796A; ATE212736T1

Abstract

정보 검색을 위한 서치 시스템으로서, 텍스트(T)를 저장하기 위한 데이터 구조, 시퀀스(P)의 워드 및/또는 심볼들 사이의 근사 매칭을 위한 편집 거리 메트릭을 포함하는 결합된 메트릭(M), 워드 또는 심볼의 시퀀스(S)를 시퀀스(P)로 변환하는 편집 연산을 위한 가중 코스트 함수 및 텍스트(T)와 쿼리(Q) 각각의 접미어 트리 표현에서 워드 또는 워드 시퀀스 사이의 매칭도를 결정하기 위한 서치 알고리즘을 포함한다. 상기 알고리즘은 쿼리(Q)에 의해 데이터 구조를 서치하여, 쿼리에 대해 특정된 매칭을 갖는 정보를 검색한다. 서치 시스템에서 정보를 검색하기 위한 방법으로서, 워드의 접미어들을 워드 시퀀스 정보로서 텍스트(T)에 저장하기 위한 워드-간격의 접미어 트리 및 워드 시퀀스(S,P)에 대한 워드 크기-종속 편집 거리 메트릭을 발생시키고 편집 연산에 대한 워드-가중 코스트 함수들을 포함하며, 모든 매칭들에 대해 편집 거리를 계산하므로써 워드 시퀀스(S_R) 또는 검색된 정보(R) 및 쿼리(Q)에 대한 워드 시퀀스(P_Q)사이의 매칭도를 결정한다. 근사 서치 엔진에서의 사용도 본 발명에 포함된다.

Description

데이터의 검색을 위한 서치 시스템 및 방법{A SEARCH SYSTEM AND METHOD FOR RETRIEVAL OF DATA}

다양한 인간 지식의 분야에서 엄청난 양의 정보가 수집되어 컴퓨터 메모리 시스템에 저장된다. 컴퓨터 메모리 시스템이 계속해서 공용 데이터 통신 네트워크에 링크되기 때문에, 공용 또는 개인적인 정보를 서치하고 검색하기 위한 시스템 및 방법들을 개발하려는 노력이 점점 더 증가하고 있다. 그러나, 현재의 데이터 서치 방법은 이런 식으로 저장되는 정보를 효과적으로 검색하고 사용하는 가능성을 현저하게 축소시키는 한계를 갖는다.

정보는 서로 다른 데이터 형으로 저장될 수 있으며, 정보 서치 및 검색에 관련하여서는 동적 데이터 및 정적 데이터를 구별하는 것이 유용할 것이다. 동적 데이터는 빈번하게 계속해서 변화하여 유효한 데이터 집합이 항상 다른 데이터이고, 반면에 정적 데이터는 거의 변하지 않거나 전혀 변하지 않는 데이터이다. 예를 들어, 주식 가격 같은 경제 데이터 또는 기상 데이터는 매우 빨리 변하는 속성을 갖기 때문에 동적 데이터이다. 반면에, 도서 및 문서의 기록 저장은 보통 변하지 않고 따라서 정적 데이터이다. 데이터의 휘발성(volatility)이라는 개념은 정보가 얼마나 오랫동안 유효한가에 관련된 것이다. 데이터의 휘발성은 정보가 서치되고 검색되는 방식과 관련이 있다. 많은 양의 데이터가 서치를 편리하게 하기 위한 구조를 필요로 하지만, 그러한 구조화에 드는 시간 코스트(cost)가 데이터가 유효한 시간보다 많아서는 안된다. 구조화에 드는 코스트는 데이터의 양에 따라 변하며 정보를 서치하기 위한 데이터 구조화 작업에 있어서는 데이터의 양과 휘발성을 모두 고려하여야 한다. 수집된 정보는 데이터 베이스에 저장되고 이 저장된 정보들은 구조화되기도 하고 구조화되지 않기도 한다. 또한, 데이터 베이스에는 이미지, 비디오, 소리 및 형식화 되었거나(formatted) 주석이 달린(annotated) 텍스트를 포함하는 복합 문서들을 포함한 여러 가지 종류의 문서들이 포함된다. 특정의 구조화된 데이터베이스들은 데이터 서치 및 검색을 촉진하기 위해 통상적으로 색인을 제공받는다. 월드 와이드 웹(WWW)의 성장은 꾸준히 성장하는 복합 및 하이퍼 링크된 문서의 집합을 제공한다. 이 많은 문서들은 구조화된 데이터 베이스에 수집되지도 않고, 빠른 서치를 촉진하는 아무런 색인들도 사용가능하지 않다. 그러나, 월드 와이드 웹에서 문서 서치의 필요성은 명백하며, 그리하여 많은 소위 서치 엔진들이 개발되어 왔고, 적어도 어느 정도까지는 월드 와이드 웹 정보의 서치를 가능하게 만들었다.

서치 엔진과 함께, 통상적으로 정보의 서치 및 검색을 위한 하나 이상의 룰(rule)이 요구될 것이라고 이해된다. 적절한 서치 시스템에 더하여, 서치 엔진은 또한 예컨대 많은 URL(Uniform Resource Locator)들로부터의 텍스트까지 포함하는 색인을 포함한다. 그러한 서치 엔진들로는 Alta Vista, Inktomy technology의 HotBot, Infoseek, Excite 및 Yahoo가 있다. 이 모든 서치 엔진들은 월드 와이드 웹에서 정보의 서치 및 검색을 수행하는데 편리함을 제공한다. 그러나, 그 속도 및 효율이 결코 월드 와이드 웹 상에 사용가능한 막대한 정보를 서치하기에 충분하지 않으며, 따라서 이러한 서치 엔진들의 서치 및 검색 효율은 개선되어야 할 점들이 많다.

많은 텍스트 문서 집합의 서치는 보통 수개의 쿼리(query) 형태로 행해질 수 있다. 가장 흔한 쿼리 형태는 매칭(matching) 또는 이것의 변형이다. 쿼리된 정보에 나타나야할 키워드 또는 키워드의 집합을 특정하므로써, 상기 서치 시스템은 이런 요구사항을 충족시킬 모든 문서를 검색하게 된다. 기본적인 서치 방법은 소위 단일 키워드 매칭(single keyword matching)을 기초로 한다. 키워드(p)가 서치되고 이 워드를 포함하는 모든 문서들이 검색될 것이다. 키워드의 접두어(prefix;p)를 서치하는 것도 가능하며 그 문서 내의 이 접두어가 나타나는 모든 문서가 검색될 것이다. 키워드로 서치하는 대신에, 서치는 종종 소위 완전 구 매칭(exact phrase matching)에 기초를 두기도 하는데, 이 서치는 특정 시퀀스 내의 수개의 단일 키워드를 사용한다. 당업자에게 잘 알려진 바와 같이, 많은 서치 시스템에서 키워드 구의 완전 매칭은 정보를 필터링(filtering) 할 수 있는, 예컨대 AND, OR, NOT과 같은 불리안(Boolean) 연산자를 사용하여 행해진다.; 예를 들어, AND 연산자를 사용하는 경우에, AND 연사자에 의해 연결된 두개의 키워드를 포함하는 모든 문서들이 리턴(return)될 것이다. 또한 NEAR 연산자는 문서 텍스트내에서, 매칭되고 서로에게 "가까이" 위치하는 키워드를 리턴하는데 사용되어 왔다. 많은 구조화된 데이터베이스에서 데이터베이스에 포함된 문서들은 주석 첨가(annotated), 예컨대 문서의 어떤 부분 또는 타입을 표시하는 필드(field)가 제공되었다. 이것은 문서의 일부분에서 만의 매칭을 위한 서치를 가능케하고, 쿼리된 정보가 미리 알려져 있을 경우에 유용하다.

텍스트 문서를 서치를 하는 경우에, 데이터는 구조화되어 있고 영어나 노르웨이어 등과 같은 몇몇 자연어로 표기되어 있을 가능성이 많다. 어떤 내용이 있는 문서를 서치하는 경우에, 쿼리와 거의 매칭되는 키워드 또는 구를 매칭시키기 위해 근접성 메트릭(proximity metric)을 사용하는 것이 가능하다. 키워드 및 구에서 에러를 허용하는 것은 근접 서치를 위한 흔한 방법이며, 백과사전을 사용하는 방법 또한 흔히 사용된다. 근접 서치는 검색된 정보와 쿼리 사이의 부분적인 매치가 있을 것만을 요구한다. 국제 사무용 기기 조합(International Business Machines Corp.)에 양도되었으며 "변화 가능한 길이 데이터 시퀀스 매칭 방법 및 장치"라는 표제가 붙어 있으며 국제 공개된 출원 WO96/00945(Doeringer al.)은 엔트리를 저장하고 적어도 부분적인 매칭, 바람직하게는 엔트리로부터 가장 긴 부분 매칭 또는 서치 인자(입력 키)의 모든 부분 매칭을 검색하기 위한 트리같은 구조를 갖는 데이터 베이스의 구성, 유지 및 사용을 개시한다.일반적인 종래 기술을 더 살펴보기 위해, 국제 공개된 특허 출원 WO92/15954(Kimball등, U.S.A. Red Brick System에게 양도됨,) 및 US 특허 번호 제 5,627,748호(Baker등, U.S.A. Lucent Technologies, Inc., 에게 양도됨. )에 대해 언급하고자 한다. 이들 특허 출원은 모두 정사각 행렬에서 서치/매칭을 위한 접미어 트리 형태의 데이터 구조를 개시한다. 이 두가지 발명 중 어느 것도, 매칭을 하는 동안 링크드 리스트(linked list)를 사용하는 것을 제외하고는 보통의(regular) 접미어 트리 이상의 것을 개시하지 않으며, 근사 매칭을 위한 서치를 할때 서치 공간을 제한하는 접근 방법을 제안하지 않는다. 그러나, 그러한 접근 방법은 접미어 트리에 기초한 데이터 구조의 서치할때, 특히 월드 와이드 웹에 찾을 수 있는 것과 같이 엄청난 양의 문서 집합에서의 근사 매칭을 위한 서치에 적용할 때는 가장 바람직한 방법일 것이다.

본 발명은 정보 검색(retrieve), 특히 텍스트(T)의 형태로 저장된 정보를 포함하는 정보 검색(retrieve)을 위한 서치(search) 시스템으로서, 상기 텍스트(T)는 워드 및/또는 심볼(s) 및 그들의 시퀀스(S)를 포함하고, 상기 정보 검색은 워드 및/또는 심볼(q) 및 그들의 시퀀스들(P)을 포함하는 쿼리(Q;query)와 상기 텍스트(T)로부터의 워드 및/또는 심볼 및 그들의 시퀀스들을 포함하는 검색된 정보(R) 사이의 고정되어 있거나 혹은 변화하는 매칭도에 따라 발생하고, 상기 서치 시스템은 상기 텍스트(T)의 적어도 일부분을 저장하기 위한 데이터 구조 및 쿼리(Q)와 검색된 정보(R) 사이의 매칭도를 측정하는 메트릭(metric;M)을 포함하고, 상기 서치 시스템은 서치, 특히 키워드(kw)를 기초로 전문 서치를 수행하기 위한 서치 알고리즘을 구현하는 서치 시스템; 및 정보 검색, 특히 텍스트(T)의 형태로 저장된 정보를 포함하는 정보를 검색하기 위한 서치(search) 시스템에서 정보를 검색하기 위한 방법으로서, 상기 텍스트(T)는 워드, 심볼(s) 및 그들의 시퀀스(S)를 포함하고, 상기 정보 검색은 워드 및/또는 심볼(q) 및 그들의 시퀀스들(P)을 포함하는 쿼리(Q)와 텍스트(T)로부터의 워드 및/또는 심볼 및 그들의 시퀀스들을 포함하는 검색된 정보(R) 사이의 고정되어 있거나 혹은 변화하는 매칭도에 따라 발생하고, 상기 서치 시스템은 상기 텍스트(T)의 적어도 일부분을 저장하기 위한 데이터 구조 및 쿼리(Q)와 검색된 정보(R) 사이의 매칭도를 측정하는 메트릭(M)을 포함하고, 상기 서치 시스템은 서치, 특히 키워드(kw)를 기초로한 전문 검색을 수행하기 위한 서치 알고리즘을 구현하고, 상기 텍스트(T)에서의 정보는 워드(s) 및 워드 시퀀스(S)들로 분할되고, 상기 워드는 워드 경계 텀(word boundary term)에 의해 분리된 전체 텍스트의 하위 스트링이며 또한 심볼의 시퀀스를 형성하고, 각 워드는 심볼의 시퀀스로서 구조화 되는 방법에 관한 것이며, 본 발명은 또한 상기 서치 시스템의 용도에도 관련되어 있다.

도 1은 접미어 트리의 예이다.

도 2는 본 발명에 사용되는 것과 같은 워드-간격의 희소 접미어 트리의 예이다.

도 3은 종래 기술에서 알려진 소위 패트리샤 트라이(PATRICIA trie)의 예이다.

도 4는 본 발명에 사용되는 것과 같은 워드-간격의 희소 접미어 트리의 추가적인 예이다.

도 5는 본 발명에 사용되는 것과 같은 명시적으로 저장된 워드 시퀀스의 예이다.

도 6은 본 발명에 사용되는 것과 같은 나뭇잎 노드 구조(leaf node structure)이다.

도 7은 본 발명에 따른 서치 시스템을 갖는 서치 엔진의 개략적인 구조이다.

본 발명의 주목적은 서치 시스템 및 많은 양의 데이터에서 정보를 빠르고 효율적으로 서치 및 검색 하기 위한 방법을 제공하는 것이다. 특히 본 발명은 분산된 대량의 데이터 저장소를 갖는 정보 시스템, 예컨대 인터넷의 서치를 위한 서치 엔진을 구현하기에 적합한 서치 시스템을 제공하는 것이다. 본 발명에 따른 서치 시스템은 결코 영숫자(alphanumeric) 심볼 형태로 저장된 정보를 서치하고 검색하는 것으로 제한되지 않지만, 여기에 사용되는 워드 텍스트가 전체적 또는 부분적으로 심볼의 집합으로 표현되는 경우에는 이미지로 해석될 수도 있기 때문에, 디지털화된 이미지 및 그래픽 심볼들의 형태로 저장된 정보를 서치하고 검색하는 데에도 동등하게 적용될 수 있다는 것이 이해되어야 한다. 본 발명에 따른 서치 시스템은 상업적으로 가용한 컴퓨터 시스템 상에서 근사 고급 언어로 작성된 소프트웨어로 구현될 수도 있지만, 앞에서 언급된 종류의 정보를 서치하고 검색하기 위한 프로세서 장치의 형태로 구현될 수도 있다는 사실도 이해되어야 한다.

위에 언급된 목적 및 잇점들은, 상기 데이터 구조는 상기 텍스트(T) 내의 워드 및/또는 심볼들(s) 및 그들의 시퀀스들(S)의 접미어들을 저장하기 위한 비균일한(non-evenly) 간격의 희소 접미어 트리 ST(T) 형태의 트리 구조를 포함하고, 상기 메트릭(M)은 텍스트(T) 및 쿼리(Q)내의 각 워드 및/또는 심볼들(s;q) 사이의 근사 매칭도에 대한 편집 거리 메트릭 D(s,q) 및 상기 텍스트(T) 내의 워드 및/또는 심볼들(s)의 시퀀스들(S)과 상기 쿼리(Q) 내의 워드 및/또는 심볼들(q)의 쿼리 시퀀스(P) 사이의 근사 매칭도에 대한 편집 거리 메트릭 D_WS(S,P)의 조합을 포함하고, 후자인 편집 거리 메트릭은 텍스트(T) 내의 워드 및/또는 심볼들(s)의 시퀀스(S)를 쿼리(Q)내의 워드 및/또는 심볼들(q)의 시퀀스(P)로 변환하는 편집 연산을 위한 가중 코스트 함수(weighting cost function)를 포함하고, 상기 가중치 부여는 변환에서의 시퀀스 길이(S)의 변화에 비례하거나 매칭될 시퀀스(S;P) 내의 워드 및/또는 심볼(s;q)의 크기에 종속인 값과 함께 발생하고, 상기 구현된 서치 알고리즘은 텍스트(T) 및 쿼리(Q) 각각의 접미어 트리 표현내의 워드 및/또는 심볼(s;q) 사이의 매칭도를 결정하기 위한 제1 알고리즘과 텍스트(T) 및 쿼리(Q) 각각의 접미어 트리 표현내의 워드 및/또는 심볼(s;q)의 시퀀스들(S;P) 사이의 매칭도를 결정하기 위한 제2 알고리즘을 포함하고, 상기 제1 및/또는 제2 알고리즘은 워드, 심볼, 워드의 시퀀스 또는 심볼의 시퀀스 또는 그들의 조합 중 한 형태의 쿼리(Q)에 의해 데이터 구조를 서치하여, 정보(R)가 전자 및 후자 사이에서 특정 매칭도를 갖는 쿼리(Q)를 기초로 검색토록 하며, 상기 서치 알고리즘은 또한 선택적으로 각각 텍스트(T) 및 쿼리(Q)의 접미어 트리 표현내의 워드 및/또는 심볼들(s;q) 사이의 완전 매칭을 결정하기 위한 제3 알고리즘 및/또는 각각 텍스트(T) 및 쿼리(Q)의 접미어 트리 표현내의 워드 및/또는 심볼(s;q)의 시퀀스들(S;P) 사이의 완전 매칭을 결정하기 위한 제4 알고리즘을 포함하고, 상기 제3 및/또는 제4 알고리즘은 워드, 심볼, 워드의 시퀀스 또는 심볼의 시퀀스 또는 그들의 조합 중 하나의 형태인 쿼리(Q)에 의해 데이터 구조를 서치하여, 정보(R)가 전자 및 후자 사이에서 완전 매칭을 갖는 쿼리(Q)를 기초로 검색되는 것을 특징으로 하는 서치 시스템을 갖는 발명에 따라 실현된다.

본 발명에 따른 서치 시스템의 유익한 실시예에서, 접미어 트리(suffix tree;ST(T))는 워드-간격의 희소 접미어 트리(word-spaced sparse suffix tree;SST_WS(T))이며, 텍스트(T)내 접미어들의 부분 집합만을 포함한다.바람직하게는, 상기 워드-간격의 희소 접미어 트리 SST_WS(T)는 키워드-간격의 희소 접미어 트리 SST_KWS(T)이다. 본 발명에 따른 서치 시스템의 더 유익한 실시예에서, 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서의 키워드 매칭도를 검출하기 위한 제1 알고리즘은 종속항인 제4항과 같이 구현되고, 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서의 시퀀스 매칭도를 결정하기 위한 제2 알고리즘은 종속항인 제5항과 같이 구현되며, 키워드-간격 희소 접미어 트리 SST_KWS(T)에서의 완전 키워드 매칭을 결정하기 위한 제3 알고리즘은 종속항인 제7항과 같이 구현되고, 마지막으로 키워드-간격 희소 접미어 트리 SST_KWS(T)에서의 완전 키워드 시퀀스 매칭을 결정하기 위한 제4 알고리즘은 종속항인 제8항과 같이 구현된다.

위에 언급된 목적 및 잇점들은 또한 정보 검색, 특히 텍스트(T)의 형태로 저장된 정보의 검색을 위한 서치(search) 시스템에서 정보를 검색하기 위한 방법으로서, 상기 텍스트(T)는 워드, 심볼(s) 및 그들의 시퀀스(S)를 포함하고, 상기 정보 검색은 워드 및/또는 심볼(q) 및 그들의 시퀀스들(P)을 포함하는 쿼리(Q)와 텍스트(T)로부터의 워드 및/또는 심볼 및 그들의 시퀀스들을 포함하는 검색된 정보(R) 사이의 고정되어 있거나 혹은 변화하는 매칭도에 따라 발생하고, 상기 서치 시스템은 상기 텍스트(T)의 적어도 일부분을 저장하기 위한 데이터 구조 및 쿼리(Q)와 검색된 정보(R) 사이의 매칭도를 측정하는 메트릭(M)을 포함하고, 상기 서치 시스템은 서치, 특히 키워드(kw)를 기초로한 전문 검색을 수행하기 위한 서치 알고리즘을 구현하고, 상기 텍스트(T)에서의 정보는 워드(s) 및 워드 시퀀스(S)들로 분할되고, 상기 워드는 워드 경계 텀(word boundary term)에 의해 분리된 전체 텍스트의 하위 스트링이며 또한 심볼의 시퀀스를 형성하고, 각 워드는 심볼의 시퀀스로서 구조화 되는 방법으로서, 상기 데이터 구조를 텍스트(T)의 워드 분리 심볼(word separator symbol)에서 시작하는 모든 접미어를 표현하기 위한 텍스트(T)의 워드-간격의 희소 접미어 트리 SST_WS(T)로서 발생시키는 단계; 상기 텍스트(T)내 워드(s)의 시퀀스 정보를 상기 워드-간격의 희소 접미어 트리 SST_WS(T)에 저장하는 단계;상기 텍스트(T)의 워드(s)와 상기 쿼리(Q)의 쿼리 워드(q)에 대한 편집 거리 메트릭 D(s,q) 및 상기 텍스트(T)내의 워드(s)의 시퀀스(S)와 상기 쿼리(Q)내의 워드(q)의 시퀀스(P)에 대한 워드 크기-종속 편집 거리 메트릭 D_WS(S,P)을 포함하는 결합된 편집 거리 메트릭(M)을 발생시키고, 상기 편집 거리 메트릭 D_WS(S,P)은 상기 시퀀스(S)를 시퀀스(P)로 변환하는 편집 연산에 대한 코스트의 최소합이며, 코스트의 최소합은 시퀀스(S)의 총 길이 변화에 비례하는 파라미터 또는 현재 워드 길이와 시퀀스(S;P)의 평균 길이와의 비율에 의해, 가중된 각각의 편집 연산에 대한 코스트 함수의 최소합인 단계; 및 검색된 정보(R)의 워드(s)와 쿼리(Q)의 워드(q) 사이의 편집 거리 D(s,q)를 계산하므로써 워드(s,q) 사이의 매칭도를 결정하거나, 상기 워드(s,q)가 서로 k개 이상의 에러를 갖는 경우에는 모든 매칭에 대한 편집 거리 D_WS(S_R,P_Q)를 계산하므로써 검색된 정보(R) 및 쿼리(Q) 각각의 워드 시퀀스들(S_R,P_Q) 사이의 매칭도를 결정하는 단계를 포함하는 것을 특징으로 하는 정보 검색 방법으로 실현된다.

본 발명에 따른 방법은 추가적으로, 시퀀스(S)를 또다른 시퀀스(P)로 바꾸는 편집 연산을, 시퀀스(S,P)의 심볼들 사이의 근접성에 대한 파라미터로 가중하는 단계를 포함하며, 해당 편집 연산의 코스트를 결정할 때 시퀀스(S,P)의 유사성을 고려한다.본 발명에 따른 방법의 유리한 실시예에 있어서, 매칭수는 상기 쿼리 워드 시퀀스(P_Q)의 제한된 워드에 대한 편집 거리 D_WS(S_R,P_Q)를 계산하므로써 제한된다.본 발명에 따른 방법의 또다른 유리한 실시예에서, 워드(s)와 워드(q) 사이의 편집 거리 D(s,q)는 순환적으로(recursively) 정의되고, 동적 프로그램 과정에 의해 계산되며, 시퀀스(S)와 시퀀스(P) 사이의 편집 거리 D_WS(S,P)는 이에 대응하여 순환적으로 정의되고, 동적 프로그래밍 과정에 의해 계산된다.

본 발명에 따라, 위에 언급된 목적 및 잇점들 또한 근사 서치 엔진에서 본 발명에 따른 서치 시스템을 사용하므로써 실현된다.

본 발명에 따른 서치 시스템 및 방법은 첨부된 도면을 참조하여 더 상세히 설명될 것이다.

본 발명에 따른 서치 시스템은 본질적으로 3개의 부분 즉, 데이터 구조, 근사 매칭의 메트릭 및 서치 알고리즘을 포함한다. 본질적으로 본 발명에 따른 서치 시스템과 같이, 전문 검색이 목적인 경우는, 복구될 전체 데이터 세트가 높은 쿼리 성능을 뒷받침하는 데이터 구조에 저장될 것이다.

본 발명의 기초를 이루는 기본 개념을 보다 상세하게 논의하고자 한다. 텍스트(T)의 형태로 저장된 정보는 워드 및 워드 시퀀스로 분할된다. 워드는 워드 경계 텀(word boundary term)에 의해 분리된 전문(full text)에 대한 하위 스트링(substring)이다. 워드 경계 텀의 집합은 BT_word로 표시된다. 워드 경계 텀의 통상적인 집합은 {'',':','＼t','＼n','＼0','.',';','?'}이고, 여기서 ＼t는 탭 문자를 나타내고, ＼n는 개행문자를 나타내며, ＼0는 문서끝(end-of-document) 표시기를 나타낸다. 다음의 본 발명에 대한 설명과 관련하여, 스트링 및 시퀀스에 대한 몇가지 정의가 필요할 것이다.

정의 1 : 스트링

스트링은 ASCII 문자와 같이 알파벳으로부터 선택된 심볼들의 시퀀스이다. 스트링의 길이는 스트링을 포함하는 심볼 또는 문자들의 수이며 |x|로 표시된다. x가 길이m을 갖는 경우에는, 스트링은 x₁x₂...x_i...x_m으로도 표현할 수 있으며, 여기서 x_i는 스트링에서 i번째 심볼을 표현한다.

x의 하위 스트링은 x내의 인접하는 심볼들의 그룹에 의해 주어지는 스트링이다. 하위 스트링은 스트링의 시작 또는 끝으로부터 하나 이상의 문자를 삭제하여 x로부터 얻을 수 있다.

정의 2 : 하위 스트링, 접미어 및 접두어

x의 하위 스트링은 스트링이고, 1≤i≤j≤n이다. 스트링 x_i=x_i ⁿ=x_i...x_n은 스트링 x의 접미어이고, 스트링 x_j=x₁ ^j=x₁x₂...x_j는 스트링 x의 접두어이다.

또한 워드 시퀀스의 표기도 사용될 것이다.

정의 3 : 워드 시퀀스

워드 시퀀스는 별개의 연속적인 워드의 시퀀스이다. 워드 시퀀스 S=s₁,s₂,...,s_n는 n개의 단일 워드(또는 스트링) s₁,s₂에서 s_n까지를 포함한다. 워드 시퀀스는 시퀀스 경계 텀에 의해 범위가 정해진다. 시퀀스 경계 텀의 집합은 BT_seq으로 표시된다. 시퀀스 경계 텀의 보통 집합은 {'＼0'}일수 있으며, ＼0은 문서끝 표시기를 나타낸다.

근사 워드 매칭의 개념은 다음과 같이 설명될 수 있다.

스트링 s=s₁s₂...s_n및 쿼리 텀 q=q₁q₂...q_m이 주어진 경우에, 그 다음 작업은 s에 있는 모든 q를 찾아내는 것이다. 근접 메트릭은 q 및 잠재적인 매칭 s_i...s_j사이의 에러를 계산하는 방법을 결정한다.

근사 워드 매칭을 위한 통상적인 메트릭은 레벤슈타인(Levenstein) 거리 또는 편집 거리이다(V.I.Levenstein, "삭제, 삽입 및 반전을 교정할 수 있는 이진 코드들", (러시안) Doklady Akademii nauk SSSR, Vol.163,No.4,pp.845-8(1965) 및 사이버네틱스(cybernetics)와 제어 이론, Vol.10,No.8,pp707-10,(1966) 참조). 이 메트릭은 한 스트링을 다른 것으로 변환하는데 필요한 편집 연산의 최소값으로 정의된다. 한 편집 연산은 임의의 재기록 규칙으로 주어진다. 예를 들어,

(a→ε), 삭제

(ε→a), 삽입

(a→b), 변경

p와 m을 크기가 각각 i와 j인 워드라 하자. 그러면 D(i,j)는 p의 i번째 접두어와 m의 j번째 접두어 사이의 편집 거리를 나타낸다. 상기 편집 거리는 각각 다음과 같이 정의된다.

여기서인 경우는이고, 그렇지 않으면 1이다.

워드 시퀀스의 워드 레벨 상의 근사 매칭을 정의하는 것 또한 가능하며, 이것은 다음과 같이 설명될 수 있다.주어진 텍스트(T)는 각 워드가 문자의 스트링인 n개의 워드 w₁,w₂...w_n로 구성된다. 시퀀스 패턴(P)은 시퀀스 p₁,p₂,...,p_m가 1≤i≤j≤n인 시퀀스 w_i,w_i+1,...w_j와 최대 k만큼 다른 경우에는, T에서 근사 어커런스(occurrence)를 갖는다. 다시, 근접성 메트릭은 두개의 시퀀스 사이의 에러수를 계산하는 방법을 결정한다.

서치 시스템에서 검색될 텍스트는 데이터 서치를 촉진시킬 수 있는 방식으로 색인이 매겨져야 한다. 결과적으로 상기 데이터 구조는 본 발명에 따른 서치 시스템의 커널(kernel) 데이터 구조이며, 소위 접미어 트리, 특히 희소 접미어 트리에 기초를 두고 있다. 이러한 두 종류의 구조가 다음에서 정의될 것이다. 접미어 트리 S(T)는 텍스트(T)에서 모든 가능한 접미어의 트리 표현이다. 접미어 트리 S(T)에서 모든 단일 노드들은 그 자식 노드와 연결되어 소형의 변형을 발생시킨다.

도 1은 텍스트(T)="structure"에 대한 접미어 트리를 도시한다.

보다 구체적으로는, 본 발명은 희소 접미어 트리에 기초한다. 이러한 것들은 J.Kaerkkaeinen E.Ukkonen에 의한 "희소 접미어 트리"(제2차 연례 국제 계산 및 조합론 협회(the Second Annual International Computing and Combinatorics Conference;COCOON '96) 회보, Springer Verlag, pp.219-230)에 소개되어 있으며, 이 내용은 다시 D.R. Morrison에 의해 출판된 "PATRICIA-문자숫자식으로 코드화된 정보를 검색하기 위한 실제적 알고리즘(Practical Algorithm To Retrieve Information Coded in Alphanumeric)"(ACM 저널,15,pp.514-534(1968))에 기초하고 있다. 희소 접미어 트리는 다음과 같이 정의된다.

정의 4 : 희소 접미어 트리

희소 접미어 트리(sparse suffix tree;SST(T)는 텍스트의 접미어 트리(suffix tree;ST(T))에 나타난 접미어들의 부분집합 만을 포함하는 접미어 트리이다.

본 발명에 따른 전체 워드를 찾기 위한 서치 시스템을 사용할 때, 비균일(non-evenly) 간격의 희소 접미어 트리는 워드 경계에서만 시작하는 접미어를 저장하므로써 발생된다. 워드-간격의 희소 접미어 트리의 개념은 다음과 같이 정의 된다.

정의 5 : 워드-간격의 희소 접미어 트리

텍스트(T)의 워드-간격의 희소 접미어 트리(word-spaced suffix tree;SST_WS(T))는 텍스트에서 워드 분리기 문자(word separator character)에서 시작하는 접미어들 만을 포함하는 희소 접미어 트리 SST(T)이다.

도 2는 2개의 워드-간격의 희소 접미어 트리의 예를 도시한다. 접미어 부분들은 보다 읽기 쉽도록 하기 위해 생략되었다. T="to be the best"로 만들기 위한 워드-간격의 희소 접미어 트리는 도 2의 좌측 구조이며, T="to make the only major modificaiton"로 만들기 위한 구조는 우측 구조이다.

본 발명의 서치 시스템에서, 상기 텍스트는 당연히 독립적으로 워드-간격의 희소 접미어 트리에 저장된 워드들로 나누어진다. 서치의 기본적인 서치 텀은 워드 그 자체이기 때문에, 각 접미어는 워드의 끝에서 종결되는 것이 유리하다. 이것은 희소 접미어 트리를 소위 PATRICIA 트라이(Morrison, 앞에 인용한 책)까지 축소시킨다. 상기 문헌에서 정의된 트라이는 뿌리를 제외하고는, 각 노드가 알파벳 심볼을 포함하고, 동일한 노드의 자식 노드들은 모두 다른 심볼을 갖는, 뿌리가 있는 나무이다. 트라이(trie)라는 단어는 검색(retrieval)이라는 단어로부터 파생된 것이고, 따라서 트라이는 데이터 검색에 적절한 트리 구조이다. PATRICIA 트라이는 키워드-간격의 희소 접미어 트리(keyword-spaced sparse suffix tree;KWS tree)로 정의되고 상기 나뭇잎 노드는 키워드 구획문자(delimiter)에 의해 제한된다. 키워드 집합{"avoid", "abuse","be","become","breathe","say"}에 대한 PATRICIA 트라이가 도 3에 도시되어 있다. 본 발명의 서치 시스템은 워드의 시퀀스 정보를 명시적으로 저장하기 때문에 본 발명의 서치 시스템에 사용되는 구조는 상기 PATRICIA 트라이와는 다르다. 접미어 길이를 축소하는 것은 나뭇잎 노드 표현의 변경을 필요로 한다. 오리지날 텍스트에 대한 포인터는 접미어 스트링 그 자체로 대체된다.도 2에 나타난 스트링들 중 하나에 대해서 이런 종류의 접미어 길이 축소가 도 4에 도시되어 있다. 다른 말로 하면, 도 4는 T="to make the only major modification"에 대한 워드-간격 희소 접미어 트리를 나타내고, 접미어들은 워드 경계에서 절단된다. 나뭇잎 노드는 워드가 나뭇잎 노드에 의해 표현되는 워드가 발생하는 모든 위치의 리스트를 포함할 것이다.

오리지날 텍스트에서 발견되는 정보의 묵시적 시퀀스를 사용하는 대신, 본 발명은 시퀀스 정보를 워드-간격의 희소 접미어 트리에 명시적으로 저장한다. 이것은 오리지날 텍스트의 연속된 워드들을 표현하는 나뭇잎 노드들 사이의 포인터들을 사용하여 행해진다. 적어도 특정 나뭇잎 노드에 의해 표현되는 워드의 모든 어커런스들이 사용가능하기 때문에, 포인터가 다음의 연속된 나뭇잎에 추가되어야 한다.

나뭇잎 노드는 그것이 표현하는 워드의 접미어 만을 포함하기 때문에, 어커런스 리스트가 시퀀스 포인터를 통과할때는, 각 연속된 워드들의 접미어들만 보여진다. 이것은 접미어 대신 전체 워드를 나뭇잎 노드에 저장하므로써 조절되고, 또한 본 발명의 데이터 구조는 이런 면에서 상기 PATRICIA 트라이와는 다르다. 다음 연속 워드 및 그 어커런스로의 포인터를 포함한 어커런스 리스트와 함께 명시적으로 저장된 워드 시퀀스 정보를 위한 데이터 구조가 도 5에 도시되어 있다.

본 발명에 따른 서치 시스템은 어커런스 리스트(Morrison, 앞에 인용한 책)를 구성하기 위해 PATRICIA 트라이를 사용한다. PATRICIA 트라이는 서치 시스템으로 하여금 시간 O(|p₂|)내에 스트링 p₂에 매칭되는 모든 연속된 워드의 리스트에 접근할 수 있도록 한다. 여기서 |p₂|는 물론 p₂의 길이이다. PATRICIA 트라이를 사용하여 어커런스의 리스트를 구성하므로써, 텍스트로부터의 워드를 저장하고 시퀀스 정보를 유지하기 위한 완전하게 정의된 트리 구조를 얻을 수 있다. 구성된 어커런스 리스트 및 여분의 정리되지 않은 어커런스 리스트에 대한 두 PATRICIA 트라이 모두를 갖는 통상적인 나뭇잎 노드가 도 6에 도시된다. 본 발명의 서치 시스템에 사용된 것과 같은 어커런스 리스트에 대한 메모리 필요조건의 예로서, 약 742358개의 문서를 갖는 데이터베이스는 총 333,856,744개의 워드 및 538,244개의 서로 다른 워드의 어휘를 갖는다. 데이터베이스의 총 크기는 2054.52 MB이다. 평균 워드 길이는 6.45바이트이다. 희소 접미어 트리는 32비트 포인터를 사용하는 각 내부 노드에 대해 8 바이트를 사용할 것이다. 평균 2개의 내부 노드들이 각 워드에 대해 사용된다. 전체 워드에다가 어커런스 리스트로의 포인터에 대한 32비트까지 저장하기 위해서는 6.45 바이트가 필요할 것이다. 총 34.45 바이트/워드는 총 18.108 MB의 크기를 제공할 것이다. 추가적으로 상기 어커런스 리스트는 엔트리당 4 바이트의 크기를 갖고, 풀 버전(full version)이 사용될 경우에는 12 바이트의 크기를 갖는다. 그러므로, 어커런스 리스트의 총 메모리 필요량은 1273MB 에서 3820MB 사이이다. 희소 접미어 트리를 사용하는 데이터 구조는 오리지날 텍스트의 60% 내지 200%의 크기를 가질 것이다. 이것은 반전된(inverted) 파일의 필요량에 필적할만 하지만, 본 발명에 따른 서치 시스템에 사용되는 것과 같은 희소 접미어 트리는 훨씬 빠른 서치를 제공하고 근사 매칭을 가능하게 하며 수행하기에 쉬운 시퀀스 매칭을 만들어 준다.근사 서치에서, 가능한 매칭의 에러를 측정하기 위해 메트릭이 사용된다. 본 발명에 따른 서치 시스템은 수개의 메트릭, 특히 메트릭의 유일한 조합을 채용한다. 조합된 메트릭과 함께 이러한 메트릭들이 아래에서 논의될 것이다.

위에 정의된 것과 같은 편집 거리 메트릭은 직관적으로 워드 및 문자에 적용되는 삭제, 삽입 및 변경과 같은 연산을 가능케한다. 구를 매칭시키는데 있어서의 통상적인 에러는 누락(missing), 추가(extra) 또는 변경된(changed) 워드이다. 따라서, 이전에 정의된 것과 같은 편집 거리 메트릭이 근사 워드 시퀀스 매칭 문제에 적용되기 위해 채용되고 확장될 것이다. 시퀀스들을 위한 편집 연산은 다음과 같이 정의된다.

정의 6 : 시퀀스들을 위한 편집 연산

한 시퀀스(S)의 워드들을 또다른 시퀀스(P)의 워드로 변환하기 위해, 시퀀스의 워드 상에 허가된 편집 연산들은 다음의 재기록 규칙에 따라 기록될 수 있다.

(a→ε), 시퀀스로부터 워드 a의 삭제(deletion)

(ε→a), 워드 a를 시퀀스에 삽입(insertion)

(a→b), 워드 a를 워드 b로 변경(change)

(ab→ba), 근접한 워드 a 및 b의 전치(transposition).

본 발명에 따른 서치 시스템은 원자로서의 문자대신에 편집 연산을 연산 원자로 간주되는 워드에 적용시킨다.

코스트 함수는 다음과 같이 정의되는 상수이다.

여기서,은 다음과 같이 정의된다.

위의 정의와 같은 편집 연산을 사용하므로써, 시퀀스에 대한 편집 거리가 정의될 수 있다.

정의 7 : 시퀀스들에 대한 편집 거리

시퀀스에 대한 편집 거리 메트릭은 시퀀스 (S=s₁,s₂,...,s_n)와 시퀀스 (P=p₁,p₂,...,p_m) 사이의 거리 (D_seq(S,P))를, 시퀀스 (S)를 시퀀스 (P)로 변환하는 편집 연산의 시퀀스에 대한 코스트 c(x→y)의 최소합으로 정의한다.

본 발명에 따른 서치 시스템은 시퀀스들에 대한 편집 거리 메트릭을 늘려서 편집 연산의 코스트를 연산되는 워드의 크기 만큼 가중시킨다.

정의 8 : 시퀀스들에 대한 워드 크기-종속 편집 거리

시퀀스들에 대한 워드 크기-종속 편집 거리는 한 시퀀스를 다른 시퀀스로 변환하는데 필요한 편집 연산에 대한 코스트의 최소합으로 정의된다. 연산함수는 그 피연산자의 워드 크기에 따라 변한다.

본 발명에 따른 서치 시스템에서 코스트 함수의 정의는 다음 방정식으로 주어진다.

여기서 l은 비교되는 두 시퀀스내 워드의 평균 길이를 표시한다. 각 편집 연산의 코스트는 시퀀스의 총 길이의 변화에 비례하는 크기만큼 또는 고려되는 시퀀스내 현재 워드 길이 및 평균 워드 길이의 비율만큼 가중된다.

거리 메트릭은 워드 길이와 워드가 상기 워드 시퀀스의 의미 문맥에 대해 얼마나 중요성을 갖는가 사이의 관계에 대한 가정을 반영한다. 게다가 본 발명에 따른 서치 시스템은 변경 편집 연산(a→b)이 사용될 때의 문자 레벨의 근접성을 채용한다. 워드 a를 또다른 워드 b로 대체하는 것은 이러한 두 워드 사이의 유사성에 관련되어져야 한다. 변경 편집 연산에 대한 새로운 코스트 함수는 다음과 같이 주어진다.

여기서,

D(a,b)는 워드들에 대한 함수를 측정하는 표준화된 편집 거리이고, 0은 완전 유사성을 의미하고, 1은 무유사성을 의미한다.

본 발명에 따른 서치 시스템은 시퀀스들에 대한 편집 거리 메트릭을 수학식 4,5 및 6으로 주어진 코스트 함수 및 수학식 1로 주어진 워드들에 대한 편집 거리 메트릭과 결합한다. 이것은 시퀀스 편집 연산들이 워드들이 서로 k개 이상의 에러와 매칭될 때에만 사용된다는 것을 의미한다.

본 발명에 따른 서치 시스템에서 사용되는 알고리즘은 설명된 구조에 대한 효율적인 서치를 수행한다. 매칭은 위에 주어진 메트릭에 의해 확인된다.

워드-간격의 희소 접미어 트리에서의 근사 워드 매칭은 편집 거리 행렬의 계산과 접미어 트리의 횡단(traversal)을 결합하므로써 행해진다. 이것의 알고리즘은 의사 코드(pseudo-code)로 씌여지며, 표 1에 주어져 있다.

이 알고리즘은 Shang T.H.Merrettal의 "근사 스트링 매칭을 위한 트라이(Tries for Approximate String Matching)"(지식 및 데이터 엔지니어링에 대한 IEEE 회보, Vol.5, No.4,pp.540-547(1996).)에 제안된 것과 같은 트라이-매칭 알고리즘에서 발췌된 것이다. 예상되는 최악의 경우 상기 알고리즘의 러닝 타임은 Shang Merrettal(앞에 인용한 책)에 따른이다.

근사 워드 시퀀스 매칭은 모든 가능한 매칭에 대한 워드 시퀀스 편집 거리의 계산을 필요로 한다. 그러나, 가능한 매칭의 수는 매칭이 가능한 워드들에 대해서만 편집거리 계산을 시작하므로써 제한될 수 있다. 시퀀스들로부터 워드를 삭제하는데 드는 코스트가 가능한 시작 워드들의 수를 결정한다. 쿼리 시퀀스(P_Q)의 처음 i개의 워드를 삭제하는데 드는 누적된 코스트가 주어진 에러 임계값을 넘는 경우에, 상기 쿼리의 i번째 워드로 시작하는 후보 시퀀스는 매칭이 될 수 없다. 그러므로, i개의 워드들의 쿼리 시퀀스(P_Q)에 대해서, 고작해야 i개의 가능한 시작 워드들이 시도될 것이다. 상기 트리의 시퀀스 구조에는 후방 포인터(backpointer)가 없기 때문에, 모든 가능한 매칭을 얻을 수 있다는 보장은 없다. 후방 포인터를 추가한다면 이 문제를 해결할 수 있을 것이다. 본 발명에 따른 서치 시스템에서 사용된 것과 같은 근사 워드 시퀀스에 대한 알고리즘은 아래의 표 2에서 의사 코드로 주어진다. 이 알고리즘은 첫번째 키워드를 p₁,p₂,..와 차례로 매칭시키고, 모든 가능한 위치를 시험한다.

표 2의 ApproxSequenceMatch 알고리즘에서 ApproxMatchRest함수는 아래의 표 3의 알고리즘으로 정의된다. 이 함수가 초기 에러값을 사용하여 나머지 시퀀스를 매칭시키게 된다.

표 2 및 3의 알고리즘들은 표 1의 알고리즘과 동일한 의사 코드로 기록되어 있다.

시퀀스의 첫번째 워드와 매칭되는 나뭇잎 노드를 찾는데 사용되는 FindExact 함수는 트리의 단순 횡단을 수행하고 그 러닝 타임은이며,은 쿼리 시퀀스(P_Q)의 첫번째 워드를 나타낸다. 편집 거리의 계산은 계산 알고리즘의 향상된 버전을 사용하여 직접적인 동적 프로그래밍을 사용하는시간 또는 상기 계산 알고리즘의 향상된 버전을 사용하는시간(k는 에러 임계값을 나타냄)에 행해질 수 있다(E.U. Ukkonen의 "스트링에서의 근사 패턴 발견"(Journal of Algorithms, vol.6,pp.132-137(1985)) 참조).

가 워드 시퀀스에서의 각 워드의 어커런스 수의 총합을 나타낸다면, 최악의 경우 러닝 타임은이다.

본 발명에 따른 서치 시스템을 기초로 한 서치 엔진의 구현을 간략하게 논의하고자 한다. 특정하여 말하면, 본 발명에 따른 서치 시스템을 기초로 한 서치 엔진은 근사 서치 엔진(approximate search engine;ASE)으로 구현되며, 많은 문서 집합에 색인을 달고 이러한 문서 집합의 완전 또는 근사 서치를 위한 알고리즘을 제공하기 위한 서치 엔진으로 만들도록 의도된다. ASE는 대량의 텍스트 또는 문서 집합을 저장하기 위한 데이터 구조를 제공할 것이다. 데이터 구조는 이미지, 영상 및 음성과 같은 추가적인 정보를 포함하는 문서로부터 발생될 수 있으며, 상기 텍스트는 형식화 되거나 및/또는 주석이 더해질 수 있다. 상기 데이터 구조는 위에 논의된 워드-간격의 희소 접미어와 동일함은 물론 상기 워드는 서치 시스템의 키워드여야 한다는 사실이 이해되어야 한다. 따라서, 상기 워드-간격의 희소 접미어 트리가 대신 키워드-간격의 희소 접미어 트리(keyword-spaced sparse suffix tree;KWS tree)로 명명된다. 상기 ASE는 상기 KWS 트리의 문서들에 색인을 달기 위한 알고리즘을 포함할 것이다. 이러한 알고리즘은 물론 본 발명에 따른 서치 시스템의 부분을 형성하지는 않지만, 당업자에게 잘 알려져 있고 문학에 설명되어 있다(예컨대, J.Kaekkaeinen E. Ukkonen(앞에 인용한 책) 및 D.R. Morrisson(앞에 인용한 책) 참조).

본 발명에 따른 서치 시스템은 ASE에 사용된 것과 같이 KWS 트리에서 패턴의 완전 및 근사 매칭 모두에 대한 알고리즘을 채용한다. 위 표 1 및 표 2에 주어진 알고리즘은 메트릭으로서의 비균일 편집 거리와 매칭을 이루는 근사 워드 및 워드 시퀀스에 대해 사용된다. KWS 트리에서 길이가 m인 키워드(p)의 완전 매칭을 찾아내는 것은 해당 분야에 알려져 있으며, 트리 구조의 단순한 횡단으로 쉽게 구현될 수 있다. 의사 코드로 기록된 완전 키워드 매칭을 위한 적절한 알고리즘이 표 4에 주어져 있다. 본 발명에 따른 서치 시스템은 또한 완전 키워드 시퀀스 매칭을 위한 알고리즘을 뒷받침할 수 있을 것이다. 완전 키워드 매칭을 위한 알고리즘들은 해당 분야에 알려져 있으며, 예컨대 아래 표 5의 의사 코드에 보여진 대로 쉽게 구현될 수 있다. 여기에 주어진 알고리즘은 처음 키워드의 정확한 매칭(있다면)을 발견할 것이다. 그리고는 첫번째 키워드의 모든 어커런스에 대해서 두번째 키워드가 쿼리의 두번째 키워드와 매칭되는지를 체크할 것이다. 매칭되는 경우에는, 표 5의 MatchRest 과정이 처음 두개의 키워드의 어커런스가 전체 시퀀스와 매칭되는지를 판단하는데 사용된다. KWS 트리에서의 근사 키워드 매칭을 위해, 서치 시스템은 위 표 1의 알고리즘을 구현하여, 첫번째 키워드를 차례로 p₁,p₂,..와 매칭시키고, 모든 가능한 시작 위치를 시험하며, 표 3에 주어진 ApproxMatch 함수를 적용하여 특정 위치에서 시작하는 시퀀스와 매칭시키고 초기 에러값을 조절한다.

상기 ASE는 사용자에게 색인을 매기고 상기 문서 집합에의 쿼리를 하게 해주는 단순 전단부(simple front end)를 필요로 할 것이다. 상기 전단부는 또한 문서 집합의 통계를 제공하고, 예컨대 WWW을 통한 원거리 액세스(access)를 위한 네트워크 인터페이스 및 지역 서버 사용자 인터페이스 모두를 제공한다.

본 발명에 따른 서치 시스템을 갖는 ASE는 새 색인 및 서치 알고리즘을 쉽게 추가할 수 있도록 해주는 방식에 있어서 일반적이어야 한다. 또한, 각 문서 또는 키워드에 대한 여분의 정보를 저장하는 것은 간단한 방법으로 구현할 수 있어야 한다. 특히, 상기 전단부는 데이터 구조 및 서치 알고리즘에 독립적이며, 이것들 내부의 변화는 데이터 구조의 설계에 영향이 없다.

본 발명의 ASE에 따른 서치 시스템의 사용은 데이터 구조에서 가능한 한 적게 메모리를 소비하도록 설계되어야 한다. 또한 서치는 가능한 한 빠른 속도가 되도록 설계되어야 한다. 그러나, 보통은 이 두개의 요인 사이에 트레이드-오프(trade-off)가 있게 마련이다.

요약하면, 본 발명에 따른 서치 시스템을 갖는 ASE는 4개의 주모듈을 포함한다.

1. KWS 트리 구조에서 문서들에 색인을 달기 위한 문서 색인 모듈(DocumentIndexing Module ; DIM). 이 모듈은 또한 수개의 문서 타입을 뒷받침하기 위한 모든 확장도 포함하여야 한다.

2. 키워드-간격의 희소 접미어 트리(KWS 트리)를 기초로 한 데이터 저장 모듈(Data Storage Module ; DSM)

3. 상기 KWS 트리를 서치하기 위한 서치 알고리즘 모듈(Search Algorithm Module ; SAM), 이 모듈은 각각의 워드 및 워드 시퀀스에 대한 완전 및/또는 근사 매칭을 위한 알고리즘을 포함한다.

4. 사용자 인터페이스 전단부 모듈(User Interface Front-End Module ; FEM)은 지역 서버 사용자 인터페이스 및 원거리 쿼리를 위한 네트워크 인터페이스를 포함한다.

상기 ASE의 4개 모듈은 함께 작용하여 완전한 서치 엔진 기능을 제공한다. 서로 다른 모듈들 사이의 데이터 흐름이 도 7에 도시되어 있다. 문서의 집합에 색인을 다는 것은 색인 알고리즘을 포함하는 문서 색인 모듈(DIM)에서 행해진다. 이 모듈은 물론 본 발명에 따른 서치 시스템의 부분은 아니지만, 사용될 수 있는 색인 알고리즘은 해당 분야에 잘 알려져 있다. 문서에서 발견되는 텍스트는 저장을 위한 데이터 저장 모듈(DSM)로 넘겨진다. 상기 데이터 저장 모듈은 물론 본 발명에 따른 서치 시스템의 일부이며, 상기 KWS 트리 구조를 기초로 언급된다. 서치 알고리즘 모듈(SAM)은 상기 데이터 저장 모듈에 위치한 데이터를 서치하기 위한 알고리즘을 포함한다. 이 모듈은 본 발명에 따른 서치 시스템을 구현하고 트리 및 노드 정보를 위한 데이터 구조에 쿼리하는 서치 프로세스를 가능케 하고, 상태 변수들을 유지한다. 상기 전단부 모듈은 예컨대 워크 스테이션(work station) 또는 퍼스널 컴퓨터 등등에 구현될 수 있고, 위에 언급된 기능을 제공한다.

서론에서 이미 언급된 바와 같이, 본 발명에 따른 서치 시스템은 워크 스테이션을 포함하는 상용화된 컴퓨터 시스템 상에, 적절한 하이-레벨(high-level) 언어로 작성된 소프트웨어로 구현될 수 있다. 언급된 바와 같이 본 발명에 따른 서치 시스템은 다수의 병렬 프로세서들을 포함하여 다수의 쿼리 워드 시퀀스들과의 근사 매칭을 위해 많은 워드 시퀀스들을 병렬적으로 처리할 수 있는 전용 프로세서 장치의 형태로 구현될 수도 있다. 상기 프로세서의 고정된 연산 파라미터들은 로우-레벨(low-level) 코드로 입력될 수 있는 반면에, 상기 KWS 트리 구조로부터의 키워드 시퀀스 입력은 대량의 데이터에 대한 쿼리들을 극도로 빨리 프로세싱 할 수 있도록 하고, 본 발명에 따른 서치 시스템은 예컨대 월드 와이드 웹 상에서 고도로 서치를 수행하기에 적합해질 것이며, 심지어는 현재 월드 와이드 웹 상에 제공되어 있는 모든 문서들에 색인을 달기에 충분히 큰 KWS 트리 구조에서 서치를 수행하는 것은 물론, 앞으로의 월드 와이드 웹의 성장량도 다룰 수 있게 될 것이다.

Claims

텍스트(T)의 형태로 저장된 정보를 포함하는 정보 검색(retrieve)을 위한 서치(search) 시스템으로서,

상기 텍스트(T)는 워드 및/또는 심볼(s) 및 그들의 시퀀스(S)를 포함하고,

상기 정보 검색은 워드 및/또는 심볼(q) 및 그들의 시퀀스들(P)을 포함하는 쿼리(Q;query)와 상기 텍스트(T)로부터의 워드 및/또는 심볼 및 그들의 시퀀스들을 포함하는 검색된 정보(R) 사이의 고정되어 있거나 혹은 변화하는 매칭도에 따라 발생하고,

상기 서치 시스템은 상기 텍스트(T)의 적어도 일부분을 저장하기 위한 데이터 구조 및 쿼리(Q)와 검색된 정보(R) 사이의 매칭도를 측정하는 메트릭(metric;M)을 포함하고, 상기 서치 시스템은 서치, 특히 키워드(kw)를 기초로 전문 서치를 수행하기 위한 서치 알고리즘을 구현하는 서치 시스템으로서,

상기 데이터 구조는 상기 텍스트(T) 내의 워드 및/또는 심볼들(s) 및 그들의 시퀀스들(S)의 접미어들을 저장하기 위한 비균일한(non-evenly) 간격의 희소(sparse) 접미어 트리 ST(T) 형태의 트리 구조를 포함하고,

상기 메트릭(M)은 텍스트(T)내의 각각의 워드 및/또는 심볼들(s;q)과 쿼리(Q) 사이의 근사 매칭도에 대한 편집 거리 메트릭 D(s,q) 및 상기 텍스트(T) 내의 워드 및/또는 심볼들(q)의 시퀀스들(S)과 상기 쿼리(Q) 내의 워드 및/또는 심볼들의 쿼리 시퀀스(P) 사이의 근사 매칭도에 대한 편집 거리 메트릭 D_WS(S,P)의 조합을 포함하고, 후자인 상기 편집 거리 메트릭은 텍스트(T) 내의 워드 및/또는 심볼들(s)의 시퀀스(S)를 쿼리(Q)내의 워드 및/또는 심볼들(q)의 시퀀스(P)로 변환하는 편집 연산을 위한 가중 코스트 함수(weighting cost function)를 포함하고, 상기 가중치 부여는 변환에서의 시퀀스 길이(S)의 변화에 비례하거나 매칭될 시퀀스(S;P) 내의 워드 및/또는 심볼(s;q)의 크기에 종속인 값과 함께 발생하고,

상기 구현된 서치 알고리즘은 텍스트(T) 및 쿼리(Q) 각각의 접미어 트리 표현내의 워드 및/또는 심볼(s;q) 사이의 매칭도를 결정하기 위한 제1 알고리즘과 텍스트(T) 및 쿼리(Q) 각각의 접미어 트리 표현내의 워드 및/또는 심볼(s;q)의 시퀀스들(S;P) 사이의 매칭도를 결정하기 위한 제2 알고리즘을 포함하고, 상기 제1 및/또는 제2 알고리즘은 워드, 심볼, 워드의 시퀀스 또는 심볼의 시퀀스 또는 그들의 조합 중 한 형태의 쿼리(Q)에 의해 데이터 구조를 서치하여, 정보(R)가 전자 및 후자 사이에서 특정 매칭도를 갖는 쿼리(Q)를 기초로 검색토록 하며,

상기 서치 알고리즘은 또한 선택적으로 각각 텍스트(T) 및 쿼리(Q)의 접미어 트리 표현내의 워드 및/또는 심볼들(s;q) 사이의 완전 매칭을 결정하기 위한 제3 알고리즘 및/또는 각각 텍스트(T) 및 쿼리(Q)의 접미어 트리 표현내의 워드 및/또는 심볼(s;q)의 시퀀스들(S;P) 사이의 완전 매칭을 결정하기 위한 제4 알고리즘을 포함하고, 상기 제3 및/또는 제4 알고리즘은 워드, 심볼, 워드의 시퀀스 또는 심볼의 시퀀스 또는 그들의 조합 중 하나의 형태인 쿼리(Q)에 의해 데이터 구조를 서치하여, 정보(R)가 상기 쿼리(Q) 및 상기 정보(R) 사이에서 완전 매칭을 갖는 쿼리(Q)를 기초로 검색되는 것을 특징으로 하는 서치 시스템.
제1항에 있어서, 상기 비균일한 간격의 희소 접미어 트리 ST(T)는 텍스트(T)내에 오직 접미어 부분 집합만을 포함하는 워드-간격의 희소 접미어 트리 SST_WS(T)인 것을 특징으로 하는 서치 시스템.
제2항에 있어서, 상기 워드-간격의 희소 접미어 트리 SST_WS(T)는 키워드-간격의 희소 접미어 트리 SST_KWS(T)인 것을 특징으로 하는 서치 시스템.
제3항에 있어서, 상기 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서의 키워드 매칭도를 검출하기 위한 제1 알고리즘은 다음과 같은 의사-코드(pseudo-code)로 구현되는 것을 특징으로 하는 서치 시스템.
제3항에 있어서, 상기 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서의 키워드 시퀀스 매칭도를 결정하기 위한 제2 알고리즘은 다음과 같은 의사-코드로 구현되는 것을 특징으로 하는 서치 시스템.
제5항에 있어서, 상기 제2 알고리즘의 상기 ApproxMatchRest 서브 루틴은 다음과 같은 의사 코드로 구현되는 것을 특징으로 하는 서치 시스템.
제3항에 있어서, 상기 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서 완전 키워드 매칭을 결정하기 위한 제3 알고리즘은 다음과 같은 의사-코드로 구현되는 것을 특징으로 하는 서치 시스템.
제3항에 있어서, 상기 키워드-간격의 희소 접미어 트리 SST_KWS(T)에서의 완전 키워드 시퀀스 매칭을 결정하기 위한 제4 알고리즘은 다음과 같은 의사-코드로 구현되는 것을 특징으로 하는 서치 시스템.
텍스트(T)의 형태로 저장된 정보를 포함하는 정보를 검색하기 위한 서치(search) 시스템에서 정보를 검색하기 위한 방법으로서,

상기 텍스트(T)는 워드, 심볼(s) 및 그들의 시퀀스(S)를 포함하고,

상기 정보 검색은 워드 및/또는 심볼(q) 및 그들의 시퀀스들(P)을 포함하는 쿼리(Q)와 텍스트(T)로부터의 워드 및/또는 심볼 및 그들의 시퀀스들을 포함하는 검색된 정보(R) 사이의 고정되어 있거나 혹은 변화하는 매칭도에 따라 발생하고,

상기 서치 시스템은 상기 텍스트(T)의 적어도 일부분을 저장하기 위한 데이터 구조 및 쿼리(Q)와 검색된 정보(R) 사이의 매칭도를 측정하는 메트릭(M)을 포함하고,

상기 서치 시스템은 서치, 특히 키워드(kw)를 기초로한 전문 검색을 수행하기 위한 서치 알고리즘을 구현하고,

상기 텍스트(T)에서의 정보는 워드(s) 및 워드 시퀀스(S)들로 분할되고, 상기 워드는 워드 경계 텀(word boundary term)에 의해 분리된 전체 텍스트의 하위 스트링이며 또한 심볼의 시퀀스를 형성하고,

각 워드는 심볼의 시퀀스로서 구조화 되는 방법으로서,

상기 데이터 구조를 텍스트(T)의 워드 분리 심볼(word separator symbol)에서 시작하는 모든 접미어를 표현하기 위한 텍스트(T)의 워드-간격의 희소 접미어 트리 SST_WS(T)로서 발생시키는 단계;

상기 텍스트(T)내 워드(s)의 시퀀스 정보를 상기 워드-간격의 희소 접미어 트리 SST_WS(T)에 저장하는 단계;

상기 텍스트(T)의 워드(s)와 상기 쿼리(Q)의 쿼리 워드(q)에 대한 편집 거리 메트릭 D(s,q) 및 상기 텍스트(T)내의 워드(s)의 시퀀스(S)와 상기 쿼리(Q)내의 워드(q)의 시퀀스(P)에 대한 워드 크기-종속 편집 거리 메트릭 D_WS(S,P)을 포함하는 결합된 편집 거리 메트릭(M)을 발생시키고,

상기 편집 거리 메트릭 D_WS(S,P)은 상기 시퀀스(S)를 시퀀스(P)로 변환하는 편집 연산에 대한 코스트의 최소합이며,

코스트의 최소합은 시퀀스(S)의 총 길이 변화에 비례하는 파라미터 또는 현재 워드 길이와 시퀀스(S;P)의 평균 길이와의 비율에 의해, 가중된 각각의 편집 연산에 대한 코스트 함수의 최소합인 단계; 및

검색된 정보(R)의 워드(s)와 쿼리(Q)의 워드(q) 사이의 편집 거리 D(s,q)를 계산하므로써 워드(s,q) 사이의 매칭도를 결정하거나,

상기 워드(s,q)가 서로 k개 이상의 에러를 갖는 경우에는 모든 매칭에 대한 편집 거리 D_WS(S_R,P_Q)를 계산하므로써 검색된 정보(R) 및 쿼리(Q) 각각의 워드 시퀀스들(S_R,P_Q) 사이의 매칭도를 결정하는 단계를 포함하는 것을 특징으로 하는 정보 검색 방법.
제9항에 있어서, 워드(s;q) 사이의 근접성(proximity)에 대한 파라미터로 워드(s)를 워드(q)로 변경시키는 편집 연산에 가중치를 주므로써, 당해 편집 연산의 코스트을 결정할때 워드(s;q)의 유사성을 고려하는 것을 특징으로 하는 정보 검색 방법.
제9항에 있어서, 쿼리 워드 시퀀스(P_Q)내의 제한된 워드수에 대한 편집 거리 D_WS(S_R,P_Q)를 계산하므로써 매칭수를 제한하는 것을 특징으로 하는 정보 검색 방법.
제9항에 있어서, 워드들(s)과 워드(q) 사이의 상기 편집 거리 D(s,q)를 순환적으로(recursively) 정의하고, 동적 프로그래밍 과정에 의해 상기 편집 거리 D(s,q)를 계산하는 것을 특징으로 하는 정보 검색 방법.
제9항에 있어서, 시퀀스(S) 및 시퀀스(P) 사이의 편집거리 D_WS(S,P)를 순환적으로 정의하고 동적 프로그래밍 과정에 의해 상기 편집 거리 D_WS(S,P)를 계산하는 것을 특징으로 하는 정보 검색 방법.
제1항에 있어서, 상기 서치 시스템은 근사(approximate) 서치 엔진에서 사용되는 것을 특징으로 하는 서치 시스템.