텍스트 검색 시스템에서 효율적인 정보 검색을 위해 다양한 인덱싱 기법이 활용됩니다. 그중에서도 역인덱스(Inverted Index)와 시그니처 파일(Signature File)은 가장 널리 알려진 텍스트 검색 인덱싱 기술입니다.
역인덱스(Inverted Index)
역인덱스는 해시 인덱스 또는 B+-트리 인덱스로 구성된 두 개의 테이블, 즉 document_table과 term_table을 유지 관리하는 인덱스 구조입니다.
- document_table: 문서 레코드들의 집합으로, 각 레코드는
doc_id와posting_list두 필드를 포함합니다. posting_list는 해당 문서에 등장하는 단어(또는 단어에 대한 포인터) 목록으로, 일정한 관련도 측정 기준에 따라 정렬됩니다. - term_table: 단어 레코드들의 집합으로, 각 레코드는
term_id와posting_list두 필드를 포함합니다. 여기서 posting_list는 해당 단어가 등장하는 문서(레코드) 식별자 목록을 지정합니다.
역인덱스를 활용하면 주어진 단어 집합과 연관된 모든 문서를 찾을 수 있으며, 반대로 주어진 문서 집합과 연관된 모든 단어를 찾는 데에도 사용할 수 있습니다. 예를 들어 특정 단어 집합과 관련된 문서를 찾으려면, 먼저 term_table에서 각 단어에 대한 문서 식별자 목록을 조회한 뒤, 이 목록들을 서로 교집합하여 관련 레코드 집합을 얻을 수 있습니다.
역인덱스의 장단점
역인덱스는 실제 현업에서 폭넓게 사용되고 있으며 구현이 비교적 간단하다는 장점이 있습니다. 하지만 포스팅 리스트가 매우 길어질 수 있어 저장 공간 요구량이 상당히 커질 수 있습니다. 또한 동의어(synonymy), 즉 전혀 다른 단어가 같은 의미를 갖는 경우나 다의어(polysemy), 즉 하나의 단어가 여러 의미를 갖는 경우를 처리하는 데 한계가 있습니다.
시그니처 파일(Signature File)
시그니처 파일은 데이터베이스의 각 레코드에 대한 시그니처 데이터를 저장하는 파일입니다. 각 시그니처는 단어를 정의하는 고정된 크기(b비트)를 가집니다.
간단한 인코딩 방식은 다음과 같습니다. 먼저 레코드 시그니처의 모든 비트를 0으로 초기화합니다. 그런 다음 해당 비트가 나타내는 단어가 레코드에 등장하면 그 비트를 1로 설정합니다. 시그니처 S2에서 설정된 모든 비트가 S1에서도 설정되어 있다면, 시그니처 S1은 S2와 일치(match)한다고 판단합니다.
일반적으로 사용 가능한 비트 수보다 단어 수가 더 많기 때문에 여러 단어가 동일한 비트로 매핑되는 다대일(many-to-one) 매핑이 발생합니다. 이로 인해 쿼리 시그니처와 일치하는 레코드가 반드시 쿼리의 키워드 집합을 포함하지는 않으므로 검색 비용이 증가하게 됩니다. 따라서 일치하는 레코드들을 실제로 조회한 후 파싱하고 어간 추출(stemming)을 거쳐 최종 검증해야 합니다.
검색 성능을 개선하려면 먼저 빈도 분석(frequency analysis), 어간 추출(stemming), 불용어(stop word) 필터링을 수행한 후, 해싱(hashing) 기법과 중첩 코딩(superimposed coding) 기술을 활용하여 단어 목록을 비트 표현으로 인코딩하는 방법을 사용할 수 있습니다.