[데이터 색인] 역색인 구조 (역 인덱스; Inverted Index)

 

안녕하세요. 개발개입니다.

 

이번 글에서는 검색엔진 분야에서 주목받고 있는 엘라스틱서치의

주요 특징 중 하나인 역색인 구조란 무엇인지에 대해 알아보겠습니다.

 

오타, 오류 혹은 기타 의견은 언제든지 환영합니다.

 

 

 

 

---

 

 

색인(Index)란?

문서에서 키워드를 찾아보기 쉽도록 정렬/나열한 목록을 말합니다.

일반적으로 책 뒷편에 색인, 인덱스, 찾아보기와 같은 이름으로 정돈된 목록을 말합니다.

 

 

역색인(Inverted Index)란?

키워드를 통해 문서를 찾아내는 방식을 말합니다.

책 뒷편의 색인된 키워드를 이용해 역으로 본문(혹은 문서)을 찾는 방식을 말합니다.

 

예를 들어,

리눅스를 사용하던 중 특정 파일을 찾고 싶어 명령어를 사용하려고 합니다. 그런데 which, whereis, find와 같은 명령어 중 무엇을 사용해야 할 지 모르겠어서 책에서 각 명령어에 대해 먼저 알아보려고 합니다. 이럴 때 우리는 보통 책 맨 뒤를 열어 색인(Index) 목록을 확인합니다.

찾아보기

…

find  ………………………… 105, 203

…

which …………………………… 203

whereis…………………………… 204

…

이를 통해 105, 203, 204 페이지를 확인하면 우리가 찾던 명령어에 대한 내용을 찾을 수 있는데 이를 역색인(Inverted Index)이라고 합니다.

 

 

역색인 구조 생성 과정

0. 다음과 같은 문서가 있다고 가정한다.

문서ID	문서 내용
doc1	null pointer exception
doc2	Exception cases
doc3	in some exception cases

1. 원문에서 색인어를 추출하고 분석기에 따라 소문자로 변환하기도 한다.
(소문자로 변환하지 않으면 exception과 Exception을 다른 단어로 인식)

문서ID	색인어
doc1	null, pointer, exception
doc2	exception, cases
doc3	in, some, exception, cases

2. 색인어수(문서빈도)를 카운트하고 정렬한다.

색인어	색인어수(문서빈도)
cases	2
exception	3
in	1
null	1
pointer	1
some	1

3. 색인어별 역색인 벡터를 만든다. (렉시콘파일 → 포스팅파일)

색인어	색인어수(문서빈도)		문서ID
cases	2	→	doc2, doc3
exception	3	→	doc1, doc2, doc3
in	1	→	doc3
null	1	→	doc1
pointer	1	→	doc1
some	1	→	doc3

 

 

 

역색인 구조의 이점

검색이 매우 빠릅니다.

 

예를 들어,

RDBMS에서 예문의 "pointer"라는 색인어가 포함 문서를 찾으려면 다음처럼 like 검색을 사용해야 합니다. 

SELECT doc_id
  FROM documnets
 WHERE doc_content LIKE '%pointer%';

심지어 해당하는 모든 문서를 찾으려면 모든 열(row)의 내용에 대해서 LIKE를 수행하기 때문에 데이터가 늘면 늘수록 속도가 현저히 떨어진다는 단점이 있습니다.

(해당 색인어를 찾기 위해 책을 처음부터 한 줄 한 줄 읽어가며 찾는 방식)

 

하지만 역색인 구조를 생성해 두면 키워드 색인을 통해 문서ID를 바로 찾을 수 있습니다.

(책 뒷편 인덱스 목록에서 찾아 바로 해당 페이지로 이동하는 방식)

 

 

---

 

 

본 글은 다음을 참고하여 작성되었습니다.

 

- 이준호, 정보검색론, 숭실대학교 정보검색연구실, p.102~109, 2003.9

- 권택환 외, 엘라스틱서치 실무가이드, 위키북스