inverted index와 full text scan 사이에 존재하는 signature files

대부분 개발자든  누구든지간에 검색의 시발점이 되는것은 색인이라고 생각을 한다.  색인을 만든다고 하면 대부분 역색인(inverted index)를 생각한다.

여기에 정보검색의 초기시절 빠른 색인 속도와 적은 색인 구조로 제안이 되었던 색인(?)구조를 찾아봤다.

이름하여 “Signature File”구조인데 이 구조는 full text search와 inverted index 구조의 사이에 존재하는 개념이라고 생각하면 전체적인 위치를 보기에 쉬울듯 싶다.

사용자 삽입 이미지

모든 문서들을 실제 문서보다 작은 데이터로 인코딩하는것이 이 sign file의 주된 작업이고, 몇몇 특수한 검색엔진에서는 이 sign file을 수 비트 이내로 제한을 해서 유지를 하는것이 목적이다.  그리고 또한 어떤 검색엔진에서는 몇가지 문서 집단을 대표하는 sign file을 생성해서 유지하기도 한다. 문서의 포멧이 일정하고 트리 구조로 표현하기 적합한 문서 집단이라면 여러 문서를 하나의 sign file로 표현해서 계층적으로 접근하는 방법도 한가지 방법이라 생각이 된다.

예를 들어서 문서를 4비트로 표현을 한다고 하고 각 term에 대한 비트를 아래와 같이 할당하고자 한다.

term    h(term)
t1         0101
t2         1010
t3         0011


h라고 표현된 함수는 해싱 함수이다. (블로그는 테이블 표현하기가 너무 귀찮다. ㅜㅜ 위키 플러그인 같은건 없나?)

그리고 문서를 표현해 보자. (or 연산)

d1은  t1을 포함한다.
d2은  t1, t3를 포함한다.
d3은  t1, t2를 포함한다.


문서 signature
d1     0101
d2     0111
d3     1111

t3가 포함된 문서를 검색하고자. 쿼리를 t3로 날려보면 t3는 0011로 표현이 될 것이고 이 쿼리를 and연산으로 각 문서 signature에 날려보면 해당 텀에 대한 문서 집합을 가져올 수 있을것이다. 하지만 d3가 t3를 포함하지 않는데도 검색결과로 나올것임에 뻔하다.
그래서 이런  miss matching 문제 때문에 1024 비트로 문서 비트를 확장하면 오류가 줄어들 것이라는 연구 결과도 있다.

오래된 기술인데 한번 짚어 봤다.
지금 쓰이는지 아닌지는 잘 모르겠지만, 나름 이런 기술도 있구나 하고 알고 있으면 좋을거 같다는 생각이 든다.

나름 생각한 바로는 검색하는 색인어가 한정적이고, 색인 저장 용량에 대한 제한이 심할 경우, 그리고 문서의 삽입 삭제가 빈번할 경우 이 방법을 사용하는것도 고려해볼 만 할거 같다. (책에서 나왔는데 정렬이 필요없기 때문에 parreal processing에 좋다는 이야기도 있다.)
하지만 여러 검색 옵션을 주기가 힘들고, 랭킹 산정하기가 힘들다는 단점도 있다.

CC BY-NC 4.0 inverted index와 full text scan 사이에 존재하는 signature files by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.