역색인

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역색인의 구조 및 종류
- 2.1. 레코드 단위 역색인
- 2.2. 단어 단위 역색인
3. 역색인의 활용
- 3.1. 검색 엔진
- 3.2. 생물 정보학
4. 역색인과 정색인
5. 압축
참조

1. 개요

역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이다. 크게 레코드 단위와 단어 단위 역색인으로 나뉘며, 레코드 단위는 단어와 해당 단어를 포함하는 문서 목록을, 단어 단위는 위치 정보까지 포함한다. 역색인은 검색 엔진의 핵심 요소로, 쿼리 속도를 최적화하는 데 사용된다. 텍스트 검색, 생물 정보학 등 다양한 분야에서 활용되며, 저장 공간 효율성을 위해 압축 기법이 적용되기도 한다.

더 읽어볼만한 페이지

검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
데이터 관리 - 데이터 센터
데이터센터는 컴퓨터 시스템 및 관련 장비와 지원 인프라를 수용하는 시설로, 기술 발전에 따라 규모와 중요성이 확대되었으며, 에너지 효율과 보안을 고려하여 설계 및 운영되고, TIA-942 표준에 따른 티어 분류와 친환경 기술 도입이 이루어지고 있다.
데이터 관리 - 정보 아키텍처
정보 아키텍처는 정보 시스템 및 정보 기술 분야에서 공유 정보 환경의 구조적 설계를 의미하며, 웹사이트, 소프트웨어 등의 구성과 레이블링을 포함하여 검색 용이성과 사용성을 지원하고, 도서관정보학에 기원을 두고 있다.

역색인
데이터 구조
유형	인덱스
개요
설명	역색인은 데이터베이스에서 데이터의 위치를 빠르게 찾기 위해 사용되는 인덱스 유형이다. 일반적인 데이터베이스 인덱스는 데이터 레코드의 키를 저장하고 해당 키에 대한 포인터를 저장하는 반면, 역색인은 단어 또는 값과 같은 콘텐츠를 저장하고 해당 콘텐츠를 포함하는 데이터 레코드에 대한 포인터를 저장한다.
속성
용도	전체 텍스트 검색에서 사용된다. 데이터 마이닝에서 사용된다. 정보 검색에서 사용된다.
구조
구성 요소	어휘 (용어 집합) 발생 (각 용어에 대해, 문서 목록이 나타나는 위치)
예시
예시 설명	문서 모음이 있다고 가정해보자. 문서 1: "This is the first document." 문서 2: "This is the second document." 다음은 이러한 문서에 대한 작은 역색인이다.
역색인	"this": {1, 2} "is": {1, 2} "the": {1, 2} "first": {1} "second": {2} "document": {1, 2}

2. 역색인의 구조 및 종류

역색인은 크게 두 가지로 나뉜다.

레코드 단위 역색인 (record level inverted index): '역 파일 인덱스'라고도 하며, 각 단어와 그 단어를 포함하는 모든 문서 목록을 담는다. 디스크 용량은 절약되지만, 단어 검색만 가능하고 구문 검색은 할 수 없다.
단어 단위 역색인 (word level inverted index): '완전 역색인'이라고도 하며, 각 단어를 포함하는 모든 문서와 함께 단어의 문서 내 위치 정보까지 담는다. 가장 단순하게는 모든 문서 ID와 위치 정보를 쌍으로 저장한다.

레코드 단위 역색인은 기능이 제한적인 반면, 단어 단위 역색인은 구문 검색 등 고급 검색을 지원한다.^[1]

2. 1. 레코드 단위 역색인

레코드 단위 역색인은 각 단어와 해당 단어를 포함하는 모든 문서의 목록을 저장한다. 구현이 간단하고 저장 공간을 적게 차지하지만, 구문 검색(phrase search)과 같이 단어의 순서나 위치가 중요한 검색에는 적합하지 않다.^[1]

2. 2. 단어 단위 역색인

단어 단위 역색인(완전 역색인이라고도 함)은 각 단어를 포함하는 모든 문서뿐만 아니라, 해당 단어가 문서 내에서 나타나는 위치 정보까지 함께 저장한다. 단어의 위치 정보를 활용하여 구문 검색, 근접 검색(proximity search) 등 고급 검색 기능을 구현할 수 있다. 레코드 단위 역색인에 비해 더 많은 저장 공간을 필요로 한다. 구현 방법에 따라, 모든 문서 ID와 그 저장 위치 정보를 쌍으로 저장하거나, 해시 테이블 형태를 취하기도 한다.

다음과 같은 텍스트가 있다고 가정해 보자.

:

T_0=

"it is what it is",

:

T_1=

"what is it",

:

T_2=

"it is a banana"

여기에서 단어 출현 위치까지 포함하는 완전한 역색인을 만들면 다음과 같다.

단어	문서 및 위치 정보
a	(2, 2)
banana	(2, 3)
is	(0, 1), (0, 4), (1, 1), (2, 1)
it	(0, 0), (0, 3), (1, 2), (2, 0)
what	(0, 2), (1, 0)

문서 번호와 마찬가지로, 단어 출현 위치는 0을 기준으로 한다. 예를 들어 "banana": {(2, 3)}는 "banana"라는 단어가 3번째 문서( $T_2$ )에 나타나고, 해당 문서 내의 4번째 단어(position 3)라는 의미이다.

"what is it" 이라는 구문 검색을 실행하면 모든 문자열을 포함하는 문서 0과 문서 1이 검색된다. 하지만 단어가 연속해서 (구문 = 프레이즈로) 나타나는 것은 문서 1뿐이라는 것을 알 수 있다.

3. 역색인의 활용

역색인은 다양한 분야에서 활용되고 있다.

검색 엔진은 역색인을 이용하여 사용자가 입력한 검색어에 해당하는 문서를 빠르게 찾아낸다.^[5] 생물 정보학에서 역색인은 시퀀싱된 DNA의 짧은 단편(read)의 시퀀스 조립에 매우 중요하다.^[5]

3. 1. 검색 엔진

역색인 자료 구조는 검색 엔진 색인 알고리즘의 핵심 구성 요소이다.^[5] 검색 엔진은 역색인을 이용하여 사용자가 입력한 검색어(쿼리)에 해당하는 문서를 빠르게 찾아내고, 관련성 순으로 정렬하여 결과를 제공한다. 검색 엔진 구현의 목표는 쿼리 속도를 최적화하는 것이며, 역색인은 이러한 목표를 달성하는 데 필수적인 기술이다.^[6]

역색인이 생성되면 역색인에서 단어 ID( 무작위 접근을 통해)로 이동하여 쿼리를 해결할 수 있다.

컴퓨터 시대 이전에는 중요한 책에 대한 콘코던스가 수동으로 조립되었다. 이것들은 엄청난 노력을 들여 제작해야 했던 소량의 해설이 함께 제공되는 실질적인 역색인이었다.

전산 기술에서 역색인은 단어, 숫자 등의 내용에서 해당 내용이 포함된 데이터베이스나 문서 모음으로의 매핑을 유지하는 인덱스형 자료 구조이다. 문서 모음으로의 매핑의 경우, 검색 엔진이 구현된다. 역색인 파일은 인덱스라기보다는 데이터베이스라고 부르는 것이 더 적절한 경우도 있다. 또한, 검색 키가 단어(문자열)이고, 연관 배열의 값이 위치 정보인 경우, 해시 테이블의 형태를 취하기도 한다.

역색인에는 크게 2가지 방법이 있다.

레코드 단위 역색인(record level inverted index; 역 파일 인덱스라고도 함)은 단어와 해당 단어를 포함하는 모든 문서를 리스트로 갖는다.
단어 단위 인덱스(word level inverted index; 완전 역색인이라고도 함)는 단어를 포함하는 모든 문서 외에, 해당 단어가 문서 내 어디에 나타나는지 위치 정보까지 포함한다. 단어 단위 역색인 구현 방법에도 여러 가지가 있다. 가장 단순한 것은 모든 문서 ID와 그 저장 위치 정보를 쌍으로 저장하는 것이다.

레코드 단위 역색인은 디스크 용량 절약에는 도움이 되지만, 그만큼 기능성도 떨어진다. (일반적으로 검색 엔진에서 수행하는) 단어 검색은 가능하지만, (검색 쿼리를 따옴표로 묶는 것과 같은) 구문 검색은 할 수 없다.

검색 엔진을 설계할 때, 전치 인덱스의 필요성을 고려하고, 엔진의 알고리즘, 그 동작 단계를 고려하는 것은 중요한 일이다. 예를 들어, 코퍼스를 사용한 방법으로 색인 파일을 만드는 것을 생각해 보자. 알고리즘의 시작은, 첫 번째 문서를 확인하고, 단어별로 분할하는 것이다. 처리의 마지막에는, 문서에 나타나는 모든 단어의 목록과 그 출현 위치를 나열한다. 물론, 같은 단어는 여러 번에 걸쳐 나타난다. 따라서 출현 위치 정보도 하나만 있는 것은 아니다. 위치 정보란 단어가 문서의 어디에 위치해 있는지이며, 단어의 출현에 앞서 나타난 문자 수를 세는 것이라고 할 수 있다. 예를 들어, 어떤 문서에 처음 나타난 단어는, 문서의 첫 번째 문자를 포함하고 있으며, 즉 위치 정보는 "0"이라고 할 수 있다. 두 번째 단어는 5번째 문자에 출현한다고 한다. 따라서 위치 정보도 "5"가 된다.

표 형식으로 나타내면 다음과 같다.

단어 ID	단어	위치 정보
1	dog	1, 20, 500, etc
2	cat	10, 45, 3445, etc

하나의 문서뿐만 아니라, 코퍼스를 사용하고 있기 때문에, 각 문서에 나타나는 모든 단어를 저장하는 데 더 큰 목록이 필요하게 된다. 여기가 검색 엔진 설계자의 견해가 다른 부분이며, 모든 검색 엔진이 같은 설계가 아닌 이유 중 하나이다.

일반적인 견해로는, 각 문서에 연속적으로 접근할 때, 그때마다 직접 단어 목록을 생성하여 저장해 가는 것이 손쉬운 방법일 것이다. 문서별로 단어 목록을 저장해 가면 완성되는 것은 우리가 잘 아는 소위 "색인"이 된다. 이 시점에서는 문서당 단어 목록이며, 단어당 문서 목록은 아니므로 전치 색인(역 색인)이 아닌 정색인이라고 할 수 있을 것이다. 아래가 그 예이다. (검색 엔진에 따라서는 크게 구조가 다른 경우도 있다)

문서 ID	포함된 단어 ID와 위치
1	(1 at 1, 20, 500) (2 at 10, 45, 3445)
2	(1 at 3, 50, 60) (2 at 100, 120, 130, ..)
3	etc

전치 인덱스의 기본적인 개념은 테이블에 대해 "단어 X는 어떤 문서에 있는가"와 같은 쿼리의 응답 속도를 최적화하는 것이다.

위의 테이블에 대한 쿼리에서는, 목록 중의 각 항목을 일일이 확인하고, 각 항목에 대해 단어가 존재하는지를 확인해야 하는 알고리즘이 된다. 전치 인덱스란 문서별로 단어를 찾는 것이 아니라, 단어별로 그것을 포함하는 문서를 목록 추출하기 위해, 위의 테이블의 행렬을 "전치"시킨 것이다.

같은 예에서, 전치 인덱스는 다음과 같을 것이다.

단어 ID	해당 문서 ID
1	1, 3, 4, 5
2	2, 3, 4
3	etc

이렇게 함으로써, 단어를 포함하는 문서를 찾기 위해, 알고리즘은 전치 인덱스의 단어 ID로 점프하여, 문서 목록을 찾아낼 수 있다. 이것에 의해 검색 응답 시간의 대폭적인 단축이 이루어지게 된다.

3. 2. 생물 정보학

생물 정보학에서 역색인은 시퀀싱된 DNA의 짧은 단편(read)의 시퀀스 조립에 매우 중요하다.^[5] 단편의 출처를 찾는 한 가지 방법은 참조 DNA 시퀀스에 대해 검색하는 것이다. 시퀀싱된 DNA와 참조 DNA 간의 차이 또는 오류로 인한 소수의 불일치는 단편을 더 작은 단편으로 나누어 처리할 수 있다. 즉, 최소한 하나의 하위 단편이 참조 DNA 시퀀스와 일치할 가능성이 있다. 일치를 위해서는 참조 DNA 시퀀스에서 특정 길이의 모든 부분 문자열에 대한 역색인을 구축해야 한다. 인간 DNA에는 30억 개 이상의 염기쌍이 포함되어 있고 각 색인에 대해 DNA 부분 문자열을 저장해야 하며, 색인 자체에 대해 32비트 정수를 저장해야 하므로, 이러한 역색인에 대한 저장 요구 사항은 수십 GB가 될 것이다.

4. 역색인과 정색인

역색인은 정색인과 대비되는 개념이다. 정색인은 각 문서별로 포함된 단어 목록을 저장하는 방식이다.^[5] 정색인은 각 문서와 각 단어를 순차적으로 반복하여 일치하는 문서를 확인해야 하므로, 쿼리 처리 시간이 오래 걸릴 수 있다. 반면 역색인은 정색인을 역전시켜 단어별로 해당 단어를 포함하는 문서를 나열하는 방식으로, 쿼리 처리 속도를 크게 향상시킨다.^[6]

정색인의 구조는 다음과 같다.

문서 ID	포함된 단어 ID와 위치
1	(1 at 1, 20, 500) (2 at 10, 45, 3445)
2	(1 at 3, 50, 60) (2 at 100, 120, 130, ..)
3	etc

역색인의 구조는 다음과 같다.

단어 ID	해당 문서 ID
1	1, 3, 4, 5
2	2, 3, 4
3	etc

역색인을 사용하면, 특정 단어를 포함하는 문서를 빠르게 찾을 수 있어 검색 응답 시간을 단축할 수 있다.

5. 압축

역색인 파일은 크기가 커질 수 있으므로, 저장 공간 효율성을 높이기 위해 압축 기법이 사용된다. 역색인 압축과 비트맵 압축은 별개의 연구 분야로 개발되었으나, 나중에야 본질적으로 동일한 문제를 해결한다는 사실이 밝혀졌다.^[7]

참조

_[1] 서적 The Art of Computer Programming Addison-Wesley
_[2] 학술지 Extended Boolean information retrieval https://doi.org/10.1[...] 1983-11-00
_[3] 학술지 Inverted files versus signature files for text indexing Association for Computing Machinery 1998-12-00
_[4] 서적 Modern information retrieval Addison-Wesley Longman
_[5] 학술지 Inverted Files for Text Search Engines Association for Computing Machinery 2006-07-00
_[6] 서적 Information Retrieval: Implementing and Evaluating Search Engines http://www.ir.uwater[...] MIT Press 2010-08-08
_[7] 웹사이트 An Experimental Study of Bitmap Compression vs. Inverted List Compression https://doi.org/10.1[...] Association for Computing Machinery 2017-05-09
_[8] 학술자료
_[9] 학술자료

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com