역색인

컴퓨터 과학에서 역색인, 역 인덱스(inverted index), 역 파일(inverted file)은 낱말이나 숫자와 같은 내용물로부터의 매핑 정보를 데이터베이스 파일의 특정 지점이나 문서 또는 문서 집합 안에 저장하는 색인 데이터 구조이다. 역색인의 목적은 문서가 데이터베이스에 추가될 때 늘어나는 처리를 위해 빠른 전문 검색을 가능케 하는 것이다. 역 파일은 색인이 아닌, 데이터베이스 파일 그 자체를 가리킬 수도 있다. 문서 검색 시스템에 쓰이는 가장 대중적인 데이터 구조로서, 이를테면 검색 엔진과 같은 대규모에 쓰인다. 일부 중요한 일반 목적 메인프레임 기반 데이터베이스 관리 시스템들은 역색인 구조를 사용해 왔으며 아다바스, 데이터콤/DB, 모델 204 등이 있다.

역색인에는 두 가지 주요 변형이 있다. 레코드 수준 역색인(또는 역파일 색인 또는 그냥 역파일)은 각 단어에 대한 문서 참조 목록을 포함한다. 단어 수준 역색인(또는 전체 역색인 또는 역목록)은 문서 내 각 단어의 위치를 추가로 포함한다. 후자 형태는 더 많은 기능(예: 구문 검색)을 제공하지만 생성하는 데 더 많은 처리 능력과 공간이 필요하다.

응용

역색인 자료 구조는 일반적인 검색 엔진 색인 알고리즘의 핵심 구성 요소이다. 검색 엔진 구현의 목표는 질의 속도를 최적화하는 것이다: 단어 X가 나타나는 문서를 찾는 것. 문서당 단어 목록을 저장하는 정방향 색인이 개발되면, 이를 역으로 변환하여 역색인을 개발한다. 정방향 색인에 질의하면 일치하는 문서를 확인하기 위해 각 문서와 각 단어를 순차적으로 반복해야 한다. 이러한 질의를 수행하는 데 필요한 시간, 메모리 및 처리 자원은 항상 기술적으로 현실적이지 않다. 정방향 색인에 문서당 단어를 나열하는 대신, 단어당 문서를 나열하는 역색인 자료 구조가 개발된다.

역색인이 생성되면, 역색인에서 단어 ID로 임의 접근하여 질의를 해결할 수 있다.

컴퓨터 이전 시대에는 중요한 책의 용어 색인이 수작업으로 조립되었다. 이들은 엄청난 노력을 요하는 소량의 해설이 동반된 효과적인 역색인이었다.

생물정보학에서 역색인은 염기서열 분석된 DNA의 짧은 단편 서열 조립에 매우 중요하다. 단편의 출처를 찾는 한 가지 방법은 참조 DNA 서열에 대해 검색하는 것이다. (염기서열 분석된 DNA와 참조 DNA 간의 차이 또는 오류로 인한) 소수의 불일치는 단편을 더 작은 단편으로 나누어 설명할 수 있다. 적어도 하나의 하위 단편은 참조 DNA 서열과 일치할 가능성이 높다. 일치시키려면 참조 DNA 서열에서 특정 길이의 모든 부분 문자열에 대한 역색인을 구성해야 한다. 인간 DNA는 30억 개 이상의 염기쌍을 포함하고, 우리는 각 색인에 대해 DNA 부분 문자열과 색인 자체에 대해 32비트 정수를 저장해야 하므로, 이러한 역색인에 필요한 저장 공간은 아마 수십 기가바이트가 될 것이다.

압축

역사적인 이유로, 역목록 압축과 비트맵 압축은 별도의 연구 분야로 개발되었으며, 나중에 본질적으로 동일한 문제를 해결한다는 것이 인식되었다.

같이 보기

• 벡터 공간 모델

각주

• Knuth 1997, 560–563 of section 6.5: Retrieval on Secondary Keys쪽

외부 링크

• (영어) NIST's Dictionary of Algorithms and Data Structures: inverted index