Inverted Index

역인덱스는 문서 검색 시스템의 핵심 데이터 구조로, 효율적인 전문 검색(full-text search)을 가능하게 한다. 이 구조는 텍스트 검색 엔진의 기본 요소이며, 현대 검색 엔진의 핵심 기술이다.

현대의 검색 엔진과 정보 검색 시스템에서 필수적인 요소로, 사용자가 방대한 문서 컬렉션에서 관련 정보를 빠르게 찾을 수 있도록 도와준다. 역인덱스의 구조와 알고리즘을 이해하는 것은 효율적인 검색 시스템을 설계하고 구현하는 데 중요한 기반이 된다.

역인덱스의 기본 개념

일반적인 인덱스(forward index)는 문서를 식별자로 찾아 그 내용을 검색하는 방식이다. 반면, 역인덱스는 이 관계를 ‘뒤집어’ 단어나 용어를 키로 하고, 그 단어가 등장하는 문서들의 목록을 값으로 저장한다.

예를 들어 설명해 보면:

문서 컬렉션:

일반 인덱스:

역인덱스:

이런 구조를 통해 “사과"라는 단어를 검색할 때 바로 문서1과 문서2를 찾을 수 있다.

역인덱스의 구조

역인덱스는 주로 두 가지 구성 요소로 이루어진다:

  1. 어휘 사전(Dictionary): 문서 컬렉션에 나타나는 모든 고유 용어의 목록
  2. 포스팅 리스트(Posting List): 각 용어가 등장하는 문서의 식별자 목록

더 발전된 역인덱스는 다음과 같은 추가 정보를 포함할 수 있다:

역인덱스 생성 과정

역인덱스를 생성하는 과정은 다음과 같은 단계로 이루어진다:

  1. 문서 수집: 인덱싱할 문서들을 수집한다.
  2. 토큰화(Tokenization): 문서를 개별 용어(토큰)로 분리한다.
  3. 정규화(Normalization): 대소문자 통일, 불용어 제거, 어간 추출 등의 과정을 통해 토큰을 정규화한다.
  4. 인덱싱: 정규화된 토큰을 역인덱스 구조에 저장한다.

간단한 파이썬 코드로 구현한 역인덱스 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

def create_inverted_index(documents):
    """
    문서 컬렉션으로부터 역인덱스를 생성합니다.
    
    Args:
        documents: 문서 ID와 내용을 담고 있는 딕셔너리
        
    Returns:
        역인덱스 딕셔너리
    """
    inverted_index = {}
    
    # 각 문서에 대해 처리
    for doc_id, content in documents.items():
        # 토큰화 (간단한 공백 기준 분리)
        tokens = content.lower().split()
        
        # 각 토큰에 대해 역인덱스 구축
        for token in tokens:
            # 이미 인덱스에 있는 토큰이면 문서 ID 추가
            if token in inverted_index:
                inverted_index[token].add(doc_id)
            # 새로운 토큰이면 새 집합 생성 후 문서 ID 추가
            else:
                inverted_index[token] = {doc_id}
    
    return inverted_index

# 예시 사용
documents = {
    1: "사과는 맛있는 과일입니다",
    2: "바나나와 사과는 과일입니다",
    3: "과일은 건강에 좋습니다"
}

index = create_inverted_index(documents)
print(index)

역인덱스의 검색 과정

역인덱스를 이용한 검색은 다음과 같은 단계로 이루어진다:

  1. 쿼리 처리: 사용자의 쿼리를 토큰화하고 정규화한다.
  2. 용어 검색: 각 쿼리 용어에 대한 포스팅 리스트를 검색한다.
  3. 결과 병합: 불리언 연산(AND, OR, NOT)이나 랭킹 알고리즘을 이용해 최종 결과를 생성한다.

간단한 검색 함수 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def search(inverted_index, query):
    """
    역인덱스를 이용해 쿼리에 해당하는 문서를 검색합니다.
    
    Args:
        inverted_index: 역인덱스 딕셔너리
        query: 검색할 쿼리 문자열
        
    Returns:
        쿼리와 일치하는 문서 ID 집합
    """
    # 쿼리 토큰화
    tokens = query.lower().split()
    
    if not tokens:
        return set()
    
    # 첫 번째 토큰으로 결과 초기화
    result = inverted_index.get(tokens[0], set())
    
    # AND 연산 수행 (모든 토큰이 포함된 문서 검색)
    for token in tokens[1:]:
        result = result.intersection(inverted_index.get(token, set()))
    
    return result

# 예시 검색
query = "사과 과일"
result = search(index, query)
print(f"쿼리 '{query}'에 해당하는 문서: {result}")

역인덱스의 장점

  1. 검색 속도: 특정 용어가 포함된 문서를 빠르게 찾을 수 있다.
  2. 공간 효율성: 압축 기법을 적용하여 저장 공간을 최적화할 수 있다.
  3. 증분 업데이트: 새로운 문서가 추가될 때 전체 인덱스를 재구성할 필요 없이 업데이트가 가능하다.
  4. 복잡한 쿼리 지원: 불리언 연산, 근접 검색, 구문 검색 등 다양한 검색 기법을 지원한다.

역인덱스의 최적화 기법

  1. 인덱스 압축(Index Compression): 포스팅 리스트를 압축하여 저장 공간과 메모리 사용량을 줄인다.

    • 가변 길이 인코딩(Variable-length encoding)
    • 델타 인코딩(Delta encoding)
    • 비트맵 인덱싱(Bitmap indexing)

  2. 스키핑(Skipping): 포스팅 리스트에 건너뛰기 포인터를 추가하여 검색 속도를 개선한다.

  3. 필터링(Filtering): 블룸 필터(Bloom filter)와 같은 확률적 자료구조를 사용하여 빠른 필터링을 수행한다.

실제 활용 사례

  1. 검색 엔진: Elasticsearch, Solr, Lucene 등의 검색 엔진은 역인덱스를 핵심 데이터 구조로 사용한다.
  2. 텍스트 마이닝: 대량의 문서에서 특정 패턴이나 정보를 추출하는 데 활용된다.
  3. 정보 검색 시스템: 디지털 도서관, 학술 검색 시스템 등에서 문서 검색을 위해 사용된다.

용어 정리

용어설명

참고 및 출처