Skip to content

Latest commit

 

History

History
53 lines (47 loc) · 4.64 KB

ABOUT_INVERTED_INDEXING.md

File metadata and controls

53 lines (47 loc) · 4.64 KB

역색인화 (Inverted Indexing)

관련 솔루션:

1. 색인

(1) 색인화란?

기본적으로 '색인화(Indexing)'란 대량 문서에서 원하는 내용을 빠르게 검색할 수 있도록 문서를 효율적인 구조로 변환하는 작업을 일컫는다. Solr에서의 색인화는 도큐먼트로부터 색인 테이블을 생성하여 쿼리를 이용한 검색이 가능하도록 만드는 과정을 뜻한다.

(2,1) 역색인화란?

보통의 색인 테이블은 도큐먼트 번호 - 해당 번호에 대응하는 도큐먼트의 내용으로 구성되는 반면, 역색인 테이블은 토큰 - 해당 토큰을 포함하는 도큐먼트의 번호로 이루어져 있다. 역색인화(Inverted Indexing)'는 바로 이 역색인 테이블을 만드는 작업을 뜻한다. 토큰(Token)은 각 도큐먼트의 내용을 의미있는 단어로 분리한(+ 불용어 제거, 정규화 등) 최소 길이의 식별자를 의미하며 여기에는 숫자도 포함된다. 토큰의 분리에는 형태소 분석기(Morpheme Analyzer)가 필요하다.

(2.2) 역색인화의 장점

SQL의 단순 LIKE문이 각 도큐먼트의 실제 내용과 검색어를 비교해야 하는 것에 비해, 역색인 테이블은 도큐먼트의 내용을 탐색할 필요가 없어 토큰화 작업만 빠르게 이루어진다면 검색 시간을 효과적으로 단축할 수 있다.

(3) 도큐먼트

도큐먼트는 웹사이트나 기타 곳곳에 퍼져 있는 로우(Raw) 데이터들을 한데 모아 정형화시킨 것을 통칭해서 부르는 말이다. SQL 데이터베이의 테이블이 될 수도 있고, CSV 파일이 될 수도 있고, NoSQL 데이터베이스의 키-값 컬렉션이 될 수도 있다.

예를 들어, 어떤 웹사이트의 정보를 크롤링하여 테이블 형태로 정형화시켰을 경우 다음과 같은 모습이 나오게 된다.

    +--------+---------------------+-------------+----------------------+
    |   ID   |         URL         |    TITLE    |       CONTENTS       |
    +--------+---------------------+-------------+----------------------+
    |  ...   |         ...         |     ...     |          ...         |
    +--------+---------------------+-------------+----------------------+
                                <도큐먼트의 예>

이러한 도큐먼트에 등장하는 텍스트들을 분석하여 별도의 역색인 테이블을 만들면 다음과 같은 형태가 된다.

                    +------------+---------------------+
                    |    Term    |     Document ID     |
                    +------------+---------------------+
                    |     cpp    |          1          |
                    +------------+---------------------+
                    |  developer |          2          |
                    +------------+---------------------+
                    |    code    |       1, 3, 4       |
                    +------------+---------------------+
                    |    java    |    3, 4, 7, 8, 10   |
                    +------------+---------------------+
                    |     git    |         4, 9        |
                    +------------+---------------------+
                    |     ...    |         ...         |
                    +------------+---------------------+
                              <역색인 테이블의 예>

사용자가 'cpp code'를 검색했다면, 'cpp'와 'code'에 해당하는 도큐먼트가 반환된다.

2. 검색

역색인 테이블에서의 검색은 사용자가 입력한 검색어와 일치하거나 연관성이 높은 도큐먼트를 찾는 과정이다. 이를 수행하려면 문자열 형식의 검색어를 일정한 규격을 가진 최소 형태인 토큰으로 파싱(tokenizing, query parsing)하는 과정이 필요하다. 검색어가 적절한 클래스를 거쳐 토큰으로 분리되면, 해당 토큰을 역색인 테이블의 Term 필드 값과 비교하여 일치 또는 유사하다고 판단되는 도큐먼트를 반환한다.

3. 루씬

이러한 역색인 테이블 자료구조를 이용한 데이터 색인화 및 검색을 가능하게 해 주는 오픈 소스 라이브러리가 바로 루씬(Lucene)이다. 아파치 라이선스 2.0으로 공개되어 있고 Java로 프로그래밍되었다. 모든 문서들을 JSON 형식의 파일로 인덱싱하여 저장하고, RESTful API로 이 인덱싱한 결과물을 검색할 수 있게 하는 기능을 제공한다.