역색인 (Inverted Index)

문헌정보학

한 줄 정의: 각 색인어를 키로 하여 그 색인어가 등장하는 문헌들의 목록(포스팅 리스트)을 연결해 놓은 자료구조로, 대규모 문헌집단에서 특정 색인어를 포함한 문헌을 빠르게 찾아낼 수 있게 해주는 정보검색시스템의 핵심 색인 구조이다.

쉽게 풀면

'이 단어는 어떤 문서들에 들어있다'는 목록을 미리 만들어 두어서, 검색할 때 전체 문서를 다 뒤지지 않고도 빨리 찾을 수 있게 해주는 구조이다.

왜 중요한가

역색인은 각 용어가 어느 문서에 나타나는지를 미리 기록해 두어 질의어로 문서를 즉시 찾을 수 있게 하는 자료구조로, 사실상 모든 전문 검색 시스템의 핵심입니다. 검색 속도와 저장 공간의 균형, 갱신 비용이 시스템 설계의 주요 고려사항입니다. 웹 검색엔진처럼 초당 수만 건의 질의를 처리해야 하는 환경에서 역색인은 사실상 유일하게 실용적인 색인 구조로 자리잡았다. 실시간으로 새 문서가 추가되는 서비스에서는 역색인을 점진적으로 갱신하는 기법이 별도로 요구된다.

논문에서는 이렇게 쓰입니다

검색엔진은 대규모 웹문서를 실시간으로 처리하기 위해 색인어별 포스팅 리스트를 압축한 역색인 구조를 사용한다.

검색엔진이 방대한 문서량을 빠르게 처리하기 위해 역색인이라는 자료구조를 활용함을 설명하는 문장이다.

"질의 처리 속도를 높이기 위해 포스팅 리스트에 델타 인코딩과 가변 길이 압축 기법을 적용하였다."

역색인의 목록 부분을 더 작은 용량으로 압축해 저장하고 불러오는 속도를 높이는 기법을 설명한 문장입니다.

조금 더 깊게 보면

역색인은 용어 단위 매칭에 최적화되어 있어 의미적 유사성은 포착하지 못하며, 이 한계가 밀집 벡터 색인과의 결합(하이브리드 검색)으로 보완되고 있습니다. 위치 정보를 포함하는지에 따라 구문 검색 가능 여부와 색인 크기가 크게 달라집니다. 역색인은 각 용어가 어느 문서에 몇 번 나타나는지를 기록한 목록 구조로, 특정 단어를 포함한 문서를 찾을 때 전체 문서를 순차 탐색할 필요 없이 해당 용어의 항목만 조회하면 되어 검색 속도를 획기적으로 높인다. 등장 위치까지 함께 기록해 두면 인접한 단어들의 구문 검색도 지원할 수 있다. 분산 검색시스템에서는 역색인 자체를 여러 서버에 나누어 저장해 대규모 컬렉션에서도 빠른 응답 속도를 유지한다.

주의할 점

역색인은 색인 구축 이후 문헌이 추가·삭제될 때 갱신 비용이 발생하므로 대규모 동적 컬렉션에서는 색인 갱신 전략이 중요하다. 색인 크기가 문서 집합의 크기에 비례해 커지므로, 대규모 컬렉션에서는 압축 기법과 분산 저장이 함께 요구된다는 점에 유의해야 한다.