FULL TEXT SEARCH and INVERTED INDEX 파헤치기

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

J.phil
2023-02-23
2023-02-05
2913

# OVERVIEW

앞 elasticsearch lecture에서 [LINK](https://www.joinc.co.kr/w/elk_stack_theory) 설명한 대로 full-text search는 로그 분석 및 다량 데이터 분석에서 매우 필요한 기술이다. 이를 학습하기 전에 먼저 과연 우리가 데이터 분석을 위해 다루게 될 데이터들은 어떤 종류로 나누어지는지 파악해보고, 그 후 full-text search에 대해서 설명하려 한다.

## Data Type

일반적으로 데이터 포맷은 크게 3 종류로 나뉜다. 이에 따라 Database의 종류가 나뉘고 저장 방식도 차이가 생긴다. 가령, 여러분들이 기존에 많이 접해본 RDBMS Mysql은 Structured Data 범주인 CSV 파일을 손쉽게 저장 및 관리할 수 있다. 하지만 Apache Log 과 같이 Json 데이터 포맷은 저장하기 쉽지 않으므로, 다른 Database 가령 Nosql을 사용해서 저장 및 관리해야한다. 이처럼 어떤 데이터 포맷들이 있는지 살펴보자.

- Structured Data
	- 국문으로 `정형 데이터`라 하며, 미리 정해놓은 형식과 구조에 따라 저장되도록 구성하여 고정된 스키마, i.e., fixed schema 저장되는 데이터 입니다. 즉, 지정된 행열에 데이터가 구별되어 있으며, 이를 위에서 설명한 것처럼 RDBMS의 테이블 형태로 저장한다. 이처럼 정해진 구조 바탕으로 데이터를 용이하게 검색 및 수정 및 삭제 (CRUD) 등의 연산을 수행할 수 있다. 
- Semi-Structured Data
	- 국문으로 `반정형 데이터`라 하는데, 사실 국문이 어색하여 필자는 영문 그대로 `SEMI-STRUCTURED DATA`라고 부른다. 위에서 설명한 정형 데이터와 같이 TABLE의 행과 열로 구조화되어 있지는 않으나 Schema 및 Metadata 특성을 가지고 있다. 즉 정형 데이터와 달리 데어티 내용안에 구조에 대한 설명이 함께 존재한다고 봐도 무방한다. 예시로 `XML, HTML, JSON` 형태가 있다.
- Unstructured Data
	- `비정형 데이터`라 칭하며, 위 2가지 포맷과 달리 특별히 정해진 구조가 없이 저장된 데이터이다. social network test, image, video file, word, etc 문서와 같은 멀티미디어 데이터가 대표적인 예다. 약 20년전부터 SNS 이용률이 크게 높아지면서 실시간으로 많은 양의 비정형 데이터가 생산되고 있어 여러분들은 해당 데이터들을 쉽게 접할 수 있다.

## Full Text Search and Inverted Index

이제 본격적으로 full text search에 대해서 알아보려고 한다. elasticsearch 에서는 이 기능을 위해 Inverted Index 자료구조를 이용한다. 그럼 이는 무엇일까?

### What is Inverted Index ?

- Inverted Index 자료 구조를 들어본 적이 있는가? 만약 들어보지 못했더라도, 이 자료 구조는 여러분의 실생활에서 접해봤을 것이다. 요즘은 많이 쓰지 않지만, 필자가 어렸을 때는 `백과사전` 모음집 세트를 어린이날 선물로 받곤 했다. 항상 이 백과사전을 어떻게 봐야하는가 궁금증을 갖고 있을때마다, 가장 뒷면으로 시선을 옮겼다. 이 때  사전에 나오는 단어별로 'Word - Page1, Page 20, Page 100' 이런 구조로, 어떤 단어들이 어떤 페이지에서 설명하고 있는지 Figure로 표시되어있었다. 이게 바로 `Inverted Index`구조이다.

- 이처럼 다량의 문서들이나 데이터들을 Elasticsearch 에 Bulky Insertion 할 때 특정 연산과정들을 통해서 각 단어별로 문서번호를 연결해서 이 자료 구조를 만들어준다. 이를 통해 User가 어떤 특정 단어들을 임의적으로 검색할 수 있게 된다. 이런 검색 기능을 full text search 라고 정의한다.

### How to make Inverted Index in the Elasticsearch ?

![INVERTED INDEX](https://joinc-edu.s3.ap-northeast-2.amazonaws.com/joinc-posting/p-full1.png)

그럼 위와 같은 Inverted Index 는 어떻게 만들어질까? 아래와 같이 5 STEP 을 통해 생성된다.

> Document 1. `The quick brown fox jumped over the lazy dog`
Document 2. `Quick brown foxes leap over lazy dogs in summer`

**STEP1 >** Fetching the Document
- 위 그림처럼 위 2개 Document 들을 스캔하여 Unique 단어들을 리스트들을 만들어 준다.

![STEP2](https://joinc-edu.s3.ap-northeast-2.amazonaws.com/joinc-posting/p-fe1.png)

**STEP2 >** Removing the Stop Words
- 자! 과연 고객들이 Document 나 Log 에서 단어들을 검색할 때 전치사, 관사, Be 동사 등 이런 단어들 검색하고 싶을까? 이들은 특정 Meanigful Word 가 아니므로 이 단계에서 Stop Word List 를 통해 제거해주고 1번에서 만들었던 리스트들을 경량화 시킨다. 
- 이 때 고객이 'quick' 이라는 문자 그대로 검색하게 되면 어떤 문제가 발생할까? 'Quick' 대문자는 검색이 안되고 'quick' 소문자만 결과만 받게 되는데 이는 원하는 결과가 아니다! 고객은 대-소문자를 구분해서 검색하거나, 3인칭 단수-복수 들을 구분해서 검색하고 싶지 않다. 그러기 위해서 3. Normalization 과정이 필요하다.

![STEP2](https://joinc-edu.s3.ap-northeast-2.amazonaws.com/joinc-posting/p-fe2.png)

**STEP3 >**  Stem to the Root Word

- 이 과정을 통해서 위 문제들을 해결해준다.
     - 동의어 묶어주기
     - 단수, 복수 표준화 시켜서 묶어주기
     - 대,소문자를 한 단어로 통일해서 묶어주기
     - etc
-  표준화 과정
    - `Quick` and `quick` appear as separate terms, while the user probably thinks of them as the same word. Quick can be lowercased to become quick.
    - `fox` and `foxes` are pretty similar, as are `dog` and `dogs`; They share the same root word. foxes can be stemmed--reduced to its root form—to become fox. Similarly, dogs could be stemmed to dog.
    - `jumped` and `leap`, while not from the same root word, are similar in meaning. They are synonyms. jumped and leap are synonyms and can be indexed as just the single term jump.

![STEP2](https://joinc-edu.s3.ap-northeast-2.amazonaws.com/joinc-posting/p-fe-3.png)

**STEP4 >**   Record Document IDs

- 이제 간단하게 위 표준화된 단어들을 각각 Document ID를 부여해서 기록한다.

**STEP5 >** Merge and Store the Terms
- 이전 과정을 통한 결과 값들을 하나로 묶어서 저장하고, Inverted Index 자료구조를 완성시킨다. :)

Search For:

BY TAGS

Recent Posts

Archive Posts

Tags

About

Get in Touch

Categories