메모智 유머사진 환영합니다, 손님!    메모지 | 회원가입 | 로그인
검색도움말 메모지 검색
  재미 • 메모智.COM 설치   •   메모智 홈   •   바깥고리   •   전체 메모智 목록   •   회원가입   •   로그인   •   도움말   •  
 
Introduction to Information Retrieval
메모智 -> 정보검색;
Introduction to Information Retrieval
http://www-csli.stanford.edu/~schuetze/information-retrieval-book.html
1
작성자: fireguy 추천수: 0 첨부파일: 0 등록일: 공개 바깥고리
이 메모智에 달린 꼬리표 #1 # #2#54#hfireguy #
2 #54 #정보검색 #
2 #54 #Introduction to Information Retrieval #
2 #54 #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 <- <> # 2 while p != NIL and q != NIL # 3 do if docID[p] = docID[q] # 4 then ADD(answer, docID[p]) # 5 else if docID[p] < docID[q] # 6 then p<-next[p] # 7 else q<-next[q] # 8 return answer # 위 알고리즘을 질의 [Brutus AND Calpurnia AND Caesar]에 적용시켜보자. 포스팅 데이터는 그림 1.3의 것을 사용하도록 한다. #위 알고리즘은 두 개의 포스팅 리스트를 받아서 처리하도록 되어 있기 때문에 먼저 두 단어의 포스팅 리스트를 병합 처리하고, 그 결과로 나온 포스팅 리스트와 남은 단어의 포스팅 리스트를 다시 병합처리하도록 해야한다. 위 알고리즘의 실행 속도는 비교 대상이 되는 포스팅 리스트의 길이에 달려있다. 즉, 길이가 짧으면 짧을 수록 병합 속도가 빠르게 된다. # 따라서 질의 [Brutus AND Calpurnia AND Caesar]는 [ (Calpurnia AND Brutus) AND Caesar ]과 같이 처리가 되게 된다. #2장. The dictionary and postings lists # 이번 챕터에서는 역색인 데이터를 구성하기까지의 과정을 살펴보면서 각 과정에서 생각해보아야 할 몇가지 주제에 대해서 이야기하고 있다. 이전 챕터에서 이야기 했었던 역색인 데이터를 구성하는 과정을 잠시 다시 살펴보자. # 1. 색인할 문서들을 수집한다. # 2. 문서의 텍스트 데이터를 토큰으로 분리한다. # 3. 각 토큰들을 언어적 처리를 하여 색인어로 추출한다. # 4. 색인어를 가지고 역색인 데이터를 구성한다. # 이 챕터에서는 각 과정을 살펴보면서 유의해야 할 몇가지 주제에 대해 논의하며, 챕터의 후반부에는 병합을 빨리 처리할 수 있는 포스팅 리스트의 구조와 phrase and proximity query를 처리하기 위한 확장 포스팅 리스트 구조에 대해 설명한다.(개인적으로 챕터 후반부만 봐도 이 챕터는 다 봤다고 생각한다...ㅡ.ㅡ;) #문서에 대한 정의(Document delineation and character sequence decoding) # 디지털 시스템에서의 문서란 파일과 같은 일정한 바이트의 연속이라고 할 수 있다. 색인을 하기 위해 가장 먼저해야할 일은 바로 이 연속된 바이트를 연속된 문자열로 변환하는 것이다. 이럴 때 고려해야할 사항은 문서가 어떤 문서인가 하는 것이다. 문서의 인코딩 타입이 UTF-8인지, 문서가 PDF형식 인지, html형식인지, 문서의 언어(한국어, 중국어, 영어 등..)는 무엇인지, 문서가 하나 이상의 언어로 작성되어 있는지, 등등 이런 것들을 모두 고려해야 문서를 제대로 읽어들여서 색인에 사용할 수 있게 된다. # 위 내용이 고려가 되었다면 문서의 단위는 어떻게 되는 것인지도 생각해 보아야 한다. 하나의 파일, 하나의 메일 내용이나 메일에 첨가된 내용, 아니면 다양한 형식의 문서들의 집합, 등등 문서의 단위를 정할때는 다양한 경우에 대해 고려해봐야 한다. #문서의 텍스트를 토큰으로 분리(Tokenization) # 색인할 문서를 정의하고 나면 다음에는 문서의 텍스트 데이터를 토큰 단위로 분리하는 처리를 해야한다. 토큰은 일반적으로 용어(term)나 단어(word)를 가리킨다. 문서로부터 분리된 토큰은 token/type으로 만들어진다.(이건 해석이 영...ㅡ.ㅡ;;) token은 특정한 문서 내의 연속된 문자열이고, type은 동일한 연속된 문자열을 가지는 토큰들을 모아서 분류해 놓은 것이다. tokenization의 간단한 예를 보여준다. # Input : Friends, Romans, Countrymen, lend me your ears; # Output : [Friends] [Romans] [Countrymen] [lend] [me] [your] [ears] # 토큰이 추출되었다고해서 모든 토큰이 색인이 될 수 있는 것은 아니다. 색인에 유효한 토큰이 되기 위해서는 고려해야할 사항들이 많이 있다. 여기서는 아래와 같은 주제를 가지고 토큰을 어떻게 처리할 것인가에 이야기 해보도록 하겠다. 뭐 결국 이야기 하고자 하는 내용은 색인어를 추출할 때, 그리고 질의문으로부터 질의어를 추출할 때 동일한 언어처리기를 사용하면 정책적으로 버려지는 몇몇 색인어 및 질의어를 제외하면 색인어와 질의어가 정확히 일치하기 때문에 검색이 잘 될 수 있다는 것이다.(이게 맞나..ㅡ.ㅡ? 아마 맞을거다..ㅎㅎ) # 1. 생략부호(Apostrophe, [']) # 2. 하이픈 기호와 공백(Hyphens and whitespace, [-][ ]) # 3. 숫자로 구성되어진 또는 숫자를 포함하는 토큰 # 4. 언어적 특성 # 4.1 복합어(Compounds) # 4.2 어절(Word segmentation) # 4.3 다중 언어로 구성된 토큰(Multiple alphabets) # 5. 불용어(stop words) #생략부호(Apostrophe, [']) # 다음의 문장을 보자. # [Mr. O'Neill thinks that the boys' stories about Chile's capital aren't amusing.] # 위 문장에서 O'Neill에 대해서 토큰으로 처리할 수 있는 경우에 대해 생각해보면 다음과 같은 형태의 토큰들을 생각해볼 수 있다. # [neill], [oneill], [o'neill], [o'] [neill], [o] [neill] # 위에서 보여지는 것처럼 토큰들이 구성이 되었을 때, [neill AND capital] 질의를 처리해보자. 이 경우는 실제 [neill] 문자가 다섯개의 토큰에 포함이 되어 있지만 정확히 일치하는 토큰은 3개 밖에 없다. [oneill AND capital]의 경우는 다섯개의 경우의 수 중, 단 1개밖에 일치하는 결과가 없게 된다. # 생략부호가 텍스트에 포함되었을 때 토큰으로 어떻게 분리하는가에 따라 검색 결과가 크게 달라지게 됨으로 생략부호가 포함된 텍스트를 처리할 때는 이점을 유의해야 한다. #하이픈 기호와 공백(Hyphens and whitespace, [-][ ]) # 영어에서는(경우에 따라서는 거의 모든 언어에서..) 하이픈 기호가 다양한 용도(단어 내에서 모음 사이의 분리[co-education], 이름을 지을 때 명사의 결합[Hewlett-Packard], 단어의 그룹화[the hold-him-back-and-drag-him-away maneuver], 등등..)로 사옹된다. 하이픈이 포함된 경우, 하나의 토큰으로 처리할 수도 있고, 하이픈을 앞뒤로 잘래내어서 두 개의 토큰으로 사용할 수도 있다. 그래서 하이픈이 포함된 경우를 자동으로 처리하기란 매우 복잡합 일이다. 가장 좋은 방법은 사용자가 질의문을 입력할 때 하이픈을 포함해서 넣게 하는 것이다. 질의문에 하이픈이 포함되어 있으면 우선 하나의 토큰으로 처리해서 검색을 하고, 그 다음 하이픈으로 구분자로 토큰을 다시 구성해서 검색을 할 수 있어서 거의 모든 경우의 수를 처리할 수 있기 때문이다. # 단순히 하이픈 만으로 구성된 토큰이라면 위와 같은 방법으로 어느 정도 처리가 가능하다. 여기에 공백이 같이 조합된 경우를 생각해보자. [San Francisco-Los Angeles]와 같은 경우를 생각해보자. 일반적으로 토큰을 구분하는 기본적인 단위를 공백이다. 그러나 공백만으로 토큰을 분리하게 되면, [San] [Francisco-Los] [Angeles]와 같이 토큰이 분리되어 전혀 의미를 알아볼 수 없는 토큰이 생성이 된다. # 따라서 하이픈이 포함되어 있는 텍스트 데이터를 처리할 때는 항상 공백과 함께 고려해야 한다. #숫자로 구성되어진 또는 숫자를 포함하는 토큰 # 날짜, 또는 아이피 주소, B-52와 같은 고유 명사처럼 토큰에 숫자가 포함되어 있는 경우를 생각해보자. 대부분 이런 토큰들은 색인을 하지 않고 버리는 토큰들이다. 왜냐하면 이런 데이터를 색인을 하게 되면 사전의 크기가 너무 방대해지기 때문이다. 그러나 이런 처리는 데이터베이스 에러 코드를 이용한 검색, [Lecture 3]과 같은 숫자가 포함된 질의를 처리할 수 없게 만드는 단점도 있다. 이런 문제점을 보완하기 위해 메타데이터(meta-data)로 분리해서 색인하는 방법을 쓰기도 한다. #언어적 특성 # 여기서는 세계 각국의 언어적 특성과 그에 따른 쟁점들에 대해 살펴본다. # 복합어(Compounds) # 각 단어가 결합되었을 때 독특한 형태를 띄는 언어들이 종종 있다. 프랑스어의 경우 단어의 시작이 모음인 단어 앞에 (정)관사가 결합될 경우 생략기호를 사용한 형태로 표시할 수 있다. 예를 들면, [un ensemble]은 모음 앞에 관사가 결합되어 있는 형태인데 이것은 [l'ensemble]로 표기될 수 있고, 동일한 의미를 가진다. 독일어의 경우는 복합명사를 그대로 이어써서 표기하는 특성을 가진다.(예: Computerlinguistik, Lebensversicherungsgesellschaftsangestellter) # 이런 경우에 생각해볼 수 있는 문제는 [l'ensemble]이 질의어로 들어왔을 때, [Computerlinguistik]가 질의어로 들어왔을 때, 복합어의 형태가 아닌 경우도 검색을 해줄 수 있어야한다는 것이다. 따라서 텍스트를 토큰으로 분리할 때, 이런 경우를 잘 생각해서 처리하도록 해야한다. # 어절(Word segmentation) # 어떤 언어의 경우 어절을 구분할 수 없는 언어들이 있다. 대표적으로 중국어와 일본어가 그런 형태를 가진다.(책에서는 한국어와 태국어도 포함하고 있는데, 태국어는 본인이 잘 몰라서 모르겠지만 한국어가 어절 구분이 없다니...ㅡ.ㅡ;;) 이런 경우는 각 토큰의 유일성을 보장할 수 없는 문제점이 있다. 그래서 이런 경우는 단어 기반의 색인을 하지 않고, 짧은 문장 단위로(character k-grams) 전부 색인해버리는 방법을 사용하기도 한다. # 다중 언어로 구성된 토큰(Multiple alphabets) # 중국어의 경우는 거의 모든 문자를 한자로 표기하기 때문에 그나마 문제가 간단한데, 일본어의 경우는 이보다 더 복잡하다. 일본어는 어절 구분이 없는데다가, 여러 언어(language)가 섞여 있기 때문에(히라가나, 카타카나, 간지체, 로마자, 등등..) 각 토큰이 어떤 언어로 구성되어 있는지, 그 토큰을 어떻게 처리할건지가 중요한 문제가 된다. #불용어(Stop words) # 간혹 매우 일반적이고 non-selective(해석이..ㅡ.ㅡ;)한 단어는 색인어 사전에서 제외가 되는데, 이런 단어들을 불용어라고 지칭한다. 이런 불용어들은 단어들을 빈도순으로 정렬을 한 다음 stop list에 불용어들이 등록되고, 색인 과정에서 버려지게 된다. 아래에 대표적인 불용어들을 보여주고 있다.(영어일 때...) # [a and as at be by for from has he in is it its of on s said that the to was will with year] # 불용어 리스트를 정의함으로써 색인 사전 및 포스팅 데이터의 크기를 상당히 줄일 수 있지만, 경우에 따라서는 불용어 처리를 함으로써 좋은 검색 결과를 보여주지 못할 수도 있다. 예를 들어, 관용구 질의(phrase query를 앞으로 "관용구 질의"라고 쓰겠다.)문 [President of the United States]의 경우를 보도록 하자. [President of the United States]의 경우 [of], [the]를 불용어 처리를 하게 되면 원래의 문장이 가리키는 의미인 "미합중국 대통령"의 의미가 사라지게 된다. 또 다른 예를 들면, [flights to London]에서 [to]를 불용어 처리를 하게 되면 원래 의미인 "런던까지의 비행"의 의미가 사라지게 된다. 이 외에도 노래제목("Let it be"), 유명한 시구("To be or not to be") 등의 경우도 마찬가지가 된다. # 현대의 검색 시스템들은 과거 200~300개에 달하던 불용어 리스트를 7~12개까지 줄여서 사용한다. 어떤 웹 검색 시스템은 불용어를 아예 사용하지 않으며, 어떤 검색 시스템들은 불용어를 어떻게 효율적으로 색인에 사용할 것인가를 연구하기도 한다.(챕터 5에서는 불용어들의 포스팅 데이터의 저장공간을 줄이기 위한 압축 방법에 대해서, 챕터 7에서는 불용어로 인해 발생할 수 있는 자원 소모에 빠지기 전에 어떻게 효과적으로 포스팅 리스트 탐색을 중단할지에 대해서 다룬다.) #토큰의 일반화(Normalization) # 텍스트로부터 토큰들이 추출된 후 각 토큰들을 일반화를 시킬 수도 있다. 예를 들면 [U.S.A] 토큰이 있을 때, 이 토큰을 일반화 하여 [USA]로 인식이 되도록 처리할 수도 있다는 것이다. 이렇게 되면 질의어가 [USA]가 들어오더라도 [U.S.A]도 같이 검색이 될 수 있는 장점이 있다. 이런 방법으로 하나의 이름으로 된 동일한 의미를 가지는 토큰의 집합을 만들 수 있는데, 이것을 Equivalence classes라고 한다. 즉, [U.S.A]와 [U.S.A.]는 [USA]로 매핑된다. 이 경우 하이픈이나 마침표 등을 제거하면 바로 해당 집합으로 매핑되는 이점이 있다. # 그러나 Equivalence classes는 반대의 경우로는 매핑하기 어렵다는 단점이 있다. [antidiscriminatory]는 [anti-discriminatory]로 매핑된다라는 것을 알기는 쉽지가 않다. 이런 문제의 대안으로 비대칭 확장(asymmetric expansion)이 있다. 이것의 예제는 아래에 보여진다. # Enter: window Search: window, windows # Enter: windows Search: Windows, windows # Enter: Windows Search: Windows # 이 방법의 경우는 Equivalence classes 보다는 토큰을 처리하는데 유연함을 가지지만 성능면에서는 그다지 좋지 않을 수 있다. # 토큰을 일반화 시키는게 항상 원하는 결과만을 가져다 주지는 않는다. [C.A.T.]를 위와 같이 일반화를 하게 되면 [CAT]가 되는데 이건 [cat]으로 인신되는 오류를 가져올 수 있다.(책에 의하면 실제로 구글이 이런 오류를 가지고 있다고 한다.) 따라서 토큰을 일반화 하는데 있을 수 있는 몇몇 문제들에 대해서 이야기해보도록 하자. # 강세와 발음부호(Accents and diacritics) # [resume]과 같은 단어는 강세 부호가 붙어서 [résumé]으로 표기될 수도 있다. [naive]도 [naïve]로 표기될 수 있다. 이런 경우 [resume]은 [résumé]과, [naive]는 [naïve]와 매칭될 수 있어야 한다. 사실 많은 언어에서 단어에 강세와 발음 부호를 붙여서 다른 소리를 내도록 구분을 하도록 하는 시스템을 가지고 있지만, 그 언어의 사용자들은 대게 부호를 생략해서 질의문을 입력한다. 따라서 사용자가 부호를 생략한 질의문을 입력을 하면 부호가 생략되지 않은 단어도 같이 검색해서 보여줄 수 있어야 한다. #Capitalization/case-folding # 일반적으로 토큰을 처리하는 방식은 모든 문자를 소문자로 처리하는 것이다. [automobile]로 검색해서 [Automobile]을 찾는다던지, [ferrari]로 검색해서 [Ferrari]를 찾는 것은 꽤 괜찮은 방법이라고 할 수 있다. 그러나 몇몇 특수한 경우(고유명사-[General Motors], 기관명-[the Fed vs. fed], 이름-[Bush])에 대해서는 이런 방식을 적용할 수 없다는 문제점이 있다. 뭐 간단한 대안으로는 모두 소문자로 처리하는 것이 아니라 일부 토큰들만 소문자로 처리하는 것이다. 일반적으로 대문자를 사용하는 경우는 문장의 가장 처음일 때, 제목일 때, 등이다. 뭐 대체적으로 사용자들이 소문자로 질의문을 넣기 때문에 모든 토큰을 소문자로 처리하는 것도 나쁘지는 않다. # 동의어와 동음이의어(Thesauri and soundex) # 몇몇 언어들을 보면 문자가 다르지만 뜻이 같은 단어, 발음은 같지만 뜻이 다른 단어들이 존재한다. 예를 들면, car와 automobile은 문자와 발음이 다르지만 뜻이 같다. 이런 경우 두 단어는 수작업으로 Equivalence classes 를 구성해야 한다. Equivalence classes 를 색인을 하게 되면 [automobile]을 포함하는 문서는 [car]의 포스팅 리스트에도 포함되고, [car]를 포함하는 문서도 [automobile]의 포스팅 리스트에 포함이 되게 된다. 포스팅 리스트가 이렇게 구성됨으로 질의어가 [car]가 들어와도, [automobile]이 들어와도 서로를 포함하고 있는 문서를 검색해서 보여줄 수 있게 된다. 뭐 포스팅 리스트와 사전을 더 많이 유지를 해야한다는 문제점은 존재하지만 토큰이 동일하지 않아도 리스트를 겹칠 수 있는 장점이 있다. # 일반화에서의 언어적 특성 # 토큰을 분리할 때도 언어적 특성에 따라 분리했지만, 분리된 토큰을 일반화할 때도 언어적 특성을 반영해서 처리해야한다. 프랑스어에서 [the]는 [le, la, l', les]와 같은 다양한 형태를 가지며, 일본어는 토큰을 분리했을 때 고려되었던 특성들을 일반화에도 그대로 고려해야 한다. # 이외의 쟁점들.. # 이외에도 미국과 영국이 [color]과 [colour]과 같이 철자를 다르게 사용하거나, 날짜가의 형식이 [3/12/91], [Mar. 12, 1991]과 같이 다양하다와 같은 주제들도 고려해보아야 한다. #언어적 전처리(Stemming and lemmatization) # 텍스트로부터 토큰을 분리하고 분리된 토큰을 일반화 시키는 작업까지 완료가 되면 각 토큰을 언어적 처리를 하여 색인어로 추출해 낸다. 이때 사용되는 방법이 stemming과 lemmatization이다. 이 언어처리의 목적은 단어의 어미변화와 파생형태를 가급적 줄여서 단어의 원형을 추출하는 것이다. 아래에 그 예를 보여준다. # [am, are, is => be] # [car, cars, car's, cars' => car] # [the boy's cars are different colors => the boy car be differ color] # stemming은 원하는 형태가 될때까지 단어의 끝을 제거해 나감으로써 단어의 원형을 찾는 방법이고, lemmatization은 단어의 형태학상의 분석과 사전을 이용해서 단어의 사전적인 기본 원형을 찾는 방법이다. # stemming 기법 중 가장 일반적인 것(영어를 stemming하는 알고리즘 중에서...) 중 하나는 Porter's algorithm이다. 이 알고리즘은 stemming을 위한 다섯 단계를 가지고 있으며, 각 단계를 차례대로 실행한다. 아래에 각 단계에서 정의하고 있는 규칙의 예를 보여준다. # 규칙의 컨셉은 단어의 길이를 측정하는 것으로, 단어가 규칙을 만족할만큼 충분한 길이인지 체크(loosely하게)한다. 규칙에 정의된 부분이 stemming의 결과로 잘려져 나가는 부분이 아니라, 접미사로 간주하기 때문이다.(솔직히 이부분은 뭔 소리를 하는지 이해가 잘..ㅡ.ㅡ;; 아래 예제가 이걸 설명하는 것 같은데 이해가 안된다...ㅈㅈ) 아래에 이 규칙에 대한 예제가 설명되어 있다. # [ (m>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%가 향상되게 된다. # #
2 #54 # #
2 #54 #1271140343 #
2 #54 # #
2 #54 # #
2 #54 # #
2 #54 #PUBLIC #
2 #54 # 정보검색 #
2 #54 #LINK #
2 #54 # #
2 #54 # # #STATUS:: SUCCESS
로그인후 꼬리표 입력가능 회원만 꼬리표 입력 가능합니다.

 

drupal hit counter

Site Stat
검색
Custom Search
모든 지식은 개인의 소유입니다.
그 외의 다른 내용은 Copyright © since 2010, 메모智.com이 가집니다.
메모지 • 사용시 주의사항 • 연락처 • powered by 크리스탈