역색인

역색인(Inverted Index, 역 인덱스, 전치 색인)은 문서마다 들어 있는 단어를 적는 대신, 단어마다 그 단어가 나오는 문서의 목록을 적어 두는 색인 구조이다.

개요

문서는 본래 "문서 → 단어들"의 관계를 가진다. 이 관계를 그대로 두면 어떤 단어가 든 문서를 찾을 때 모든 문서를 훑어야 한다. 역색인은 관계를 뒤집어 "단어 → 문서들"로 저장한다. 그래서 질의어가 주어지면 그 단어의 목록만 꺼내 보면 된다. Apache Lucene 문서는 자신의 용어 색인을 이 계열로 설명하며, 문서가 용어를 나열하는 자연스러운 관계를 뒤집었기 때문에 역(inverted)이라는 이름이 붙었다고 적는다. 웹 검색엔진, 엘라스틱서치 같은 전문 검색 엔진, 데이터베이스의 전문(full-text) 인덱스가 모두 역색인을 쓴다.

구조

• 사전(dictionary, 용어 사전) - 색인된 모든 단어(용어)의 정렬된 목록이다. 단어마다 문서 빈도 같은 통계를 함께 둔다.
• 포스팅 목록(posting list) - 단어마다 그 단어가 나오는 문서 번호를 오름차순으로 늘어놓은 목록이다. 문서 안의 출현 횟수(TF)나 위치를 함께 저장하면 순위 계산과 구문 검색에 쓸 수 있다.

단어	포스팅 목록(문서 번호)
감리	1, 4, 7
데이터	2, 4
보안	1, 2, 7, 9

"감리 AND 보안" 은 두 목록의 교집합(1, 7), OR 는 합집합으로 구한다. 목록이 정렬되어 있어 두 목록을 한 번씩만 훑으며 병합할 수 있다.

만드는 과정

문서를 토큰으로 나누고(토큰화), 대소문자·어형을 정리한 뒤, (단어, 문서 번호) 쌍을 모두 모아 단어 순으로 정렬하고 같은 단어끼리 묶어 문서 번호 목록으로 만든다.

이 과정은 맵리듀스로 그대로 옮길 수 있다. 구글의 맵리듀스 논문은 역색인을 대표 예로 들며, Map 함수가 문서를 파싱해 (단어, 문서번호) 쌍을 내보내고, Reduce 함수가 한 단어의 쌍을 모두 받아 문서번호로 정렬한 뒤 (단어, 문서번호 리스트) 쌍을 내보내면 그 출력 전체가 역색인이 된다고 설명한다. 단어 위치까지 다루도록 쉽게 확장할 수 있다.

맵리듀스의 다른 예와 구별하기

같은 논문이 든 예들은 Map 출력의 키와 값, Reduce 가 하는 일로 구별된다.

기능	Map 출력	Reduce 출력
역색인	(단어, 문서번호)	(단어, 정렬된 문서번호 리스트)
단어 빈도수(word count)	(단어, 1)	(단어, 합계)
분산 grep	패턴에 맞는 줄	받은 것을 그대로 출력(항등 함수)
역방향 웹 링크 그래프	(대상 URL, 출발 URL)	(대상 URL, 출발 URL 리스트)
URL 접근 빈도	(URL, 1)	(URL, 합계)

역색인과 역방향 링크 그래프는 둘 다 "키별 리스트"를 만들지만, 키가 단어냐 링크 대상 URL 이냐가 다르다. 단어 빈도수는 리스트가 아니라 개수를 낸다.

순방향 색인과 구별하기

구분	순방향 색인(forward index)	역색인
키	문서	단어
값	문서에 든 단어 목록	단어가 든 문서 목록
잘하는 일	문서 하나의 내용 보기	단어로 문서 찾기

같이 보기

• 맵리듀스
• 검색엔진
• 정보 검색
• BM25
• 엘라스틱서치