KR100973019B1

KR100973019B1 - 인버티드 인덱스를 위한 색인데이터 생성방법

Info

Publication number: KR100973019B1
Application number: KR1020080029775A
Authority: KR
Inventors: 심춘택
Original assignee: 이너비트 주식회사
Priority date: 2008-03-31
Filing date: 2008-03-31
Publication date: 2010-07-30
Also published as: KR20090104376A

Abstract

본 발명은 인버티드 인덱스를 위한 색인데이터 생성방법에 관한 것으로서, 특히 원문파일 또는 데이타베이스에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

특정 레코드에 저장된 문자열(S)의 길이를 M이라 하고, 전체 문자열(S)이 C₀,C₁,C₂~C_M-1로 구성되어 있을때,

이에대한 색인어로서 'C₀,C₁,C₂~C_M-1', 'C₁,C₂~C_M-1','C₂~C_M-1',…'C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 색인데이터 생성방법을 제공한다.

본 발명은 기존의 N-gram 방식에서 지원하는 기능과 완전한 키워드 일치 및 절단어 형태의 검색을 모두 만족하도록 지원하고, 휴대폰과 같은 소형무선 단말기에서 데이타 저장공간의 효율성을 재고하면서 데이타 검색시 프로세서의 연산횟수를 줄여주어 시스템 성능 향상에 기여할 수 있도록 한 인버티드 인덱스를 위한 개선된 색인데이터 생성방법에 관한 것이다.

휴대폰, 인버티드 인덱스, 색인데이터, N-gram,

Description

인버티드 인덱스를 위한 색인데이터 생성방법{Inverted Index data generation method}

본 발명은 인버티드 인덱스(Inverted Index)를 위한 색인데이터 생성방법에 관한 것으로서, 더욱 상세하게는 기존의 N-gram 방식에서 지원하는 기능에, 완전한 키워드 일치 및 절단어 형태의 검색 지원하고, 휴대폰과 같은 소형무선 단말기에서 데이타 저장공간의 효율성을 재고하면서 데이타 검색시 프로세서의 연산횟수를 줄여주어 시스템 성능 향상에 기여할 수 있도록 한 개선된 인버티드 인덱스를 위한 색인데이터 생성방법에 관한 것이다.

현재 제공되고 있는 휴대폰, PDA와 같은 소형 무선단말기에서 단말기에 저장된 특정 정보를 검색하고자 할 때 검색할 단어를 추출해서 색인 정보를 만들경우에는 N-gram방식에 의해 색인데이터를 생성하고, 그 생성된 색인데이터를 이용하여 사용자가 입력한 키워드에 해당하는 정보를 검색하도록 하고 있다.

기존의 색인데이터 생성방법으로 사용되는 N-gram 방식의 색인데이터 생성방법을 도 1을 참조하여 설명하면 다음과 같다.

N-gram은 주어진 문자열로부터 N의 길이를 갖는 부분 문자열을 추출하는 방식이며, N-gram의 대표적인 구현은 2-gram(bi-gram)으로 이루어진다.

도 1과 같이 메모리에 저장되어 있는 원문파일에 R₁,R₂,R₃,...로 표현되는 레코드가 저장되어 있고, 각각의 레코드에는 문자열(String-S)의 길이가 M(M은 서로 다를수 있음)인 문자열(문자열 S 는 'C₀,C₁,C₂~C_M-1'로 표현)이 존재할 경우, 프로세서에 의해서 2-gram(bi-gram) 방식으로 추출되는 단어는 W_i=C_iC_i+1 이다.

예를들어 보면, 문자열 'abcde'가 주어진 경우 bi-gram으로 부분문자열을 생성하면, ab,bc,cd,de로 길이가 2인 부분 문자열(색인어)들이 생성된다.

그리고, 2-gram 방식으로 추출된 색인어를 이용한 인버티드 인덱스(Inverted index)를 구성하는 최소 정보의 관계는 키워드에 대한 레코드정보와 레코드내에서의 위치정보로 이루어진다.

도 1을 이용하여 원문파일로 부터 추출되는 2-gram 키워드를 이용하여 인버티드 인덱스를 구성하는 것을 설명한다.

도 1에는 원문파일과 이 원문파일로부터 2-gram에 의해 추출된 색인어를 이용하여 구성한 인버티드 인덱스가 예시되어 있으며,

상기 원문파일에는 서로다른 문자열을 갖는 R₁~R₅의 데이터, 즉, R₁-ABCD, R₂-ABABD, R₃-BCD, R₄-ABBD, R₅-BCACDA가 기록되어 있고, 이들로부터 추출된 색인어 "AB,AC,BA,BB,BC,BD,CA,CD,DA"와 이와 관계된 레코드(Record) 및 옵셋(Offset)정보 로서 인버티드 인덱스가 구성되어 있다.

상기 인버티드 인덱스에서 옵셋정보는 해당색인어가 레코드의 문자열에 포함되어 있는 위치를 나타낸다.

즉, 문자열 'ABCD'에서 추출된 색인어 'CD'에 관한 레코드는 R₁ 또는 R₅로 표기되고, 이에대한 옵셋정보는 'R₁'일 경우 (2), 'R₅'일 경우 (3) 으로 표기되는 것이다.

그러나, 상기와같은 N-gram 방식은 다음과 같은 문제점을 갖고 있다.

원문파일로부터 많은 수의 키워드(색인어)가 발생하며, 키워드에 대한 레코드 및 옵셋정보 등의 부가정보가 기재되어야만 하므로 키워드 검색시 옵셋에 대한 프로세서의 연산횟수가 증가하게되어 시스템의 성능을 하락시키는 문제점이 있었다.

또한, 원문파일의 레코드가 많아질수록 새로 추가되는 키워드의 수는 특정값에 수렴하는 형태가 되는데 반해 이에 대한 부가정보(옵셋정보)가 계속해서 늘어나게되고, 검색을 시도할 때 키워드의 길이가 길어지면 부가정보에 대한 access 및 부가적인 연산작업이 많아져서 검색효율이 떨어지는 문제점이 있었다.

그리고, 색인어가 N개의 문자열로 이루어지도록 생성되기 때문에 색인어보다 짧은 길이를 갖는 검색 키워드에 대해서는 처리하기 어렵고, 또 색인어보다 긴 길이를 갖는 검색키워드에 대해서는 처리가 매우 복잡해지는 문제점이 있었다.

예를들어, 2-gram 색인에서 검색키워드가 'BCD'로 입력되면 프로세서가 입력된 검색어를 'BC'와 'CD'로 변경한 후 각각의 경우에 대해서 색인어를 검색해야만 하므로 검색이 어려워지는 문제점이 발생하는 것이다.

따라서, 상기 문제점을 해결하기 위한 본 발명은 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

이에대한 색인어로서 'C₀,C₁,C₂~C_M-1', 'C₁,C₂~C_M-1','C₂~C_M-1',…'C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 색인데이터 생성방법을 제공하여 기존의 N-gram 방식에서 지원하는 기능과 완전한 키워드 일치 및 절단어 형태의 검색을 모두 만족하도록 지원하고, 휴대폰과 같은 소형무선 단말기에서 데이타 저장공간의 효율성을 재고하면서 데이타 검색시 프로세서의 연산횟수를 줄여주어 시스템 성능 향상에 기여할 수 있도록 한 인버티드 인덱스를 위한 개선된 색인데이터 생성방법을 제공함을 목적으로 한다.

상기 목적달성을 위한 본 발명은,

원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

이에대한 색인어로서 'C₀,C₁,C₂~C_M-1', 'C₁,C₂~C_M-1','C₂~C_M-1',…'C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 한다.

본 발명에 의하면, 원문파일에 존재하는 문자열로부터 생성되는 색인어 데이터에서 옵셋(OFFSET)정보가 제거되므로 검색시 옵셋에 대한 연산이 불필요하게되어 시스템 성능을 향상시킬 수 있고, 기존의 N-gram 방식에서 지원하는 기능과 완전한 키워드 일치 및 절단어 형태의 검색을 모두 만족하도록 지원하고, 휴대폰과 같은 소형무선 단말기에서 데이타 저장공간의 효율성을 재고할 수 있도록 한 인버티드 인덱스를 위한 개선된 색인데이터 생성방법을 제공하는 효과를 기대할 수 있다.

이하, 첨부된 도면 도 2 내지 도 5 를 참조하여 본 발명의 바람직한 실시예를 설명하면 다음과 같다.

본 발명의 색인데이터 생성방법은 크게 N-gram, Revers N-gram, Simplex, Duplex로 구분되어 지므로 각각의 경우를 예로 설명하기로 하며, 본 발명의 설명에 있어서 종래와 동일한 구성요소에 대해서는 동일한 부호로 표기하여 중복설명을 피하기로 한다.

◈ N-gram ◈

본 발명의 N-gram에 의한 색인데이터 생성방법은,

메모리에 저장되어 있는 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1', 'C₁,C₂~C_M-1','C₂~C_M-1',…'C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 한다.

도 2와 같이 메모리에 저장되어 있는 원문파일에는 서로다른 문자열을 갖는 R₁~R₅의 데이터, 즉, R₁-ABCD, R₂-ABABD, R₃-BCD, R₄-ABBD, R₅-BCACDA가 기록되어 있다고 가정할때, R₁ 레코드의 문자열 길이 M 은 C₀(A),C₁(B),C₂(C),C₃(D)이고, 이에대해 프로세서에서 추출되는 색인어는 'C₀,C₁,C₂,C₃-ABCD','C₁,C₂,C₃-BCD','C₂,C₃-CD','C₃-D'이며, 이와 같은 방법으로 다른 레코드의 문자열에 대해서도 색인어를 추출하여 인버티드 인덱스를 구성하는 것이다.

이때, 상기 인버티드 인덱스에는 추출된 색인어와 그에 대응하는 레코드가 기재되어 있으며, 추출된 색인어가 중복되는 것일 경우에는 그 색인어가 포함된 모든 레코드를 기재한다.

이러한 본 발명의 N-gram 방식에 의해 추출된 색인어를 이용하여 인버티드 인덱스를 구축하게되면, 기존 N-gram 방식이 지원하는 기능과 완전한 키워드 일치 및 절단어 형태의 검색을 모두 만족하는 검색을 지원할 수 있고, 옵셋정보가 기록되지 않으므로 저장 공간의 효율성을 재고하는 효과를 기대할 수 있게된다.

그리고, 인버티디 인덱스에 옵셋정보가 기재되지 않으므로 키워드 검색시 일일이 옵셋에 대한 정보를 연산하지 않아도 되므로 보다 빠르게 정보를 검색할 수 있게된다.

즉, 사용자가 키입력부를 조작하여 입력한 'AB'를 키워드로서 검색하면, 프로세서는 인버티드 인덱스에 구성되어 있는 색인어 중에서 'AB'로 시작하는 색인어정보로부터 레코드 R₁,R₂,R₄를 결과로 얻을 수 있고, 'BCD'를 키워드로서 검색하면 프로세서는 인버티드 인덱스에 구성되어 있는 색인어 중에서 'BCD'로 시작하는 색인어정보로부터 레코드 R₁,R₃를 결과로 얻을 수 있게 되는 것이다.

◈ Revers N-gram ◈

본 발명의 Revers N-gram에 의한 색인데이터 생성방법은,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C_M-1,C_M-2,C_M-3,…C₁,C₀','C_M-2,C_M-3,…C₁,C₀','C_M-3,…C₁,C₀',…'C_1,C₀','C_O'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 한다.

이러한 Reverse N-gram 에 의한 색인데이터 생성방법은 사진촬영 프로그램등과 같이 저장되는 파일명을 일련번호 형식으로 생성되는 데이터의 검색에 매우 유용하게 사용할 수 있다.

Reverse N-gram 은 레코드에 저장된 문자열을 거꾸로 뒤집어서 N-gram 방식으로 색인어를 추출하는 것으로, 이를 도 3 을 참조하여 설명하면 다음과 같다.

도 3과 같이 메모리에 저장되어 있는 원문파일에는 같거나 서로 다른 문자열을 갖는 R₁,R₂의 데이터, 즉, R₁-PICTURE001, R₂-PICTURE002가 기록되어 있다고 가정할때, R₁ 레코드의 문자열 길이 M 은 'C₀(P),C₁(I),C₂(C),C₃(T),C₄(U),C₅(R),C₆(E),C₇(0),C₈(0),C₉(1)'이고, 이에대해 프로세서에서 추출되는 색인어는 문자열을 뒤집은 후 N-gram 방식을 적용하여 '100ERUTCIP','00ERUTCIP','0ERUTCIP',....,'IP','P'이며, R2 레코드의 문자열 길이 M 은 ''C₀(P),C₁(I),C₂(C),C₃(T),C₄(U),C₅(R),C₆(E),C₇(0),C₈(0),C₉(2)'이고 이로부터 추출된 색인어는 '200ERUTCIP','00ERUTCIP','0ERUTCIP',....,'IP','P'이다.

상기 추출된 색인어를 살펴보면 '100ERUTCIP'와 '200ERUTCIP'만이 상이하고 나머지는 동일하므로, 최종적으로 추출된 색인어로서 구현한 인버티드 인덱스는 도 3 과 같다.

즉, 사진파일과 같이 문자열의 앞쪽은 대부분 동일하고 뒤쪽의 숫자부분만이 변화하는 것일때, Reverse N-gram을 사용하게되면 가변되는 숫자부분이 시작되도록 색인어를 추출할 수 있게되어 보다 신속하게 원하는 정보를 검색할 수 있게된다.

Reverse N-gram에 의해 구축된 인버티드 인덱스를 이용하여 정보를 검색할 때에는 사용자가 입력한 키워드를 뒤집어서 검색하면 된다.

◈ Simplex ◈

본 발명의 Simplex에 의한 색인데이터 생성방법은,

이에 대하여 프로세서에 의해 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 한다.

Simplex 에 의한 색인데이터 생성방법은 온전한 키워드 검색에 효율적으로 적용할 수 있다.

즉, 도 4와 같이 원문파일에는 서로다른 문자열을 갖는 R₁~R₅의 데이터, 즉, R₁-ABCD, R₂-ABABD, R₃-BCD, R₄-ABBD, R₅-BCACDA가 기록되어 있다고 가정할 때, 이에 대한 색인어 역시 원문파일의 문자열과 동일한 색인어를 추출하여 프로세서가 인버티드 인덱스를 구축하는 것이다.

◈ Duplex ◈

본 발명의 Duplex 방식에 의한 색인어 생성방법은,

이에대하여 프로세서에서 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1'와 이의 역순인 'C_M-1,C_M-2,C_M-3,…C₁,C₀'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 한다.

이러한 Duplex 방식에 의한 색인데이터 생성방법은 온전한 키워드 검색 또는 어느 한쪽 부분에 대한 절단어(S* OR *S) 형태의 검색 서비스를 효율적으로 지원할 수 있게된다.

도 5와 같이 원문파일에는 서로 다른 문자열을 갖는 R₁~R₅의 데이터, 즉, R₁-ABCD, R₂-ABABD, R₃-BCD, R₄-ABBD, R₅-BCACDA가 기록되어 있다고 가정할 때, 프로세서는 데이터 R₁- ABCD에 대한 색인어로서 'ABCD'와 이의 역순인 'DCBA'를 색인어로서 추출하고, 다른 데이터에 대해서도 동일한 방식으로 색인어를 추출하며, 이와같이 추출된 색인어를 이용하여 도 5와 같이 인버티드 인덱스를 구축한다.

예를들어, 사용자가 *BCD를 검색 키워드로 입력하였다면, 프로세서는 먼저 인버티드 인덱스로부터 색인어중 'BCD'로 시작하는 색인어를 검색하여 이와 관계된 레코드 R3을 얻고, 이후 입력키워드를 뒤집어서 'DCB'로 시작하는 색인어를 검색하여 레코드 R1과 R3을 얻는 것이며, 이를 종합하여 *BCD에 대한 검색결과로서 R1,R3 레코드를 출력하게 되는 것이다.

삭제

도 1 은 종래 N-gram 방식 인버티드 인덱스를 설명하기 위한 도면.
도 2 는 본 발명의 N-gram 방식 인버티드 인덱스를 설명하기 위한 도면.

도 3 은 본 발명의 Reverse N-gram 방식 인버티드 인덱스를 설명하기 위한 도면.

도 4 는 본 발명의 Simplex 방식 인버티드 인덱스를 설명하기 위한 도면.

도 5 는 본 발명의 Duplex 방식 인버티드 인덱스를 설명하기 위한 도면.

Claims

메모리에 저장되어 있는 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

특정 레코드에 저장된 문자열(S)의 길이를 M이라 하고, 전체 문자열(S)이 C₀,C₁,C₂~C_M-1로 구성되어 있을때,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1', 'C₁,C₂~C_M-1','C₂~C_M-1',…'C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 하는 인버티드 인덱스를 위한 색인데이터 생성방법.
메모리에 저장되어 있는 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

특정 레코드에 저장된 문자열(S)의 길이를 M이라 하고, 전체 문자열(S)이 C₀,C₁,C₂~C_M-1로 구성되어 있을때,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C_M-1,C_M-2,C_M-3,…C₁,C₀','C_M-2,C_M-3,…C₁,C₀','C_M-3,…C₁,C₀',…'C₁,C₀','C_O'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하는 것을 특징으로 하는 인버티드 인덱스를 위한 색인데이터 생성방법.
메모리에 저장되어 있는 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

특정 레코드에 저장된 문자열(S)의 길이를 M이라 하고, 전체 문자열(S)이 C₀,C₁,C₂~C_M-1로 구성되어 있을때,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하여 검색 키워드에 대해 완전 매칭이나 우절단 검색만을 위한 색인데이타 갯수를 줄여줄 수 있도록 한 것을 특징으로 하는 인버티드 인덱스를 위한 색인데이터 생성방법.
메모리에 저장되어 있는 원문파일에 R₁,R₂~R_n개의 레코드가 존재하고, 각각의 레코드에 길이가 같거나 서로다른 문자열(String)이 저장되어 있고,

특정 레코드에 저장된 문자열(S)의 길이를 M이라 하고, 전체 문자열(S)이 C₀,C₁,C₂~C_M-1로 구성되어 있을때,

이에대하여 프로세서에 의해 생성되는 색인어로서 'C₀,C₁,C₂~C_M-1'와 이의 역순인'C_M-1,C_M-2,C_M-3,…C₁,C₀'을 생성하고, 다른 레코드에 저장된 문자열에 대해서도 동일한 방법으로 색인어를 생성하여 검색 키워드에 대해 완전 매칭이나 좌절단 검색 또는 우절단 검색만을 위한 색인데이타 갯수를 줄여줄 수 있도록 한 것을 특징으로 하는 인버티드 인덱스를 위한 색인데이터 생성방법.