검색엔진의 역색인(Inverted Index)의 원리

만약에 개발자들에게 "간단한 검색엔진(Search Engine)을 만들어보세요"라는 요청을 하면, 대부분은 "제가요?" "못합니다" 등으로 단호히 거절을 할 것이다. 검색엔진이라는 것은 구글이나 네이버, 다음같은 대기업만이 만들 수 있는 것이라고 생각하기 때문이다.

 

하지만, "간단한 검색엔진"이라는 요건은 개발자라면 누구나 쉽게 만들 수 있다. 물론 루씬(Lucene)이나 엘라스틱서치(Elastic Search), 솔라(Solar)같은 훌륭한 검색엔진들이 이미 즐비하니 굳이 만들 필요는 없지만 어디까지나 이 포스팅은 검색엔진의 원리를 설명하는 것을 목적으로 하니 위와 같은 솔루션들이 없다는 가정으로 생각을 해보자.

 

 

우리가 검색을 할 때 무엇을 넣을 것인가? 당연히 키워드(Keyword)를 넣는다. 네이버나 구글이나 입력창이 떡하니 있고 거기에 우리가 아무 말이나 넣으면 가장 유사한 문서를 찾아주는 것이 검색엔진이다. 여기서 간단한 검색엔진이라 함은 바로 이 "키워드"를 입력 했을 때 "문서"를 찾아주면 된다는 것이다.

 

1차적으로 개발자들은 이런식을 생각할 수 있다. 키워드와 현재 있는 문서의 내용을 모두 비교해서 문서를 가지고 오는 방법을 생각할 수 있을 것이다. 이런식의 방법은 문서의 양이 적을 경우 사용자는 느리다고 인지하지 못할 정도로 충분한 속도가 나올 수 있을 것이나. 문서가 몇만건이 넘어서는 순간부터는 속도도 속도이고, 컴퓨터는 몇번의 요청으로 뻗어버릴 수도 있을 것이다.

 

그러면 어떻게 해야 성능은 충분히 부합되는 간단한 검색엔진을 만들 수 있을까? 방법은 이 포스팅의 제목인 역색인(Inverted Index)에 달려 있다.

 

아래는 원본 데이터라고 가정을 해보자. 원본 데이터는 현재 메모리에 저장이 되어 있으며, Map 구조로 저장이 되어 있다는 가정을 가본다

 

원본데이터

key : 1

value : 자비스가 필요해의 본문 글입니다 역색인에 대해서 설명합니다.

 

key : 2

value : 자비스가 필요해, 검색엔진과 역색인의 원리

 

key : 3

value : 자비스가 필요해, 엘라스틱 서치와 루씬의 비교

 

위와 같이 원본 데이터가 3개가 있을 경우, 다음 프로세스는 형태소 분석을 수행한다. 그러면, 다음과 같이 value당 키워드들이 뽑힐 것이다(참고로, 형태소 분석은 엑소브레인의 형태소 분석 결과이다)

 

"자비스가 필요해의 본문 글입니다. 역색인에 대해서 설명합니다."의 형태소 분석 결과

 

"자비스가 필요해, 검색엔진과 역색인의 원리"의 형태소 분석 결과

 

"자비스가 필요해, 엘라스틱 서치와 루씬의 비교"의 형태소 분석 결과

 

위와 같이 3가지의 형태소 분석 결과가 있지만, 일반적으로 검색엔진은 불필요한 품사를 제외한 명사등만 추출하여 사용하기 때문에 3가지의 문장에서 명사만 추출하면 다음과 같이 형태소 분석이 뽑혀지게 된다.

 

자비스가 필요해의 본문 글입니다. 역색인에 대해서 설명합니다.

자비스,본문,글,역색인,설명

 

 

자비스가 필요해, 검색엔진과 역색인의 원리

자비스,필요,검색,엔진,역색인,원리

 

 

자비스가 필요해, 엘라스틱 서치와 루씬의 비교

자비스,필요,엘라,스틱,서치,루씬,비교

 

참고로, 검색엔진은 형태소 분석이 추출되지 않으면, 검색이 되지 않기 때문에 형태소 분석의 수준과 같은 설정 등을 사이트 및 클라이언트의 요구에 맞게 튜닝등을 해야 한다. 형태소 분석이 끝나면 검색엔진은 역색인 작업을 하게 되는데 그 결과는 다음과 같다.

 

키워드	문서번호
자비스	1,2,3
본문	1
글	1
역색인	1,2
설명	1
필요	2,3
검색	2
엔진	2
원리	2
엘라	3
스틱	3
서치	3
루씬	3
비교	3

 

위의 표를 보다시피 역색인은 키워드에 문서들의 Primary Key(혹은 주소, 파일명 등)와 같은 값등을 매핑하여 저장하는 기술이다. 역색인 작업을 하게 될때의 장점은 매우 빨리 찾을 수 있다는 것이다. 기존보다 추가적인 작업과 메모리가 필요하게 되지만, 검색은 매우 빠른 속도로 처리가 된다.

 

그리고, 키워드가 여러개 있어도 속도에 큰 영향을 주지 않게 되며 된다. 예를 들어 검색 키워드가 "자비스 역색인"이라고 입력 했을 경우 자비스에 속한 문서 번호 1,2,3을 갖고 오고, 역색인에 속한 문서 번호 1,2를 갖고 온 후, 교집합인 1,2를 출력해주면 되는 간단한 작업만 필요하다.

 

만약 위와 같이 키워드에 AND처리를 하는게 아니라 OR처리가 필요하다고 한다면, 다음과 같이 처리를 하면 된다.

 

1번 문서 2번

2번 문서 2번

3번 문서 1번

 

위와 같이 문서별 등장 빈도수를 책정 한 후, 빈도가 많은 순으로 정렬(여기선 1,2,3 순서)을 하면 된다. 개발자에게 위와 같이 구현하라고 하면 적어도 3년차 이상은 무리없이 구현할 수 있으며 이제 갓 들어온 신입 개발자라 하더라도 구글링을 하거나 책을 보면서 개발을 한다면 큰 무리 없이 다들 구현할 수 있을 것이다.

 

검색엔진은 위의 원리에서 크게 벗어나지 않으며. 여기에서 얼만큼 보다 효율적으로 구현을 하냐의 싸움이기 때문에 솔루션을 만드는 것은 다른 차원의 문제이지만, 보다 시피 간단한 검색엔진을 만드는 것은 요구사항에 따라서 하루만에도 만들 수 있는 간단한 알고리즘 집합이다.

 

참고자료

엑소브레인 텍스트 분석 API : http://aiopen.etri.re.kr/demo_nlu.php