[대규모 서비스를 지탱하는 기술] 24장. 검색 시스템의 아키텍처

June·2021년 12월 28일
0

검색 시스템이 완성되기까지

  • 크롤링
  • 저장
  • 인덱싱
  • 검색
  • 스코어링
  • 결과표시

전문 검색의 종류

grep형

검색 대상 문서를 처음부터 전부 읽어가는 가장 단순한 아키텍처다.
검색 대상인 텍스트의 길이를 m, 검색하려는 검색어의 길이를 n이라고 했을 때 O(mn)만큼 걸린다. 이는 검색 처리로서 상당히 느리다. KMP(Knuth-Morris-Pratt)법이나 BM(Boyer-Moore)법 등 개선 방법이 있지만, 시간이 많이 걸린다.

  • 단순 검색 -> O(mn), text; m, word: n
  • KMP 법 -> O(m+n)
  • BM 법 -> 최악일 때 O(mn), 최선일 때 O(n/m)

grep형의 장점은 즉시성이 좋다는 점이다. 문서가 갱신되더라도 바로 검색할 수 있다. 또한 검색 누락이 없다. 또한 병렬화하기 매우 간단하다. 예를 들면 매우 긴 문서를 검색하고자 할 때 분할해서 병렬로 검색해도 되고, 혹은 아호-코라식으로 검색하고자 하는 단어를 하나의 오토마톤에 모아서 그 안으로 문서를 집어 넣으면 복수 검색어를 한 번에 검색할 수 있다.

Suffix형

Suffix형은 검색 대상 전문을 검색 가능한 형태로 가지고 있다. 데이터 구조로는 Trie나 Suffix Array, Suffix Tree 등이 있다.

문서를 검색 가능한 형태로 가지고 있으며, 전부 메모리에 올릴 수 있는 형태가 된다. 다음에 설명할 역 인덱스는 문서 전체를 가지고 있는게 아니므로 이 점이 차이점이다.

역 인덱스형

단어(term)과 문서를 연관짓는 것이다. 역 인덱스 방식의 특징은 역 인덱스를 문서와는 별개로 만들어야 한다는 점이다. 즉, 검색하기 이전에 인덱스를 전처리로 만들어야 하는 것이다 이 때문에 grep과 같이 문서가 변경되면 바로 검색결과도 바뀌는 형태의 구현은 할 수 없다.

따라서 즉시성은 떨어지지만, 인덱스를 압축함으로써 컴팩트하게 가져갈 수 있고, 대규모하기 쉽다.

0개의 댓글