역색인

역색인은 컬렉션 내의 각 용어를 해당 용어를 포함하는 문서들의 포스팅 목록에 매핑하여, 검색 시스템이 모든 문서를 스캔하지 않고도 일치하는 문서를 찾을 수 있도록 합니다.

Definition

역색인은 색인된 용어 사전으로 구성된 데이터 구조이며, 각 용어는 해당 용어를 포함하는 문서를 열거하는 포스팅 목록을 가리키며, 검색이 포스팅 목록을 교차하거나 병합하여 수행될 수 있도록 빈도 및 용어 위치로 주석이 달리는 경우가 많습니다.

Scope

이 주제는 역색인의 구조와 구축에 대해 다룹니다: 용어 사전, 문서 식별자, 용어 빈도 및 위치를 기록하는 포스팅 목록, 그리고 블록 정렬 기반 색인화 및 단일 패스 메모리 내 색인화를 포함하여 대규모 컬렉션에 대한 색인을 구축하고 업데이트하는 알고리즘. 구문 질의를 위한 위치 정보와 색인 유지보수 공학을 다루며, 압축 및 질의 평가 전략은 인접 주제로 남겨둡니다.

Core questions

• 사전 항목과 그 포스팅 목록에는 무엇이 포함됩니까?
• 구문 및 근접 질의를 지원하기 위해 위치는 어떻게 저장됩니까?
• 컬렉션이 메모리에 비해 너무 클 때 역색인은 어떻게 구축됩니까?
• 문서가 추가, 변경 또는 삭제될 때 색인은 어떻게 업데이트됩니까?
• 포스팅 목록은 결합 질의를 위한 효율적인 교차를 어떻게 지원합니까?

Key concepts

• 용어 사전
• 포스팅 목록
• 문서 식별자
• 위치 색인
• 용어 빈도 저장
• 블록 정렬 기반 색인화 (BSBI)
• 단일 패스 메모리 내 색인화 (SPIMI)
• 색인 병합 및 업데이트

Key theories

사전 및 포스팅 구성

압축된 용어 사전을 가변 길이 포스팅 목록과 분리함으로써 시스템은 용어를 빠르게 찾아보고 관련 문서만 스트리밍할 수 있으며, 이는 모든 역색인 검색의 구조적 기반입니다.

확장 가능한 색인 구축

블록 정렬 기반 색인화 및 단일 패스 메모리 내 색인화와 같은 디스크 기반 방법은 부분 색인을 축적하고 병합함으로써 메모리보다 훨씬 큰 컬렉션에 대한 역파일을 구축합니다.

Clinical relevance

역색인은 웹 검색 엔진, Lucene 및 그 파생물과 같은 오픈 소스 검색 플랫폼, 데이터베이스 전체 텍스트 검색을 포함하여 사실상 모든 텍스트 검색 시스템의 핵심 데이터 구조입니다. 그 설계는 어떤 질의 유형이 지원되고 얼마나 빠르고 저렴하게 답변될 수 있는지를 결정합니다.

History

역파일은 초기 서지 검색 시스템에서 사용되었으며, 컬렉션이 증가함에 따라 전체 텍스트 검색의 표준 구조가 되었습니다. 단일 패스 메모리 내 색인화와 같은 확장 가능한 구축 방법을 포함한 1990년대와 2000년대의 연구는 웹 규모의 코퍼스를 색인화하는 것을 실용적으로 만들었으며, 이 구조는 현재 널리 사용되는 오픈 소스 검색 라이브러리의 기반이 되고 있습니다.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

왜 '역'색인이라고 불립니까?

일반(순방향) 색인은 각 문서에 대해 해당 문서가 포함하는 용어를 나열합니다. 역색인은 이 매핑을 역전시켜 각 용어에 대해 해당 용어를 포함하는 문서를 나열합니다. 이러한 역전은 용어 기반 조회를 빠르게 만드는 핵심입니다.

위치 색인은 무엇에 사용됩니까?

위치 색인은 각 용어가 각 문서 내에서 나타나는 위치를 저장합니다. 이를 통해 시스템은 용어가 문서 어딘가에 나타나는지 여부뿐만 아니라 용어의 순서나 근접성이 중요한 구문 질의 및 근접 질의에 답변할 수 있습니다.