정보검색론 제 12장. 유사도 계산

숭실대학교 정보검색연구실 - 정보검색론(2003) 이준호 교수님 교제를 메모하기 위한 글입니다.

제 12장. 유사도 계산

정보 검색 시스템의 중요한 기능들 중 하나는 

문서와 질의 사의의 관련 정도를 나타내는 유사도를 계산하고

계산된 유사도에 따라 문서에 순위를 부여하는 것이다.

각각의 문서 벡터와 질의 벡터의 내적으로 유사도를 계산하고, 이러한 유사도에 따라 문서에 우선순위를 부여한다면 질의 처리 시간은 정보 검색 시스템에 입력된 문서들의 수와 비례한다. 문서의 수가 증가할 수록 느려진다는 문제점이 발생하는 것이다.

이러한 문제점을 개선하기 위하여 렉시콘 파일과 포스팅 파일로 구성되는 역파일을 이용하여 질의와 문서 사이의 유사도를 계산하는 방법들이 개발되었으며 이러한 방법들에 대해서 알아 보겠다.

 

12.1 기본적 누산기 방법

누산기는 유사도를 저장하는 저장 공간, 즉 변수를 의미. 

각각의 문서에 대하여 1개의 누산기가 할당된다.

1. 누산기 생성 :

문서 집합에 포함된 각각의 문서 d에 대하여 누산기 Ad를 생성하고, 그 값을 0으로 초기화

2. 유사도 계산 :

질의에 포함된 각각의 검색어(t, wqt)에 대해 다음을 수행

2.1 역파일로부터 검색어 t에 대한 포스팅 리스트 읽음

2.2 포스팅 리스트에 포함된 각각의 포스팅 (d, wdt)에 대하여, 검색어 t와 d사이의 부분 유사도 wqt x wdt 를 계산하여 이를 문서 d의 누산기에 합산

Ad<=Ad + wqt x wdt

3. 검색 결과 생성 :

문서들은 누산기 값에 따라 정렬한 후, 사용자가 원하는 수만큼의 상위 문서들을 검색 결과로서 반환한다.

기본적 누산기 방법은 문서 집합에 포함된 각각의 문서에 대하여 1개의 누산기를 할당하기 때문에, 누산기로 인하여 소비되는 메모리의 양은 문서 집합에 포함된 문서들의 수에 비례한다.

유사도 계산 과정 중 누산기 생성 방법은 유사도 계산 과정 중에 필요에따라 누산기를 생성하고 초기화함으로써 불필요한 누산기의 할당으로 인한 메모리의 낭비를 줄일 수 있다.

위 두가지 유사도 계산 방법들은 누산기에 부분 유사도를 합산하기에 앞서 메모리 내에서 누산기의 위치를 발견해야 한다.

기본적 누산기 방법에서 누산기들은 배열로서 구현되기 때문에 빠르게 발견할 수 있다.

유사도 계산 과정 중 누산기 생성 방법에서 문서 번호와 유사도 필드들로 구성된 누산기는 해싱 또는 AVL 트리 등을 이용하여 관리되기 때문에, 기본적 누산기 방법보다 누산기의 위치 발견에 많은 시간이 소비된다.

따라서 메모리가 충분하다면 기본 누산기 방법을 사용해야 한다.

12.2 검색 결과 생성 단계의 구현

기본적 누산기 방법의 마지막 단계는 누산기 값에 따라 문서들을 정렬한 후 사용자가 원하는 수 만큼의 상위 문서들을 검색 결과로서 반환한다.

OS에서 제공하는 qsort는 데이터의 비교함수에 대한 포인터를 요구하여 정렬 속도의 감소가 초래 되므로 직접 구현하는 것이 바람직하다.

유사도 계산이 종료된 이후에 문서 집합에 포함된 모든 문서들을 정렬하는 대신에, 사용자에 의해 지정된 수만큼의 상위 문서들을 추출하고, 추출된 문서들만을 정렬함으로써 검색 결과 생성에 소비되는 시간을 단축시킬 수 있다.

r이 N 보다 매우 작은 숫자일 경우, N개의 값들로부터 r개의 상위 값들을 추출하는 문제는 r-선택이라 불리운다. 이 문제는 힙 자료 구조를 이용하여 해결될 수 있다.