IR - Inverted Index(역색인) 컨셉

정보검색(IR)에서 다루는 내용중에 하나인 역색인은 검색엔진이나 혹은 데이터베이스에서 많이 언급된다.

단어(term)가 등장하는 문서(Document)를 찾기 위해 Inverted Index가 고안되었다.

예를 들어 SQL Server에서는 다른 DB와 마찬가지로 컬럼에 적절한 인덱스를 생성하는 경우는 많이 봤을 것이다. 하지만 컬럼이 BLOB Type으로 정의되고 여기에는 책의 내용, 신문 기사 내용, 노래 가사같이 Document가 담겨 있을 수 있다. 그럼 이 컬럼에서는 어떤식으로 내용을 빠르게 찾을 수 있을까?

전에 포스팅한 내용 참고하면 좋을 것 같다. (SQL Server Full-Text Search)
https://parksuseong.blogspot.com/search?q=Full+Text+Search

그럼 색인(Index)와 역색인(Inverted Index)의 차이는 무엇인가?

Inverted Index란 Term의 집합을 dictionary, Term이 등장하는 문서들의 집합을 posting이라고 하면 Dictionary와 posting을 Vector화 하면 찾고자 하는 단어가 어떤 문서에서 등장하는지 쉽게 찾고자 고안되었다. 쉽게 생각하면 목차(색인)와 비슷하지만 동작하는 방식이 조금 다를 뿐이다. 책의 내용이 끝나고 맨 뒤에 단어들이 나와있고 이 단어가 몇 페이지에 나오는지를 알려주는 것을 볼 수 있는데 이것이 Inverted Index(역색인)이다. 즉 Term을 가지고 Document를 찾는 것이다.

Inverted Index를 만드는 방법은 다음과 같다.

1. 문서에서 등장하는 단어(Term, 혹은 token)를 구분해서 리스트를 만든다. (tokenization)
어떠한 Term이 어떤 Doc에 나오는지 찾는 과정이다.

2. 검색 시 무의미한 단어들은 제거하고(조사, 관계사 등) 대소문자, 과거형, 복수형 등을 일반화(Nomalization)시켜주는 과정을 거친다. Stop words, Equivalence class, Lemmatization, Stemming 등을 사용할 수 있다. 언어라는게 근원적으로 룰이니까 뭔가 룰베이스적인 처리가 필요하겠다.

3. Posting을 만든다.(Term, DocID)

4. posting을 sorting한다.

sorting 결과 중복되기도 하고, docID만 다른 것이 존재하는 Term들이 보인다.

5. term의 frequency를 계산하고 Posting을 list로 만든다.
(BRUTUS -> [1,2,4,11] 이런식으로 BRUTUS는 doc1, doc2 doc4 doc11에 등장)

6. 5번까지 작업하면 term List가 dictionary가 되고(dictionary 파일에 저장), document list가 posting list가 된다(이것도 posting 파일에 저장). 그럼 dictionary와 posting이 벡터라고 치면 dictionary를 통해 document를 쉽게 검색할 수 있게 된다.

기본적인 컨셉(?)만 간단하게 정리했다.