-
Elasticsearch Inverted Index 의 이해내가 공부하고 싶은 IT/지식정리 2022. 12. 25. 20:42
Elasticsearch는 Open Source Project인 Apache Lucene을 기반으로 만들어진 Search Engine 임
이 Apache Lucene에서의 Index는 Inverted Index를 사용하기 때문에, Elasticsearch도 그러함
Index 란
- Key-Value 구조를 가지는 테이블을 말한다.
Key Value 1 1번 2 2번 3 3번 4 4번 위와 같은 Key-Value 구조를 가지는 테이블은 HashMap 이라는 자료구조와도 관련이 있다, 특히 대용량 데이터에서 빠르게 데이터를 탐색할 때에 매우 유용한 자료구조로 알려져 있다.
Forward Index
보통 Index 라고 말하는 것은 forward index 를 의미한다. 어떠한 주어진 Document 들로 index를 생성하면 아래와 같이 된다. 즉 Document가 Key에 해당하고 Document에 존재하는 Word들이 Value에 해당한다.
Document Words Document1 apple, toy Document2 bit, box, toy Document3 tool,tag, fund, box Inverted Index (역색인)
위에 나온 forward index와는 달리, inverted index는 Word가 Key가 되고, 그 Word가 존재하는 Document들이 Value가 된다. 즉, 아래의 예시에서 처럼 toy라는 key로 검색해서 toy라는 단어가 있는 Document들을 찾을 수 있다.
Word Documents toy Document1, Document2 box Document2, Document3 fund Document3 예제로 설명
원본 데이터
key : 1 value : 자비스가 필요해의 본문 글입니다 역색인에 대해서 설명합니다. key : 2 value : 자비스가 필요해, 검색엔진과 역색인의 원리 key : 3 value : 자비스가 필요해, 엘라스틱 서치와 루씬의 비교형태소 분석 확인 (nori 형태소 분석기)
- “자비스가 필요해의 본문 글입니다 역색인에 대해서 설명합니다.” 형태소 분석 결과
GET /cn-place/_analyze?pretty { "analyzer": "korean_analyzer", "text": "자비스가 필요해의 본문 글입니다 역색인에 대해서 설명합니다." }{ "tokens" : [ { "token" : "자비스", "start_offset" : 0, "end_offset" : 3, "type" : "word", "position" : 0 }, { "token" : "필요", "start_offset" : 5, "end_offset" : 7, "type" : "word", "position" : 2 }, { "token" : "해", "start_offset" : 7, "end_offset" : 8, "type" : "word", "position" : 3 }, { "token" : "본문", "start_offset" : 10, "end_offset" : 12, "type" : "word", "position" : 5 }, { "token" : "글", "start_offset" : 13, "end_offset" : 14, "type" : "word", "position" : 6 }, { "token" : "역색인", "start_offset" : 18, "end_offset" : 21, "type" : "word", "position" : 9, "positionLength" : 2 }, { "token" : "역", "start_offset" : 18, "end_offset" : 19, "type" : "word", "position" : 9 }, { "token" : "색인", "start_offset" : 19, "end_offset" : 21, "type" : "word", "position" : 10 }, { "token" : "설명", "start_offset" : 27, "end_offset" : 29, "type" : "word", "position" : 14 } ] }- “자비스가 필요해, 검색엔진과 역색인의 원리” 형태소 분석 결과
GET /cn-place/_analyze?pretty { "analyzer": "korean_analyzer", "text": "자비스가 필요해, 검색엔진과 역색인의 원리" }{ "tokens" : [ { "token" : "자비스", "start_offset" : 0, "end_offset" : 3, "type" : "word", "position" : 0 }, { "token" : "필요", "start_offset" : 5, "end_offset" : 7, "type" : "word", "position" : 2 }, { "token" : "검색", "start_offset" : 10, "end_offset" : 12, "type" : "word", "position" : 5 }, { "token" : "엔진", "start_offset" : 12, "end_offset" : 14, "type" : "word", "position" : 6 }, { "token" : "역색인", "start_offset" : 16, "end_offset" : 19, "type" : "word", "position" : 8, "positionLength" : 2 }, { "token" : "역", "start_offset" : 16, "end_offset" : 17, "type" : "word", "position" : 8 }, { "token" : "색인", "start_offset" : 17, "end_offset" : 19, "type" : "word", "position" : 9 }, { "token" : "원리", "start_offset" : 21, "end_offset" : 23, "type" : "word", "position" : 11 } ] }- “자비스가 필요해, 엘라스틱 서치와 루씬의 비교” 형태소 분석 결과
GET /cn-place/_analyze?pretty { "analyzer": "korean_analyzer", "text": "자비스가 필요해, 엘라스틱 서치와 루씬의 비교" }{ "tokens" : [ { "token" : "자비스", "start_offset" : 0, "end_offset" : 3, "type" : "word", "position" : 0 }, { "token" : "필요", "start_offset" : 5, "end_offset" : 7, "type" : "word", "position" : 2 }, { "token" : "엘라스틱", "start_offset" : 10, "end_offset" : 14, "type" : "word", "position" : 5 }, { "token" : "서치", "start_offset" : 15, "end_offset" : 17, "type" : "word", "position" : 6 }, { "token" : "루씬", "start_offset" : 19, "end_offset" : 21, "type" : "word", "position" : 8 }, { "token" : "비교", "start_offset" : 23, "end_offset" : 25, "type" : "word", "position" : 10 } ] }3가지 문장의 형태소 분석으로 추출된 단어들
자비스가 필요해의 본문 글입니다. 역색인에 대해서 설명합니다. 자비스,필요,해,본문,글,역색인,역,색인,설명 자비스가 필요해, 검색엔진과 역색인의 원리 자비스,필요,검색,엔진,역색인,역,색인,원리 자비스가 필요해, 엘라스틱 서치와 루씬의 비교 자비스,필요,엘라,스틱,서치,루씬,비교형태소 분석이 끝나면 검색엔진은 역색인 작업을 하게 되는데 그 결과는 다음과 같다.
키워드 문서번호 자비스 1,2,3 필요 1,2,3 해 1 본문 1 글 1 역색인 1,2 역 1,2 색인 1,2 설명 1 검색 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 순서)을 하면 된다.
검색엔진은 위의 원리에서 크게 벗어나지 않으며. 여기에서 얼만큼 보다 효율적으로 구현을 하냐의 싸움이기 때문에 솔루션을 만드는 것은 다른 차원의 문제이지만, 보다 시피 간단한 검색엔진을 만드는 것은 요구사항에 따라서 하루만에도 만들 수 있는 간단한 알고리즘 집합이다.
Inverted indexing 이 되는 과정
용어정리
- Postings List
Indexing하는 과정에서 생성하게 되는 (Document별 Unique한 식별값인) Document ID들을 모은 List이다.
정렬은 Document ID별로 하여, List를 생성한다. - Vocabulary
각 Field별로 추출한 Term들의 집합 - Field
Term들을 묶은 집합 (Term들을 대표하는 개념이라기 보다는 document별로 공통으로 구분하는 데이터집합) - Term
Field에서 (tokenization에 의해) 추출한 word 또는 token - Doc Freq
해당 Term이 몇개의 Document에 존재하는가에 대한 빈도 - Term Freq
해당 Term이 각 Document내에 몇번 나타나는가에 대한 빈도 - position
해당 Term이 Field내에 몇번째 Term인지에 대한 값으로, 맨 앞에 존재하면 0 - offset
해당 Term이 Field내의 문자열 시작점부터 끝점까지의 값
Inverted Indexing 과정설명
- 먼저 Field들을 분류한다.
- 각 Field들에 맞는 Term들을 추출한다.
- 추출한 Term별로 DocFreq를 계산한다.
- 추출한 Term이 존재하는 Document별로 TermFreq를 계산하고 각 Document내 position을 구한다.
- (offset은 언제 구하는지 정확히 모르겠지만, Term추출 또는 DocFreq를 계산할 때 구하는 듯 합니다.)
- Term이 Key이고 Value가 Postings List(Document ID List)인 Inverted Index가 생성된다.
'내가 공부하고 싶은 IT > 지식정리' 카테고리의 다른 글
Elasticsearch bool 쿼리 (0) 2023.01.01 Elasticsearch DSL 기본 (0) 2023.01.01 Elasticsearch 분석기 테스트 (0) 2022.12.25 Elasticsearch 분석기 (0) 2022.12.25 포인트(Point) 테이블 설계 (0) 2022.11.20