http://www-csli.stanford.edu/~schuetze/information-retrieval-book.html
Introduction to Information Retrieval, Cambridge University Press. 2008.
Cambridge IR book 입니다.
검색엔진에 대해 아주 유용한 자료입니다.
영문이라...다소 ㅋ
1장. Information retrieval using the Boolean model
Information Retrieval(IR)이란?
여러 의미로 사용될 수 있지만 학문적으로 이야기하자면 "인터넷과 같은 네트워크 상의 또는 로컬 컴퓨터와 같은 큰 데이터의 저장소에서 원하는 정보를 가지고 있는 데이터(material of unstructured nature)를 찾는 것"으로 정의될 수 있다.
여기서 Unstructured nature(data)는 데이터베이스에 저장된 데이터처럼 정확히 분류되거나 구조화되지 않은 순수한 데이터, 즉 일반적으로 문자열 데이터라고 가리킨다. 뭐 예를 들자면, E-Mail의 내용이나, 홈페이지의 게시물의 내용, 아니면 어떤 책이나 시집의 내용 등이 Unstructured data가 될 수 있다.
이런 데이터들은 정확히 분류를 나누거나 구조화하기 힘들기 때문에 데이터베이스를 이용해서 원하는 데이터를 찾는 것에 많은 어려움이 있지만, IR 시스템을 이용하면 비교적 쉽고 정확하게 원하는 데이터를 찾을 수 있다는 장점이 있다. [이하 본문에서는 장점에 대해서 주구장창 설명하고 있지만 여기서는 패스...;)]
정보 검색의 간단한 맛보기 예제. (An example informatino retrieval problem)
일반적으로 사람들이 많이 들고 있는 셰익스피어 전집(외국, 특히나 영국 사람들은 그런가보다. 한국이라면 '한국위인전집' 이런거쯤 되려나..)에서 다음의 조건을 만족하는 작품을들 검색(앞으로는 '찾기'를 '검색'으로 사용하겠다.)해보도록 하자.
Example) Brutus AND Caesar AND NOT Calpurnia
가장 간단한 방법은 각 작품의 텍스트를 선형으로 읽어 들이면서 정규 표현식을 이용해서 원하는 결과를 찾아내는 것이다.(본문에서는 grep을 정규 표현식을 이용해서 실행한다고 되어 있음. 의역임.) 이건 간단한 방법 중 하나이고, 일반적으로는 더 많은 요구사항이 필요로하게 된다. 다음 그 예를 보여준다.
1. 매우 큰 문서의 빠른 처리 : 온라인 상의 데이터는 기하급수적으로 증가하고 있기 때문에 10억에서 1조에 이르는 방대한 양의 데이터를 빠르게 처리할 수 있어야 한다.
2. 질의 문장의 유연성 : 예를 들자면, Romans NEAR countrymen(NEAR는 5단어 이내를 의미)과 같은 질의문은 grep과 같은 명령어로는 실행할 수 없다.
3. 순위 검색 : 수많은 검색 결과 중 가장 적절한 검색 결과를 우선적으로 보여줄 수 있어야 한다.
위와 같은 요구사항은 선형 검색(linear scanning)으로는 처리할 수 없다. 이를 처리하는 가장 좋은 방법 중 하나는 '문서'를 '색인'하는 것이다. 여기서 색인은 간단히 말해 어느 문서(document)에 어떤 단어(term)가 포함이 되어 있는지 나열하는 것을 이야기 한다. 여기서 단어(term)는 문헌상의 '단어'가 아닌 IR 시스템 상에서의 색인 단위로 취급된다. 셰익스피어 전집을 색인한 결과는 아래 그림에서 간단히 확인해볼 수 있다.
위 그림에서 행(row)은 단어(term)을 의미하고 열(column)은 문서(document)를 의미한다. 행렬로 보았을때 행렬(i, j)의 값은 문서j에 단어i가 포함되면 1, 아니면 0이다.
이 결과를 토대로 질의문[Brutus AND Caesar AND NOT Calpurnia]을 처리하게 되면 아래와 같은 결과를 얻을 수 있다.
110100 AND 110111 AND 101111 = 100100
Calpurnia의 값은 010000 이지만 NOT 이기 때문에 101111이 된다. 따라서 Brutus와 Caesar를 포함하면서 Calpurnia를 포함하지 않는 작품은 'Anthony and Cleopatra'와 'Hamlet'이 되게 된다. 이와 같은 방법으로 검색을 하는 것을 불리언 검색 모델(Boolean retrieval model)이라고 한다. 불리언 모델은 AND, OR, NOT과 같은 불리언 식으로 표현된 어떤 질의문도 처리할 수 있다.
그러나 이런 매트릭스를 이용한 불리언 모델은 문서 및 문서에 포함된 단어의 수가 많아지면 많아질 수록 매트릭스를 구성하는데 많은 자원을 소모하게 되는 문제점이 있다. 문서가 백만개(1,000,000)가 있다고 가정하자. 각 문서가 천개(1,000)의 단어를 가지고 있고, 각 단어가 평균 6바이트를 필요로 한다고 가정하자. 이렇게 되었을 때 매트릭스를 구성하기 위해 필요한 자원의 양은 무려 6기가바이트에 달한다. 일반적으로 하나의 문서는 약 50만개(500,000)의 중복되지 않는 단어를 가지고 있으므로 이것을 반영했을 때의 크기는 약 오백억의 용량이 필요하므로 매트릭스를 구성할 수가 없게 된다.
불리언 모델보다 더 나은 방법 중 하나는 단어가 발생한 문서의 위치를 기록하는 것으로 이 방법을 역색인(Inverted index)라고 한다. 색인 데이터에는 항상 단어가 발생한 문서의 위치가 연결되어 있다. 아래 그림에 그 간단한 예가 보여진다.
사전(Dictionary)은 색인어들의 집합을 가리킨다. 포스팅(Posting)은 단어가 발생된 문서에 아이디(document ID)를 부여해서 문서를 가리키는 하나의 아이템을 이야기하며, 포스팅 리스트(Posting list)는 각 색인어에 연결된 포스팅(Posting) 데이터들을 가리킨다. 모든 포스팅 리스트(Posting list)를 통틀어서 Postings라고 한다. 이때 문서에 부여된 아이디는 유일한 값이다.
역색인(Inverted index)를 만들어봅시다.(A first take at building an inverted index)
역색인 정보를 만드는 과정을 간단히 살펴보면 아래와 같다.
1. 색인할 문서를 수집.
[Friends, Romans, countrymen.] [So let it be with Caesar] ...
2. 문서의 텍스트를 토큰으로 나누어서 각 문서를 토큰들의 리스트로 재구성한다.
[Friends] [Romans] [countrymen] [So] ...
3. 언어적 전처리를 통해 각 토큰을 일반화(normalization)한다.
[friend] [roman] [countryman] [so]
4. 각 토큰이 발생된 문서에 대한 정보를 색인하며, 이를 통해 사전(dictionary)와 postings로 구성된 역색인 정보가 생성된다.
[friend] - [1][2][4]...
[roman] - [2][31][54]...
위 과정은 그림 1.4, 1.5를 통해서 쉽게 설명할 수 있다.
그림 1.4의 가장 왼쪽에 있는 리스트는 Doc1과 Doc2에서 발견된 단어들의 리스트이며, 현재 문서에 따라 분류가 되어 있다. 이 리스트를 단어에 따라 오름차순 정렬을 하게 되면 그림 1.4의 가운데 리스트가 생성된다. 가운데 리스트를 자세히 살펴보면 각 단어들이 대상 문서에서 1번이상 발생되는 것을 확인할 수 있다.(예: killed는 Doc1에서 2번, caesar는 Doc2에서 2번 발생.) 이 발생 빈도수를 계산해서 리스트를 재구성하게 되면 그림 1.4의 가장 오른쪽에 있는 리스트가 생성되게 된다.
그림 1.5의 왼쪽 리스트는 그림 1.4에서 마지막으로 생성했던 리스트이며, 이 리스트를 바탕으로 역색인 정보를 구성한 것이 그림 1.5의 오른쪽 리스트이다. 사전(dictionary)의 단어 뒤쪽에 표시된 숫자는 현재 단어가 포스팅 리스트(Posting list)에서 총 발생한 빈도수를 나타낸다.
그림 1.5에서 보여지듯이 사전(dictionary)의 단어는 같은 단어별로 그룹화되어 있고, postings는 docID에 의해서 정렬이 되어 있다. 일반적으로 문서내의 단어의 발생 빈도수가 한번 이상이기 때문에, 색인에 필요한 저장 용량(storage requirements)이 줄어들게 되며, 검색을 효과적으로 할 수 있게 한다.
역색인 정보는 사전(dictionary)과 postings를 둘 다 저장해야 하는데, postings의 크기가 일반적으로 사전(dictionary)에 비해 훨씬 크기 때문에 postings는 디스크에 저장을 하고, 사전(dictionary)는 메모리에 저장을 한다. 때문에 각각이 차지하는 크기가 매우 중요하게 된다. posings 데이터가 디스크에 저장될 때는 각 포스팅(posting) 데이터를 가리키는 포인터가 없이 가장 첫 포스팅(posting) 데이터를 가리키는 포인터 뒤로 연속적으로 데이터가 저장되게 되는데, 이것은 포스팅(posting) 데이터가 차지하는 디스크의 용량을 줄이고, 포스팅(posting) 데이터를 메모리에 올리기 위한 디스크 seeking 빈도를 줄이기 위해서이다.
역색인 데이터의 불리언 질의 연산 (Processing Boolean queries)
위 그림 1.3에 보여지는 역색인 정보에서 [Brutus AND Calpurnia]라는 불리언 질의를 어떻게 처리할 지 간단히 정리해보면 아래와 같다.
1. 사전에서 Brutus를 찾는다.
2. Brutus의 포스팅 리스트를 가져온다.
3. 사전에서 Calpurnia를 찾는다.
4. Calpurnia의 포스팅 리스트를 가져온다.
5. 두 포스팅 리스트를 아래 그림 1.6에서 보여지는 것처럼 병합(Merge)한다.
두 단어를 모두 포함하는 검색 결과를 빠르게 가져오기 위해서는 병합 처리(Merging operation)의 속도가 빨라야 한다. 일반적으로 두 포스팅 리스트의 포인터를 유지하면서 각 포스팅 리스트를 차례대로 비교해 나가는 방법이 쓰이며, 아래의 알고리즘으로 표현할 수 있다. 이 알고리즘의 복잡도는 두 포스팅 리스트의 길이에 영향을 받기 때문에 O(x+y)가 되며, 포스팅 리스트는 반드시 정렬된 상태여야 한다.
MERGE(p, q)
1 answer 1) EMENT -> ]
이 규칙을 적용하게 되면, [replacement]는 [replac], [cement]는 [cement]가 된다. 이외에도 다양한 stemmer가 존재하며 다들 비슷한 결과를 보여주고 있다.
stemmer 대신에 lemmatizer(단어의 형태학상의 분석과 사전을 이용하여 자연언어 처리를 수행하는...)를 사용하여, 각 단어의 정확한 표제어를 찾을 수도 있다. lemmatizer를 사용하게 되면 검색의 질이 높아지는 이점이 있지만, 시스템의 성능을 저하시킬 수도 있는 단점이 있다.
역색인 데이터 구성(Postings lists, revisited)
지금까지 역색인 데이터를 구성하기 전단계를 자세히 살펴보면서 고려해야할 쟁점들에 대해 알아보았다. 다음에는 구성된 역색인 데이터를 빠르게 병합할 수 있는 방법 및 확장 포스팅 리스트에 대해서 알아보도록 하자.
빠른 포스팅 데이터 병합 : 스킵 포인터(Faster postings merges: Skip pointers)
말이나 글보다는 그림을 보는게 훨씬 이해하는게 쉽다. 아래 그림을 보도록 하자!
일단 우리가 [8]을 찾았다고 가정해보자. 병합 알고리즘에 의해 두 포스팅 리스트의 포인터는 [16]과 [41]을 가리키게 된다. 두 포인터의 값 중 위쪽 리스트의 [16]이 더 작으므로, 위쪽 리스트의 포인터를 이동을 시켜야 하는데 이때, [16]에 스킵 포인터가 걸려있다. [16]의 바로 다음 포인터 [19]와 아래쪽 리스트의 [41]을 비교하기 전에 먼저 스킵포인터의 [28]과 비교를 한다. 이때 [28]이 [41]보다 작으므로 포스팅 리스트의 포인터가 이동을 하게 된다. 즉, 스킵포인터의 [28]을 [19], [23]보다 먼저 비교함으로써 각 포스팅 데이터의 비교 횟수가 줄어들어 성능을 향상시킬 수 있게 된다.
여기서 스킵포인터를 얼마나 많이 두는가에 대한 논란이 있을 수 있는데, 스킵 포인터가 많으면, 스킵되는 구간이 짧아져서 결국 많은 비교를 수행해야 하고, 스킵 포인터가 적으면, 스킵되는 구간이 많아져서 비교가 제대로 이루어지지 않아서 정확도가 약간 떨어질 수 있다. 일반적으로 스킵포인트의 수는 전체 포스팅 리스트의 길이를 P라고 정의했을 때, √P 만큼의 스킵포인트를 유지하는 것이 좋다고 한다.
그리고 스킵포인터는 포스팅 리스트가 고정되어 있을 수록 업데이트되는 데이터가 많지 않아 쉽게 설정할 수 있는 반면에, 업데이트가 빈번하게 일어나면 업데이트가 일어날 때마다 스킵포인터를 재성해야하는 문제가 있다.
관용구 질의문(Pharase queries)
웬 생뚱맞은 관용구 질의문이라고 생각할 수도 있겠지만 이건 나중에 다룰 확장 역색인 데이터 구성을 설명하기 위한 포석이라고 보면 된다. 일반적으로 사용자가 "stanford university"와 같은 관용구로 검색을 했을 때, "I went to university at Stanford."도 검색이 되기를 원할 수도 있다. 이런 처리를 하기 위한 가장 간단한 방법은 Biword index를 사용하는 것이다.
Biword index는 인접한 두 단어를 하나로 묶어서 색인하는 방법이다. 예를 들어 ["Friends, Romans, Countrymen"]의 경우는 [friends romans], [romans countrymen]가 되며, 각 biwords는 사전의 색인어가 된다.
Biword 검색의 경우 관용구가 4문구를 넘어가면 문서에 전체 질의문의 단어가 포함되어 있는지 아닌지를 검증할 수 있는 방법이 없다. 문서를 직접 보기전에는 [friends romans]의 포스팅 리스트의 문서 중에 [countrymen]이 같이 포함이 되어 있는지 아닌지를 확인할 수 없다는 문제점(이외에도 몇개 더 있다. 나중에..ㅡ.ㅡ)이 있다.
Biword를 확장해서 각 색인어에 태그를 붙인 다음 biword를 구성하는 Extended biwords도 있다. 이 방법은 각 색인어에 대해 POST(part-of-speech-tagging)를 적용시켜 적절한 태그를 붙이는 방법이다. 아래 그림을 보면 어떤 방식으로 태그를 설정하는지 알 수 있다.
extended biword는 NX*N으로 구성이 되도록 묶음 단위를 설정한다. 예를 들면, [tangerine trees and marmalade skies]를 biword로 구성을 하게 되면 [tangerine trees AND trees and marmalade AND marmalade skies]가 되는 것이다.
그러나 biword를 통한 색인은 몇가지 문제점을 가지고 있다.
* False positives : 이 문제에 대해서는 윗 부분에서 설명했다.
* Index blowup : biword를 사용하게 되면 사전과 포스팅 데이터의 크기가 너무 커져버린다.
* No natural treatment of individual terms : 색인을 biword로 구성을 했기 때문에 단일 색인어에 대한 검색을 할 수가 없다.
이런 이유로 일반적으로 biword index를 사용하지 않는다. 이 대신에 Positional index를 주료 사용하게 된다. Positional index는 포스팅 데이터에 색인어가 발생한 문서뿐만 아니라 각 문서에서 발생한 위치 정보까지 같이 저장을 하는 방법을 이야기한다. 아래에 그 간단한 예를 보여준다.
to: 993427; 2:5[1,17,74,222,551]; 4:5[8,16,190,429,433]; 7:3[13,23,191]; . . .
be: 178239; 1:2[17,19]; 4:5[17,191,291,430,434]; 5:3[14,19,101]; . . .
질의문 [to be or not to be]를 처리하는 예를 통해서 그 사용방법을 알아보자. 우선 각 단어 [to, be, or, not]의 역색인 데이터를 가져오도록 하자. 그리고 각 포스팅 리스트의 길이를 비교한 다음 병합을 수행하도록 하자. 병합을 하는 과정에서 각 포스팅 데이터의 위치 정보를 이용하도록 하자. 우선 각 단어를 모두 포함하고 있는 문서를 찾자. 그리고 [to]가 발생한 위치보다 [be]가 발생한 위치가 1이 더 많은 위치 정보의 리스트를 찾는다. 이 과정을 나머지 단어에 대해서도 동일하게 반복을 한다. 아래에 그 결과를 간단히 보여준다.
to: . . . ; 4:. . . ,429,433; . . .
be: . . . ; 4:. . . ,430,434; . . .
Positional index가 효과적인 검색이긴 하지만 포스팅 데이터의 크기가 비약적으로 커짐으로써 저장 용량을 많이 소모한다는 단점이 있다. 하지만 대부분의 사용자들이 질의문을 관용구로 작성하고, 그런 경우 Positional index가 효율적으로 사용되어지기 때문에 검색 시스템에 기본으로 사용되어 지고 있다.
그럼 Positional index의 크기가 얼마나 될지 한번 계산해보자. 위치 정보 리스트는 단어가 발생한 문서 단위로 저장이 되는 것이 아닌 단어가 발생한 각각의 위치를 저장하기 때문에 색인 데이터의 크기는 문서의 평균 크기에 영향을 받게 된다. 웹 페이지는 평균 1,000개 이하의 단어를 가지는 반면에, 책이나 시집은 평균 100,000개 이하의 단어를 가진다. 단어가 1,000개의 문서에서 평균적으로 1번 발생한다고 생각해보자. 그때의 포스팅 데이터의 크기는 아래와 같이 나타난다.
일반적으로 positional index는 non-positional index보다 2배에서 4배까지 더 큰 저장용량을 필요로하고, positional index는 원본 문서의 약 35~50%정도의 크기를 자치하게 된다.
Combination schemes
일반적인 사용자가 입력하는 대부분의 질의문은 [Michael Jackson]이나 [Britney Spears]와 같은 특정한 관용구가 많다. 이런 질의문에 대해서는 Positional index를 사용하는게 비효율적이다. 따라서 특정한 관용구 질의에 대해서는 biword index를, 그 이외의 경우에는 positional index를 혼용해서 사용하는 것이 좋다. Willams et al. (2004)에 따르면(아마 사람인듯.. 이 사람이 논문을 쓴듯하다..), 두 색인 방법을 혼용해서 사용하게 되면 positional index를 하나만 사용했을 때 보다 전체 디스크 용량을 26% 더 소비하게 되지만, 검색 속도는 25%가 향상되게 된다.
|
