[정보검색] 역색인파일(inverted index file) 정리

이 글은 정보검색에서 일반적으로 쓰이는 역색인 파일(inverted index file)에 대한 내용을 정리한 글입니다.

 

http://informationretrieval.org의 강의자료를 참고하여 작성하였습니다.

 

먼저 term-document incidence matrix라는 개념에 대하여 정리할 필요가 있다.

 

term-document incidence matrix

	doc1	doc2	doc3	doc4	doc5	doc6	......
apple	1	1	0	0	1	0
boy	1	1	0	1	0	0
cat	1	1	0	1	1	1
desk	0	1	0	1	0	0
eagle	1	0	1	0	1	1
......

위의 표는 term-document incidence matrix를 나타낸 것이다. 1행은 각각의 문서를 의미한다. doc는 용어(term)를 포함하고 있는 문서이다. 각 행의 1열에 있는 것이 term(용어)에 해당한다. 만약 문서가 특정 단어를 포함하고 있다면 1의 값을 가지며 포함하지 않는다면 0의 값을 갖는다. 예를 들어 doc1은 apple, boy, cat, eagle 등의 단어를 포함하고 있다. 또한 apple이라는 단어는 doc1, doc2, doc5 등의 문서에서 나타난다. 이와 같은 매트릭스 형식으로 문서와 용어의 관계를 나타낸 것이 바로 term-document incidence matrix이다. 

 

위의 matrix를 활용하면 문서(document)와 용어(term)를 query형식이나 수치 연산이 가능한 vector형식 등 다양하게 표현할 수 있다.

예) doc1 : 11101, doc2 : 11110 

     apple : 110010, boy : 110100 

 

하지만 문서의 수가 많아지거나 용어의 수가 상당히 큰 경우(일반적으로 문서는 약 500,000 이상의 term을 갖는다) term-document incidence matrix는 상당히 큰 메모리를 차지하며 이는 속도면에서도 매우 비효율 적이다. 따라서 이를 보완하기 위한 방법으로 Inverted Index라는 방법을 사용한다.

 

 

역색인(Inverted index)

dictionary	posting
apple	1	2	5	27	80	127	......
boy	1	2	4	11	23	92	.....
cat	1	2	4	5	6	12	.....
......

 

위의 표는 term-document incidence matrix를 역색인(inverted index)로 타나 낸 것이다. term-document incidence matrix 용어가 문서에 나타나지 않은 경우를 0으로 표현하고 메모리를 차지하는 반면 역색인파일은 문서가 용어를 포함하는경우(1의 값을 갖는)만을 리스트 형식으로 갖는다. inverted index에서 용어들을 모아 놓은 것을 dictionary, 해당 용어를 포함하는 문서들의 집합을 posting list라고 한다.

 

역색인 파일을 생성

역색인 파일을 생성하는 순서는 다음과 같다.

 

1. 토큰화 및 전처리

2. 포스팅 생성

3. 포스팅 정렬

4. 포스팅 리스트 생성 및 문서 빈도 계산

 

 

 

이상 역색인파일(inverted index file)에 대한 정리를 마칩니다.

 

질문 또는 이상한 점 있으면 댓글로 남겨주세요.

 

감사합니다.