ݺߣ

ݺߣShare a Scribd company logo

1. boolean 검색

•
•
J
Jungkyu Lee
1 of 22
Downloaded 25 times
최신 정보 검색론 1. Boolean 검색
1.1 정보 검색의 예 • • • • • • 각 질의에 대응하여 텍스트를 순차 스캔 하는 것을 방 지하는 방법은 문헌을 미리 색인 (index)하는 것이다. Shakespeare 전집을 대상으로 Boolean 검색 모델의 기본을 살펴보자. Shakespeare 가 사용한 모든 단어 (Shakespeare 는 32,000 개의 서로 다른 단어를 사용했다.)에 대해 당 해 문헌이 각 단어를 포함하고 있는지 아닌지를 기록 한다고 해보자. 그 결과는 그림 1.1 과 같이 용어-문헌의 이진 발생 행 렬 (incidence matrix)로 표현된다. 용어 (term)는 색인의 단위로서(자세한 것은 2.2 절 에서 다룬다) 일반적으로 단어다. 당분간은 단어라고 생각해도 된다. 그렇지만 정보 검 색 문헌에서는 통상적으로 용어를 지칭한다. 왜냐하 면 ‘1-9" 또는 “Hong Kong“ 처럼 일부는 단어로 간 주하지 않기 때문이다.
1.1 정보 검색의 예 • 이제 행렬의 가로 또는 세로 중 어느 것을 보느냐에 따 라. 각 용어의 벡터 값(용어가 출현한 문헌들을 나타 냄)을 확인하고 내 또는 문헌의 벡터 값(문헌에 출현 한 용어들을 나타냄)을 알 수 있다
• 질의 식 ’‘Brutus AND Caesar AND NOT Calpurnia" 에 답하기 위해 Brutus, Caesar, Calpurnia 의 벡터 값을 계산하고 마지막 용어의 보수 값을 얻은 다음 AND 비트연산을 수행한다. • 그래서 이 질의에 대한 답은 “'Antony and Cleopatra" 와 ‘Hamlet’ 이 된다(그림1.2).
1.1 정보검색 문제의 예 • • • • • • • • Boolean 검색 모델(boolean retrieval model)은 용 어들을 Boolean 논리식 형태로 모든 질의를 작성할 수 있는 정보 검색 모델로서, 질의식을 구성하는 용어 들은 AND, OR, NOT 연산자로 결합된다. 이 모델은 모든 문헌을 단순한 단어의 집합으로 간주 한다 좀 더 현실적인 시나리오를 생각해보자. 여기서 몇 가 지 전문 용어와 표기도 함께 소개한다. 문헌 수 N=100 만 건이 있다고 가정하자. 여기서 문 헌(document) 은 어떤 단위가 되었든지 간에 하나의 검색 시스템을 구축하기로 결정한 기반 단위를 의미 한다. 문헌은 개인 메모 또는 한 책의 장일 수도 있다(자세 한 사항은 2.1 .2절에서 다룬다. ). 검색 대상이 되는 문헌의 집단을 (문헌) 컬렉션 (collection) 이라 하며,말뭉치 (corpus: 텍스트의 본 문)라고도 한다. 각 문헌은 약 1,000 단어(책의 2-3 쪽 분량) 길이라 고 가정하자. 공백 문자와 구두점을 포함하여 단어당 평균 6 바이트 라고 가정하면/ 문헌 컬렉션은 약 6 GB 분량이 된다.
1.1 정보검색 문제의 예 • • • • • • • • • 이들 문헌에서 용어 수 M= 약 500,000 개 정도이다. 우리가 선택한 수치는 특별할 것이 없으며 데이터 양 으로는 차이가 있을 수 있다. 그렇지만, 다루어야 할 문제가 어떤 것인지를 시사해 준다. 5.1 절에서 이러한 데이터 규모에 대해 그 가정 을 다루고 모델링한다. 우리의 목적은 단순 검색 (ad hoc retrieval) 작업을 다루는 시스템을 개발하는 것이다. 이것은 가장 전형적인 정보 검색 작업이다. 여기서/ 시스템의 목적은 임의의 사용자가 던진 질의 를 한 번에 하나씩 시스템에 전달하여 사용자의 정보 요구에 적합한 문헌을 컬렉션에서 찾아 제공하는 것 이다. 정보 요구(information need) 는 사용자가 더 알아 보고자 하는 주제이며, 질의와는 다르다. 질의 (query) 는 사용자의 정보 요구를 컴퓨터에 전달 하기 위해 사용자가 표현하는 것이다. 어떤 문헌이 사용자의 개인적인 정보요구와 관련하여 가치 있는 정보를 수록하고 있다고 사용자가 판단한 다면 그 문헌은 적합(relevant) 문헌이다.
• • • • • • 앞에서 설명한 예제는 정보 요구가 특정 단어들로 정 의되었다는 점에서 다소 작위적이다 반면. 사용자는 “파이프 누수” 주제에 관심이 있을 때. 그 단어들을 정확하게 표현하든지 아니면 “파이프 파 열” 등 다른 단어로 그 개념을 표현하든지 상관없이 적합문헌을 찾고 싶어 한다. 정보검색 시스템의 유효성 (effectiveness)을 평가하 는데 있어서(예: 검색 결과의 품질) 사용자는 어떤 질 의에 대해 시스템이 반환한 결과에 대한 다음의 두 가 지 핵심적인 통계량을 알고 싶어 한다 정확률(Precision): 반환된 결과 중 정보 요구에 적합 한 비율은 얼마인가? 재현율(Recall) : 컬렉션에 포함된 적합 문헌 중 시스 템에 의해 반환된 적합 문헌이 차지하는 비율은 얼마 인가 정획률과 재현율을 포함한 적합성과 평가척도에 대한 자세한 논의는 8 장에서 다룬다.
• • • • • • • • 단순한 방법으로 용어-문헌 행렬을 민들 수는 없다. 왜냐하면， 500 K x 1M 행렬은 오백억 개의 0 과 1 을 항으로 갖기 때문에 컴퓨터 메모리에 적재하기 어 렵다. 그러나 이 행렬은 극단적으로 희소하기 때문에， 0 이 아닌 값을 갖는 항은 얼마 되지 않는다는 점에 주목해 야 한다 즉 각 문헌은 1，000 개의 단어로 구성되고/ 그 행렬 은 많아야 10 억 개의 1 을 가지므로 99.8% 의 항들 은 0 을 갖는다. 따라서 1 을 갖는 향들만을 기록하는 것이 훨씬 더 좋 다. 이 방법이 바로 역색인 (inverted index) 이며 정보 검색에서 첫 번째 주요 개념의 핵심을 이룬다. 색인은 항상 용어로부터 용어들이 출현한 문헌의 특 정 부분으로 사상되므로 “역(inverted)" 이라는 말을 붙일 필요는 없다 그럼에도 역색인 혹은 역파일 (inverted file)은 정보 검색 분야에서는 표준용어가 되었다
• • • • 역색인의 기본원리는 그림 1.3 에서 보는 바와 같다. 용어 사전 (dictionary)을 어휘집 (vocabulary) 또는 어휘 사전(lexicon) 이라고도 하는데 이 책에서 는 자료구조를 말할 때는 사전이라 하고,용어 집합에 대해서는 어휘집이라 한다. 다음으로,각 용어에 대해서 어떤 문헌에 그 용어가 출 현하는지를 기록하는 목록을 작성한다. 이 목록의 각 행을 통상 포스팅 (posting) 이라 하는 데 그 항에는 어떤 문헌에서 출현하는 용어를 기록한 다.(그 문서 내의 위치도 기록한다.)
1.1 정보 검색의 예 • • • 그렇게 되면 그 목록을 포스팅 목록(postings list) (또는 역목록)"이라 하고/ 모든 포스팅 목록들을 일컬 어 포스팅 (posting) 이라 한다. 그림 1.3 에 있는 사전은 알파뱃 순으로 정렬되었고, 각 포스팅 목록은 문헌 식별변호로 정렬 이것이 왜 필요한 것인가에 대해서는 아래의 1.3 절에 서 살펴보고, 나중에는 이 방법의 대안에 대해서도 살 펴볼 것이다(7. 1.5 절).되어 있다.
1.2 역색인 구축의 첫 단계 • • • • • 검색할 때 색인의 효과를 높이려면 미리 색인을 구축 해두어야 한다. 그 주요 과정은 다음과 같다. 처리 과정의 초기 단계/ 즉 1~3 단계는 2.2 절에서 살 펴볼 것이다. 그때까지는 토큰(token)과 정규화 토큰(normalized token)을 단어와 거의 유사한 것으로 간주한다. 여기서는 첫 세 단계를 이미 수행했다고 가정하고/ 정 렬-기반 색인 (sort-based indexing)으로 기본적인 역색인 구축내용을 살펴본다.
1.2 역색인 구축의 첫 단계 • • • 어떤 문헌 컬렉션 내에서, 각 문헌은 문헌식 별자(do cID) 라는 고유한 연속번호를 갖는다고 전제한다. 색인 구축과정에서 새로운 문헌이 들어오면 각각에 그냥 연속적인 정수를 할당할 수 있다. 색인의 입력값은 각 문헌의 정규화 토큰 목록이며 그 림 1 .4처럼 용어-문헌 식별자 쌍으로 구성된 목록으 로 간주할 수 있다.
1.2 역색인 구축의 첫 단계 • • 색인 결과를 저장하기 위해서 사전과 포스팅 목록을 위한 저장 공간이 필요하다. 포스팅 목록이 더 커서, 사전은 일반적으로 메모리 에 있는데 비해 포스팅 목록들은 디스크에 저장된다.
1.3 Boolean 질의 처리 • 역색인과 기본 불리언 검색 모델을 이용해서 질의를 어떻게 처리할까? 다음과 같이 단순 결합 질의 (simple conjllnctive qllery) 처리를 생각해보라. • 그림 1.3 에서 일부 보았던 역색인에 대해 다음을 수 행한다. 1. 사전에서 Brutus 의 위치를 확인한다. 2. Brutus 와 관련된 포스팅을 검색한다. 3. 사전에서 Calpurnia 의 위치를 확인한다. 4. Calpurnia 와 관련된 포스팅을 검색한다. 5 그림 1 .5에서 보았던 것처럼 두 포스팅 목록의 교 집합을 구한다. • • • • •
1.3 Boolean 질의 처리 • • • • 교집합(intersection) 연산은 매우 중요하다. 왜냐하면, 두 용어를 모두 포함하는 문헌들을 빨리 찾 을 수 있도록 하기 위해서다. 포스팅 목록으로부터 교집합 연산을 효과적으로 수행 해야 하기 때문이다 병합 알고리즘을 이용하여 포스팅 목록의 교집합을 구하는 단순하고도 효과적인 방법이 있다(그림 1.6)
1.3 Boolean 질의 처리 • 디음과 같이 좀더 복잡한 질의를 처리하기 위해 교집 합연산을 확장할 수 있다. • 질의 최적화(query optimization) 란 시스템이 수행 해야 할 총 작업량을 최소화시킬 목적으로 질의에 대 한 응답을 조직하는 방법을 선택하는 과정이다. 불리언 질의에 대한 최적화의 주요 내용은 포스팅 목 록에 접근하는 순서를 결정하는 것이다. 질의 처리를 위한 최적의 순서는 무엇일까? 다음과 같 이 f 개의 용어들을 AND 조합한 질의를 생각해보자. • • • • • t 개의 용어에 대해 포스팅을 찾은 다음 AND 연산을 수행해야 한다. 가장 일반적인 방법은 문헌 빈도가 낮은 용어부터 처 리하는 것이다. 만일 제일 작은 두 포스팅 목록에 대해 교집합 연산부 터 수행하면 모든 중간 결과는 제일 작은 포스팅 목록 보다 결코 크지 않을 것이므로 총 작업량을 최소화시 킬 수 있다.
1.3 Boolean 질의 처리 • 따라서 그림 1.3 의 포스팅 목록에 대해 위의 질의는 다음과 같이 실행한다. • 이것이 사전에 용어의 출현 빈도를 기록하는 첫 번째 이유이다. 이처럼 어떤 포스팅 목록에 접근하기 이전에 메모리 에 있는 데이터를 근거로 연산순서를 결정할 수 있다. 이제 다음과 같이 더 일반적인 질의를 최적화시키는 방법에 대해 생각해 보자. • • • • • • 이전과 마찬가지로, 모든 용어의 출현 빈도를 얻으면 그 논리합 용어의 출현 빈도를 합하면 각 OR 항의 크 기를 예측할 수 있다. 그런 다음 논리합으로 묶인 각 용어의 크기가 낮은 순 서부터 질의를 처리한다. 임의의 Boolean. 질의에 대해서 복잡한 질의식의 경 우, 중간 단계의 질의식에 대한 답들을 평가하여 임시 로 저장해야 한다. 그러나 많은 경우, 질의는 순전히 논리곱으로 구성된 다
1.3 Boolean 질의 처리 • • • • 왜냐하면, 질의 언어의 속성 때문이거나 아니면 단순 히 사용자들이 표현하는 질의의 가장 일반적인 유형 이기 때문이다. 이런 경우에는 병합포스팅 목록을 두 개의 입력과 하 나의 출력이 있는 기능으로보는것보다는각각검색된 포스팅목록과 현재 메모리에 있는 중간 결과를 교집 합 연산시키는 것이 훨씬 효율적이다. 여기서 중간 결과는 가장 적은 출현 빈도를 보이는 포 스팅 목록을 로딩하여 초기화한다. 이 알고리즘은 그림 1. 7과 같다.
1.3 Boolean 질의 처리 • • • • • 교집합 연산은 따라서 비대칭이다. 왜냐하면, 중간결 과는 메모리에 있지만 교집합될 용어의 포스팅 목록 은 디스크에 있기 때문이다. 또 중간 결과는 항상 적어도 다른 목록만큼 짧아지며, 많은 경우 매우 짧아진다. 포스팅 교집합은 그림 1.6 과 같은 알고리즘으로 문제 없이 처리되지만, 목록 길이 간의 차이가 매우 클 때는 다른 대안을 생각할 수 있다. 중간 결과 목록에서 불필요한 항목을 수정하거나 표 시하여 교집합을 계산할 수 있다. 또는, 중간 결과 목록의 포스팅 목록이 길면 이진 검색 을 수행할 수도 있다. 또 다른 방법은 긴 포스팅 목록 을 해시 테이블로 저장함으로써 중간결과에 포함되어 있는지를 확인하는 시간은 선형이나 로그시간이 아니 라 상수시간으로 계산할 수 있다.
1.4 확장 Boolean 모델과 순위 검색 • • • • • • Boolean 검색 모델은 벡터 공간모형 (6.3 절)과 같은 순위 검색 모형 (ranked retrieval model)과 비교된 다. 순위 검색 모형에서 사용자는 대부분 자연어 질의 (free text query), 즉 질의를 표현하려면 연산자와 같은 정교한 언어를 사용하지 않고 자연어 문장처럼 단어를 나열하는 편이 더 효과적인 방법이며, 시스템 도 질의에 가장 적합한 순으로 문헌을 정렬하는 편이 더 효과적일 것이다. 수십 년 동안 이러한 장점을 갖는 순위 검색 모형에 관 한 학술적인 연구기- 있었음에도 대부분의 검색 시스 템은 Boolean 검색 모델을 사용해왔다. 근 30 년 동안 대형 정보 제공;7;1들도 검색 시스템의 선택 사양으로만 제공해 오긴 했지만 그렇다고 해서 현재 사용되는 Boolean 연산지들(AND, OR, NOT) 만을 제공하는 것은 아니다. 단순 Boole때 질의에서는 검색 결과가 정렬되지 않아 서 시용자들이 원히는 정보를 이용하기에는 너무 제 한적이다. 그리고 이들시스템은 근접 연산자와 같은 추가적인 연산자를 제공하는 확장 Boolean 검색 모델을 구현 하였다.
1.4 확장 Boolean 모델과 순위 검색 • • • 근접 연산자(proximity operator) 는 질의 에 있는 두 용어가 한 문헌에서 서로 가까이 출현하는 조건을 지 정하는 데 사용된다. 여기서 말하는 근접은 단어 사이 의 거리일 수도 있고 문장이나 문단과 같은 구조적인 단위로 제한승}는 것을 의미하기도 한다. 웹 검색에서는 긴 질의나 근접 연산지를 사용하는 것 이 일반적이지 않다는 것을 알아야 한다. 질의 길이는 평균 10 단어 내외다. 웹 검색의 일반적 인 형태와는 달리, 여기서는 단어 사이의 공백은 OR 을 의미하고, &는 AND이며 ， Is, /p, /k 는 문장/ 문 단 혹은 k 개 단어 내에서 어울려야 됨을 의미한다. 또 한/큰따옴표(“")는 구절 검색(phrase search)(연속적 인 단어)을 의미한다(2 .4절 참조).
1.4 확장 Boolean 모델과 순위 검색 • • 많은 사용샤 특히 전문가들은 Boolean 질의 모델을 더 선호한다. Boolean 질의는 정확하다. 하나의 문헌은 특정 질의에 일치하거나 그렇지 않다. 사용자는 무엇이 검색될지를 더욱더 잘 통제할 수 있 고 투명하게 확인할 수 있도록 제안한다.

More Related Content

1. boolean 검색

  • 1. 최신 정보 검색론 1. Boolean 검색
  • 2. 1.1 정보 검색의 예 • • • • • • 각 질의에 대응하여 텍스트를 순차 스캔 하는 것을 방 지하는 방법은 문헌을 미리 색인 (index)하는 것이다. Shakespeare 전집을 대상으로 Boolean 검색 모델의 기본을 살펴보자. Shakespeare 가 사용한 모든 단어 (Shakespeare 는 32,000 개의 서로 다른 단어를 사용했다.)에 대해 당 해 문헌이 각 단어를 포함하고 있는지 아닌지를 기록 한다고 해보자. 그 결과는 그림 1.1 과 같이 용어-문헌의 이진 발생 행 렬 (incidence matrix)로 표현된다. 용어 (term)는 색인의 단위로서(자세한 것은 2.2 절 에서 다룬다) 일반적으로 단어다. 당분간은 단어라고 생각해도 된다. 그렇지만 정보 검 색 문헌에서는 통상적으로 용어를 지칭한다. 왜냐하 면 ‘1-9" 또는 “Hong Kong“ 처럼 일부는 단어로 간 주하지 않기 때문이다.
  • 3. 1.1 정보 검색의 예 • 이제 행렬의 가로 또는 세로 중 어느 것을 보느냐에 따 라. 각 용어의 벡터 값(용어가 출현한 문헌들을 나타 냄)을 확인하고 내 또는 문헌의 벡터 값(문헌에 출현 한 용어들을 나타냄)을 알 수 있다
  • 4. • 질의 식 ’‘Brutus AND Caesar AND NOT Calpurnia" 에 답하기 위해 Brutus, Caesar, Calpurnia 의 벡터 값을 계산하고 마지막 용어의 보수 값을 얻은 다음 AND 비트연산을 수행한다. • 그래서 이 질의에 대한 답은 “'Antony and Cleopatra" 와 ‘Hamlet’ 이 된다(그림1.2).
  • 5. 1.1 정보검색 문제의 예 • • • • • • • • Boolean 검색 모델(boolean retrieval model)은 용 어들을 Boolean 논리식 형태로 모든 질의를 작성할 수 있는 정보 검색 모델로서, 질의식을 구성하는 용어 들은 AND, OR, NOT 연산자로 결합된다. 이 모델은 모든 문헌을 단순한 단어의 집합으로 간주 한다 좀 더 현실적인 시나리오를 생각해보자. 여기서 몇 가 지 전문 용어와 표기도 함께 소개한다. 문헌 수 N=100 만 건이 있다고 가정하자. 여기서 문 헌(document) 은 어떤 단위가 되었든지 간에 하나의 검색 시스템을 구축하기로 결정한 기반 단위를 의미 한다. 문헌은 개인 메모 또는 한 책의 장일 수도 있다(자세 한 사항은 2.1 .2절에서 다룬다. ). 검색 대상이 되는 문헌의 집단을 (문헌) 컬렉션 (collection) 이라 하며,말뭉치 (corpus: 텍스트의 본 문)라고도 한다. 각 문헌은 약 1,000 단어(책의 2-3 쪽 분량) 길이라 고 가정하자. 공백 문자와 구두점을 포함하여 단어당 평균 6 바이트 라고 가정하면/ 문헌 컬렉션은 약 6 GB 분량이 된다.
  • 6. 1.1 정보검색 문제의 예 • • • • • • • • • 이들 문헌에서 용어 수 M= 약 500,000 개 정도이다. 우리가 선택한 수치는 특별할 것이 없으며 데이터 양 으로는 차이가 있을 수 있다. 그렇지만, 다루어야 할 문제가 어떤 것인지를 시사해 준다. 5.1 절에서 이러한 데이터 규모에 대해 그 가정 을 다루고 모델링한다. 우리의 목적은 단순 검색 (ad hoc retrieval) 작업을 다루는 시스템을 개발하는 것이다. 이것은 가장 전형적인 정보 검색 작업이다. 여기서/ 시스템의 목적은 임의의 사용자가 던진 질의 를 한 번에 하나씩 시스템에 전달하여 사용자의 정보 요구에 적합한 문헌을 컬렉션에서 찾아 제공하는 것 이다. 정보 요구(information need) 는 사용자가 더 알아 보고자 하는 주제이며, 질의와는 다르다. 질의 (query) 는 사용자의 정보 요구를 컴퓨터에 전달 하기 위해 사용자가 표현하는 것이다. 어떤 문헌이 사용자의 개인적인 정보요구와 관련하여 가치 있는 정보를 수록하고 있다고 사용자가 판단한 다면 그 문헌은 적합(relevant) 문헌이다.
  • 7. • • • • • • 앞에서 설명한 예제는 정보 요구가 특정 단어들로 정 의되었다는 점에서 다소 작위적이다 반면. 사용자는 “파이프 누수” 주제에 관심이 있을 때. 그 단어들을 정확하게 표현하든지 아니면 “파이프 파 열” 등 다른 단어로 그 개념을 표현하든지 상관없이 적합문헌을 찾고 싶어 한다. 정보검색 시스템의 유효성 (effectiveness)을 평가하 는데 있어서(예: 검색 결과의 품질) 사용자는 어떤 질 의에 대해 시스템이 반환한 결과에 대한 다음의 두 가 지 핵심적인 통계량을 알고 싶어 한다 정확률(Precision): 반환된 결과 중 정보 요구에 적합 한 비율은 얼마인가? 재현율(Recall) : 컬렉션에 포함된 적합 문헌 중 시스 템에 의해 반환된 적합 문헌이 차지하는 비율은 얼마 인가 정획률과 재현율을 포함한 적합성과 평가척도에 대한 자세한 논의는 8 장에서 다룬다.
  • 8. • • • • • • • • 단순한 방법으로 용어-문헌 행렬을 민들 수는 없다. 왜냐하면， 500 K x 1M 행렬은 오백억 개의 0 과 1 을 항으로 갖기 때문에 컴퓨터 메모리에 적재하기 어 렵다. 그러나 이 행렬은 극단적으로 희소하기 때문에， 0 이 아닌 값을 갖는 항은 얼마 되지 않는다는 점에 주목해 야 한다 즉 각 문헌은 1，000 개의 단어로 구성되고/ 그 행렬 은 많아야 10 억 개의 1 을 가지므로 99.8% 의 항들 은 0 을 갖는다. 따라서 1 을 갖는 향들만을 기록하는 것이 훨씬 더 좋 다. 이 방법이 바로 역색인 (inverted index) 이며 정보 검색에서 첫 번째 주요 개념의 핵심을 이룬다. 색인은 항상 용어로부터 용어들이 출현한 문헌의 특 정 부분으로 사상되므로 “역(inverted)" 이라는 말을 붙일 필요는 없다 그럼에도 역색인 혹은 역파일 (inverted file)은 정보 검색 분야에서는 표준용어가 되었다
  • 9. • • • • 역색인의 기본원리는 그림 1.3 에서 보는 바와 같다. 용어 사전 (dictionary)을 어휘집 (vocabulary) 또는 어휘 사전(lexicon) 이라고도 하는데 이 책에서 는 자료구조를 말할 때는 사전이라 하고,용어 집합에 대해서는 어휘집이라 한다. 다음으로,각 용어에 대해서 어떤 문헌에 그 용어가 출 현하는지를 기록하는 목록을 작성한다. 이 목록의 각 행을 통상 포스팅 (posting) 이라 하는 데 그 항에는 어떤 문헌에서 출현하는 용어를 기록한 다.(그 문서 내의 위치도 기록한다.)
  • 10. 1.1 정보 검색의 예 • • • 그렇게 되면 그 목록을 포스팅 목록(postings list) (또는 역목록)"이라 하고/ 모든 포스팅 목록들을 일컬 어 포스팅 (posting) 이라 한다. 그림 1.3 에 있는 사전은 알파뱃 순으로 정렬되었고, 각 포스팅 목록은 문헌 식별변호로 정렬 이것이 왜 필요한 것인가에 대해서는 아래의 1.3 절에 서 살펴보고, 나중에는 이 방법의 대안에 대해서도 살 펴볼 것이다(7. 1.5 절).되어 있다.
  • 11. 1.2 역색인 구축의 첫 단계 • • • • • 검색할 때 색인의 효과를 높이려면 미리 색인을 구축 해두어야 한다. 그 주요 과정은 다음과 같다. 처리 과정의 초기 단계/ 즉 1~3 단계는 2.2 절에서 살 펴볼 것이다. 그때까지는 토큰(token)과 정규화 토큰(normalized token)을 단어와 거의 유사한 것으로 간주한다. 여기서는 첫 세 단계를 이미 수행했다고 가정하고/ 정 렬-기반 색인 (sort-based indexing)으로 기본적인 역색인 구축내용을 살펴본다.
  • 12. 1.2 역색인 구축의 첫 단계 • • • 어떤 문헌 컬렉션 내에서, 각 문헌은 문헌식 별자(do cID) 라는 고유한 연속번호를 갖는다고 전제한다. 색인 구축과정에서 새로운 문헌이 들어오면 각각에 그냥 연속적인 정수를 할당할 수 있다. 색인의 입력값은 각 문헌의 정규화 토큰 목록이며 그 림 1 .4처럼 용어-문헌 식별자 쌍으로 구성된 목록으 로 간주할 수 있다.
  • 13. 1.2 역색인 구축의 첫 단계 • • 색인 결과를 저장하기 위해서 사전과 포스팅 목록을 위한 저장 공간이 필요하다. 포스팅 목록이 더 커서, 사전은 일반적으로 메모리 에 있는데 비해 포스팅 목록들은 디스크에 저장된다.
  • 14. 1.3 Boolean 질의 처리 • 역색인과 기본 불리언 검색 모델을 이용해서 질의를 어떻게 처리할까? 다음과 같이 단순 결합 질의 (simple conjllnctive qllery) 처리를 생각해보라. • 그림 1.3 에서 일부 보았던 역색인에 대해 다음을 수 행한다. 1. 사전에서 Brutus 의 위치를 확인한다. 2. Brutus 와 관련된 포스팅을 검색한다. 3. 사전에서 Calpurnia 의 위치를 확인한다. 4. Calpurnia 와 관련된 포스팅을 검색한다. 5 그림 1 .5에서 보았던 것처럼 두 포스팅 목록의 교 집합을 구한다. • • • • •
  • 15. 1.3 Boolean 질의 처리 • • • • 교집합(intersection) 연산은 매우 중요하다. 왜냐하면, 두 용어를 모두 포함하는 문헌들을 빨리 찾 을 수 있도록 하기 위해서다. 포스팅 목록으로부터 교집합 연산을 효과적으로 수행 해야 하기 때문이다 병합 알고리즘을 이용하여 포스팅 목록의 교집합을 구하는 단순하고도 효과적인 방법이 있다(그림 1.6)
  • 16. 1.3 Boolean 질의 처리 • 디음과 같이 좀더 복잡한 질의를 처리하기 위해 교집 합연산을 확장할 수 있다. • 질의 최적화(query optimization) 란 시스템이 수행 해야 할 총 작업량을 최소화시킬 목적으로 질의에 대 한 응답을 조직하는 방법을 선택하는 과정이다. 불리언 질의에 대한 최적화의 주요 내용은 포스팅 목 록에 접근하는 순서를 결정하는 것이다. 질의 처리를 위한 최적의 순서는 무엇일까? 다음과 같 이 f 개의 용어들을 AND 조합한 질의를 생각해보자. • • • • • t 개의 용어에 대해 포스팅을 찾은 다음 AND 연산을 수행해야 한다. 가장 일반적인 방법은 문헌 빈도가 낮은 용어부터 처 리하는 것이다. 만일 제일 작은 두 포스팅 목록에 대해 교집합 연산부 터 수행하면 모든 중간 결과는 제일 작은 포스팅 목록 보다 결코 크지 않을 것이므로 총 작업량을 최소화시 킬 수 있다.
  • 17. 1.3 Boolean 질의 처리 • 따라서 그림 1.3 의 포스팅 목록에 대해 위의 질의는 다음과 같이 실행한다. • 이것이 사전에 용어의 출현 빈도를 기록하는 첫 번째 이유이다. 이처럼 어떤 포스팅 목록에 접근하기 이전에 메모리 에 있는 데이터를 근거로 연산순서를 결정할 수 있다. 이제 다음과 같이 더 일반적인 질의를 최적화시키는 방법에 대해 생각해 보자. • • • • • • 이전과 마찬가지로, 모든 용어의 출현 빈도를 얻으면 그 논리합 용어의 출현 빈도를 합하면 각 OR 항의 크 기를 예측할 수 있다. 그런 다음 논리합으로 묶인 각 용어의 크기가 낮은 순 서부터 질의를 처리한다. 임의의 Boolean. 질의에 대해서 복잡한 질의식의 경 우, 중간 단계의 질의식에 대한 답들을 평가하여 임시 로 저장해야 한다. 그러나 많은 경우, 질의는 순전히 논리곱으로 구성된 다
  • 18. 1.3 Boolean 질의 처리 • • • • 왜냐하면, 질의 언어의 속성 때문이거나 아니면 단순 히 사용자들이 표현하는 질의의 가장 일반적인 유형 이기 때문이다. 이런 경우에는 병합포스팅 목록을 두 개의 입력과 하 나의 출력이 있는 기능으로보는것보다는각각검색된 포스팅목록과 현재 메모리에 있는 중간 결과를 교집 합 연산시키는 것이 훨씬 효율적이다. 여기서 중간 결과는 가장 적은 출현 빈도를 보이는 포 스팅 목록을 로딩하여 초기화한다. 이 알고리즘은 그림 1. 7과 같다.
  • 19. 1.3 Boolean 질의 처리 • • • • • 교집합 연산은 따라서 비대칭이다. 왜냐하면, 중간결 과는 메모리에 있지만 교집합될 용어의 포스팅 목록 은 디스크에 있기 때문이다. 또 중간 결과는 항상 적어도 다른 목록만큼 짧아지며, 많은 경우 매우 짧아진다. 포스팅 교집합은 그림 1.6 과 같은 알고리즘으로 문제 없이 처리되지만, 목록 길이 간의 차이가 매우 클 때는 다른 대안을 생각할 수 있다. 중간 결과 목록에서 불필요한 항목을 수정하거나 표 시하여 교집합을 계산할 수 있다. 또는, 중간 결과 목록의 포스팅 목록이 길면 이진 검색 을 수행할 수도 있다. 또 다른 방법은 긴 포스팅 목록 을 해시 테이블로 저장함으로써 중간결과에 포함되어 있는지를 확인하는 시간은 선형이나 로그시간이 아니 라 상수시간으로 계산할 수 있다.
  • 20. 1.4 확장 Boolean 모델과 순위 검색 • • • • • • Boolean 검색 모델은 벡터 공간모형 (6.3 절)과 같은 순위 검색 모형 (ranked retrieval model)과 비교된 다. 순위 검색 모형에서 사용자는 대부분 자연어 질의 (free text query), 즉 질의를 표현하려면 연산자와 같은 정교한 언어를 사용하지 않고 자연어 문장처럼 단어를 나열하는 편이 더 효과적인 방법이며, 시스템 도 질의에 가장 적합한 순으로 문헌을 정렬하는 편이 더 효과적일 것이다. 수십 년 동안 이러한 장점을 갖는 순위 검색 모형에 관 한 학술적인 연구기- 있었음에도 대부분의 검색 시스 템은 Boolean 검색 모델을 사용해왔다. 근 30 년 동안 대형 정보 제공;7;1들도 검색 시스템의 선택 사양으로만 제공해 오긴 했지만 그렇다고 해서 현재 사용되는 Boolean 연산지들(AND, OR, NOT) 만을 제공하는 것은 아니다. 단순 Boole때 질의에서는 검색 결과가 정렬되지 않아 서 시용자들이 원히는 정보를 이용하기에는 너무 제 한적이다. 그리고 이들시스템은 근접 연산자와 같은 추가적인 연산자를 제공하는 확장 Boolean 검색 모델을 구현 하였다.
  • 21. 1.4 확장 Boolean 모델과 순위 검색 • • • 근접 연산자(proximity operator) 는 질의 에 있는 두 용어가 한 문헌에서 서로 가까이 출현하는 조건을 지 정하는 데 사용된다. 여기서 말하는 근접은 단어 사이 의 거리일 수도 있고 문장이나 문단과 같은 구조적인 단위로 제한승}는 것을 의미하기도 한다. 웹 검색에서는 긴 질의나 근접 연산지를 사용하는 것 이 일반적이지 않다는 것을 알아야 한다. 질의 길이는 평균 10 단어 내외다. 웹 검색의 일반적 인 형태와는 달리, 여기서는 단어 사이의 공백은 OR 을 의미하고, &는 AND이며 ， Is, /p, /k 는 문장/ 문 단 혹은 k 개 단어 내에서 어울려야 됨을 의미한다. 또 한/큰따옴표(“")는 구절 검색(phrase search)(연속적 인 단어)을 의미한다(2 .4절 참조).
  • 22. 1.4 확장 Boolean 모델과 순위 검색 • • 많은 사용샤 특히 전문가들은 Boolean 질의 모델을 더 선호한다. Boolean 질의는 정확하다. 하나의 문헌은 특정 질의에 일치하거나 그렇지 않다. 사용자는 무엇이 검색될지를 더욱더 잘 통제할 수 있 고 투명하게 확인할 수 있도록 제안한다.