개요
이전 포스팅에서, Elasticsearch의 'Full Text Search' 라는 것이 어떠한 관점에서 수행되는지 살펴 보았다.
몇개의 검색어로 자신이 찾고자 하는 정보를 정확하게 찾기는 매우 힘들겠지만, 사용자는 자신이 의도한 바와 '가까운' 검색결과를 얻기를 원한다. 이러한 정확도가 높을 수록 좋은 검색엔진인 것이다.
이러한 'Full Text Search'라는 맥락에서, Elasticsearch는 정보를 색인할때 'Inverted Index' 라는 구조를 생성한다. 이것이 무엇일까? 오늘은 이 'Inverted Index' 라는것이 무엇인지 살펴 보고자 한다.
Inverted Index
원문 - https://www.elastic.co/guide/en/elasticsearch/guide/master/inverted-index.html
이 개념을 이해하기는 쉽지 않았다. 인덱스면 인덱스지 'Inverted' 인덱스라..? 우리말로 억지로 해석하자면 '역인덱스' 정도가 되는건가? 아무튼 공식 가이드에 아주 친절하게 설명되어있다.
가령 2개의 document가 있고 'content'라는 field를 가지고 있다고 하자. 각 document의 content field에는 아래와같은 문장들이 각각 저장되어 있다.
1. The quick brown fox jumped over the lazy dog 2. Quick brown foxes leap over lazy dogs in summer이때 Elasticsearch는 Inverted Index를 생성하기 위해 각 문장의 단어(term 또는 token이라고도 한다)를 분리하고 정렬한 다음, 각 단어가 어느 document에 있는지 표시한다. 그렇게되면 아래와같은 표가 완성될 것이다.
Term Doc_1 Doc_2 ------------------------- Quick | | X The | X | brown | X | X dog | X | dogs | | X fox | X | foxes | | X in | | X jumped | X | lazy | X | X leap | | X over | X | X quick | X | summer | | X the | X | ------------------------자, 이제 'quick brown' 이라는 검색어를 입력하였다고 치자.
그러면 아래와 같은 매칭 리스트가 만들어질 것이다.
Term Doc_1 Doc_2 ------------------------- brown | X | X quick | X | ------------------------ Total | 2 | 1'brown'과 'quick' 이란 단어는 Doc_1에서 는 모두 검색이 되었고, Doc_2에서는 'brown'이라는 단어 하나만 검색이 되었다. 따라서 Doc_1이라는 문서가 우리가 의도했던 검색결과에 가장 가까운 문서가 될 것이다.
이것이 'Inverted Index'를 생성해 검색을 수행하는 기본적인 원리이다. 그렇지만 계속 드는 의문중 하나, 왜 'Inverted' 일까? 그냥 인덱스와 '역'인덱스는 무슨 차이가 있을까? 아래 URL을 참고하자.
http://www.quora.com/Information-Retrieval/What-is-inverted-index
정말 헷갈렸지만, 위 URL에서 말하고자 하는바를 간단히 요약하자면,
- 인덱스 = 책 앞부분의 목차
- 역인덱스 = 책 뒷부분의 색인
인 것 이다!! 왠만한 기술서적은 맨 뒷부분에 해당 단어가 어떤 페이지에 나와있는지를 list up 한 '색인' 이라는 페이지가 있다. 바로 이것이 '역'인덱스 인것이다. 예를 들어 아래사진과 같다!
한마디로 걍(?)인덱스는 페이지를 어떠한 topic에 매핑 시킨다. 하지만 '역'인덱스는 단어(term)를 페이지에 매핑 시키는것이다. 어떻게보면 서로 반대되는 개념이다. 그래서 '역'이라는 단어가 붙었나 보다.
책 전체 에서 어떠한 단어를 찾을때 책 첫장부터 한장씩 넘기는 멍청한짓을 하는 사람은 없을 것이다. 따라서 이러한 '역'인덱스는 단어를 통해서 문서를 찾는 Full Text Search 에 최적의 속도를 내는 방식이라고 할 수 있다.
하지만 위의 예제는 아래와 같은 몇가지 문제점이 있다.
- 'Quick'과 'quick'은 따로 리스트에 있지만 사실 같은 단어이다 (대소문자)
- 'fox'와 'foxes'는 매우 비슷한 단어이고, 'dog'와 'dogs'도 마찬가지다. (복수형)
- 'jumped'와 'leap'이라는 단어도 같은 의미이기에 'jumped'으로도 'leap' 매칭되어야 하는것이 아닌가? (동의어)
만약의 위의 역인덱스를 바탕으로 'Quick fox' 를 검색한다면 (두개의 단어가 AND 조건일때) 검색결과는 하나도 나타나지 않을 것이다.
Doc_1은 'quick fox' 가 포함되어있고 Doc_2는 'Quick foxes' 가 포함되어 있기때문이다. 따라서 어디에도 매칭되지 않는다.
이러한 문제를 해결하기 위해 Elasticsearch는 'Token Filter'라는 모듈을 제공하여 단어를 가공한다. 예를들어 아래와 같은 작업을 하는 것이다.
- 대문자로 시작하는 'Quick'은 lowercasing하여 'quick'으로 색인한다.
- 'foxes'와 'dogs'는 그 뿌리가 되는 단어인 'fox'와 'dog'으로 색인한다.
- 'jumped'와 'leap'은 동의어 이므로, 하나의 단어인 'jump'로 색인한다.
이러한 작업을 마치게되면 아래와같은 역인덱스가 완성된다.
Term Doc_1 Doc_2 ------------------------- brown | X | X dog | X | X fox | X | X in | | X jump | X | X lazy | X | X over | X | X quick | X | X summer | | X the | X | X ------------------------
이것이 Elasticsearch의 'Anaysis' 과정이다.
대략 두가지의 과정 즉, 단어의 분리와 가공의 과정을 거치는데 전자는 'Tokenizer', 후자는 'Token Filter'가 담당한다. 이러한 'Analysis'의 구체적인 과정은 다음 포스팅으로 미루겠다. 어짜피 나도 공신력(?) 있는 Elasticsearch 공식문서에서 거의 모든 정보를 얻고있다.
참고하자. https://www.elastic.co/guide/index.html
PS : 이러한 Inverted Index 원리는 비단 Elasticsearch에서만 사용되는것이 아니다. 그러므로 잘 알아두면 분명 좋을 것이라고 믿는(?)다.
댓글 없음:
댓글 쓰기