전문 검색기술 도전

목차

• 전문 검색기술의 응용범위
• 검색 시스템의 아키텍처
• 검색엔진의 내부 구조
• 정리

전문 검색기술의 응용범위

하테나 서비스는 키워드를 포함하는 블로그를 검색하는 기능을 포함하고 있습니다.

하테나는 이를 구현하기 위해 RDB를 활용했습니다. 누군가가 블로그에 글을 적게되면 글에 포함되어 있는 키워드를 모두 추출합니다. 그럼 '이 블로그는 ㅇㅇ과 ㅁㅁ라는 단어를 포함하고 있어'라고 알게 됩니다. 이 단어와 블로그의 연관성을 데이터베이스의 레코드로서 저장해 둡니다.

다만 이 방식은 확장성 측면에서 낙제점을 받았습니다. 레코드 수가 너무 많아져 검색 시간이 점점 늘어나는 문제를 겪게 됩니다.

그래서 취한 방법은 검색엔진을 만들어 검색함으로 문제를 회피한다. 라는 것이였습니다.

검색 엔진은 다음과 같은 기능을 제공합니다.

• 데이터 전처리: 수집된 데이터를 정규화하고 필요한 형식으로 변환하여 색인화를 위해 준비합니다.
• 색인화: 데이터를 검색 가능한 형식으로 색인화하여 빠른 검색을 지원합니다. 텍스트 데이터의 경우 토큰화, 어근 추출, 불용어 처리 등이 포함될 수 있습니다.
• 역색인 구조: 주로 사용되는 색인 구조로, 용어에 대한 역방향 매핑을 통해 문서의 위치를 색인화합니다. 이렇게 하면 용어를 기반으로 빠르게 검색할 수 있습니다.
• 유사도 측정 알고리즘: 검색된 결과의 유사도를 측정하여 가장 관련성이 높은 결과를 반환합니다. TF-IDF, BM25, 코사인 유사도 등의 알고리즘이 사용됩니다.
• 분산 데이터 저장: 대규모 데이터는 여러 서버에 분산하여 저장되며, 데이터의 안정성과 확장성을 보장합니다.
• 분산 색인화 및 검색: 검색 엔진은 분산 색인화 및 검색을 지원하여 대량의 데이터에 대한 효율적인 검색을 가능하게 합니다.

하테나의 북마크 검색

하테나의 검색 엔진은 개인이 북마크한 개인 데이터로부터 검색하는 시스템입니다.

사용자별로 검색 인덱스를 따로 준비해두고 이를 갱신합니다. 검색할 때는 해당 사용자의 인덱스에서만 검색합니다. 이렇게 인덱스를 타면 검색 시스템을 컴팩트하게 구현할 수 있고, 원하는 요구도 만족할 수 있습니다.

검색 시스템의 아키텍처

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

위의 검색엔진의 기능을 구현하기 위해서 해야할 것은 매우 많습니다.

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

처음에 검색할 대상 문서를 가져와야합니다. 이르 일반적으로 크롤링이라고 합니다. 대상 문서가 웹에 있다면 웹 크롤러를 만들어서 대량 문서를 가져오는 작업이 필요합니다.

그 다음에는 가져온 문서를 어떻게 저장할 것인가 라는 문제가 있습니다. 데이터 베이스의 분산도 생각해야 합니다.

그리고 가져온 문서로부터 인덱스를 구축합니다. 인덱스를 타야지 검색이 빨라지기에 검색엔진에서 인덱스는 필수입니다.

검색에서는 검색 쿼리를 포함하는 문서가 검색결과로 반환되는데, 그 순서를 지정하는 스코어링도 중요합니다.

전문 검색의 종류

전문 검색의 아키텍처에는 종류가 꽤나 많습니다. 저자는 책에서 3가지의 유형을 소개합니다.

• grep형
• Suffix형
• 역 인덱스형

grep형

grep형은 검색 대상 문서를 처음부터 전부 읽어가는, 말하자면 가장 단순한 구조입니다.

전부 읽어가면 어딘가에서는 해당 문서가 발견되기 때문입니다. 검색 대상인 텍스트 길이를 m, 검색어의 길이를 n이라고 했을 때 이는 O(mn)만큼 걸리게 됩니다.

물론 KMP법, BM(Boyer-Moore)법 등 어느정도 계산량을 개선한 방법을 활용하면 이보다 줄어들 수 있지만, 데이터가 늘어나면 힘겨워 질 것이라 상상할 수 있을 것입니다.

• KMP법 : O(m+n)
• BM법 : 최악 O(mn), 최선 O(n/m)

단순 무식하지만 사실 좋은점도 많이 있습니다. 이는 즉시성이 좋으며 검색 누락이 없습니다. 또한 병렬화하기가 매우 간단합니다.

정리하자면 이는 검색 대상을 처음부터 전부 읽으며, 즉시성이 좋고, 검색누락이 없으며, 병렬화나 쿼리 확장이 용이합니다.

Suffix형

Suffix형은 검색 대상 전문을 검색 가능한 형태로 가지고 있는 것입니다. 데이터 구조로써는 Trie, Suffix Array/Tree를 생각할 수 있습니다.

---

Suffix Array란??

이는 접미사 배열이라고도 하며 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것입니다.

물론 이 말이 곧이 곧대로 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현됩니다.

아래는 'alohomora'라는 단어의 Suffix Array를 나타냅니다.

i	A[i]	S[A[i]···]
0	8	a
1	0	a l o h o m o r a
2	3	h o m o r a
3	1	l o h o m o r a
4	5	m o r a
5	2	o h o m o r a
6	4	o m o r a
7	6	o r a
8	7	r a

alohomora의 Suffix Array는 803152467을 의미합니다.

• Q. 그래서 접미사 배열을 어디에 어떻게 쓰나요?

접미사 배열을 이용하면 문자열 검색을 최적화할 수 있습니다.
접미사 배열을 이용한 문자열 검색은 짚더미 H가 바늘 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용합니다.

• H: "alohomora"에서 N: "homo"를 찾고 있다.
• N: "homo"는 A[2] "homora"의 접두사이다.

모든 부분 문자열에 대해 이 속성이 성립함을 알 수 있습니다. 이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다.

접미사 배열의 길이는 항상 |H|이므로 이진 탐색의 내부는 O(log|H|)번 수행됩니다. 각 문자열 비교에 O(|N|) 시간이 걸리기 때문에 이 이진 탐색의 수행 시간은 O(|N|lg|H|)이 됩니다.

---

Suffix형은 문서를 전부 메모리에 올릴 수 있는 형태로 만들고 이를 통해 빠르게 검색합니다. 이 또한 데이터가 커지며 이론적으로는 검색이 가능해진다는 것을 알지만, 실제 이 구조를 가진 엔진은 좀처럼 구현하기 흼듭니다.

역 인덱스형

역 인덱스형은 주류로 사용되는 검색 기법이며, 간단히 말하자면 단어와 문서를 연관짓는 인덱스를 활용하는 것 입니다.

역 인덱스 방식의 특징으로는 역 인덱스를 문서와는 별개로 만들어야 한다는 점입니다. 즉, 검색하기 전에 인덱스를 전처리로 만들어야 합니다.

이러한 특징 때문에 즉시성의 측면에서는 뛰어나지 못합니다. 구현방법에 따라서는 검색누락이 생길 수도 있습니다.

하지만 이는 실제로 인덱스를 압축함으로써 컴패트하게 가져갈 수 있고, 대규모화하기도 쉽습니다.

• Inverted index를 그대로 번역하여 역 인덱스라고 부릅니다.

참고) Elastic Search의 경우도 내부에 역인덱스를 구성하여 검색 속도를 최적화합니다.

검색엔진의 내부 구조

역 인덱스의 구조

역 인덱스의 내부구조는 크게 Dictionary와 Postings라는 두 파트로 나뉩니다.

예제를 통해 무엇을 의미하는지 알아봅시다.

• 문서 정보

doc1 : 하테나의 마스코트인 시나몬은 도쿄에 없다.
doc2 : 홋카이도에 살았던 kurain
doc3 : 하테나교토의 시나몬에는 식숙한 kurain
doc4 : 하테나는 창업 9년째인 벤처다.
doc5 : 도치키현의 명물은 딸기다.

• 역 인덱스 테이블

하테나 -> 1, 3, 4
시나몬 -> 1, 3
교토 -> 3
도쿄 -> 1
홋카이도 -> 2
kurain -> 2, 3

단어의 집합을 Dictionary라고 합니다. 그리고 각 단어를 포함하고 있는 문서는 몇 번인지를 나타낸 것이 바로 Postings입니다.

이것이 바로 역 인덱스 입니다. = Dictionary + Postings

'교토'로 검색하면 3번만 포함되어 있다거나, 인덱스를 보면 바로 어떤 문서에 어떤 단어가 포함되어 있는지 알 수 있습니다.

그렇다면 Dictionary는 어떻게 만드나요?

모든 단어에 대해 Dictionary를 만드는 방법은 효율적이지 않습니다. 이에 따라 어떤 단어를 선택하는지에 대한 문제가 발생합니다.

또한 영어같은 경우는 공백으로 구분해서 문장이 쓰이므로 공백으로 구분하면 문서를 단어로 분해할 수 있습니다. 그러나 일본어의 경우 공백이 없고 단어의 분기점이 있는지 모른다는 문제가 있는데, 어떻게 활용하면 좋을까요?

1. 사전을 이용하는 방법

사전을 활용하면 사전이 곧 검색 시스템의 단어공간이 됩니다. 즉 사전에 들어 있는 단어만 검색할 수 있습니다. 하테나의 경우는 자체키워드 40만개 + 위키피디아의 단어 60만개를 활용해 약 100만개 정도의 단어 검색을 지원합니다.

2. 형태소 분석을 이용하는 방법

복숭아나 자두나 모두 복숭아과입니다.(일본의 말장난)
スモモモモモモモモモノウチ

라는 일본어 문장이 있을때 이 때 スモモ, モモ 등으로 품사를 분해하는 것을 유형파악과 분리라고 합니다. 이 원리에 따라 세세하게 나눈 각 단어를 형태소라고 합니다.

유형파악과 분리에 의해 형태소로 분할하는 것이 형태소 분석기의 주된 기능입니다.

형태소 분석기에 의해 분리된 형태소는 다음과 같습니다.

スモモモモモモモモノウチ

スモモ(자두) - 명사
モ(나) - 조사
モモ(복숭아도) - 명사
モ(도)) - 조사
モモ(복숭아과) - 명사
ノ(의) - 조사
ウチ(일부) - 명사

이와 같이 형태소 분석기는 문장을 형태소로 나눠서 그 품사를 추정합니다. 이런 분석기는 관련 패턴을 기계학습을 통해 학습시킵니다.

검색 누락

위와 같은 방식으로 단어를 지정할 수 있지만 그럼에도 검색누락이 발생할 수 있습니다.

예를 들어 Gears of War이라는 게임 타이틀이 있습니다. 이에 따라 Gears 발매일이라고 And 검색해보면 정확하게 Gears of War발매일이 검색되게 됩니다.

그러나 Gear 발매일이라고 검색했을 시 Metal Gear라는 게임의 발매일이 검색되게 됩니다. 이는 Gear라는 단어가 사전에 없고, Gears라는 단어는 역인덱스로 Gears of War로만 이어져 있음으로 검색되지 않는게 당연했습니다.

이러한 방식은 검색엔진의 설계나 사상에 좀 맞지 않는 것 같습니다.

집, 주택, 건물, 주거지와 같은 동의어의 경우 또한 같이 검색되지 않으면 검색 누락이 발생할 수 있습니다.

n-gram을 term으로 다루기

n-gram이란 텍스트를 n자씩 잘라낸 것을 의미합니다.

• abracadabra의 3-gram
  • abr, bra, rac... 등등

3글자 씩 잘라낸 것을 트라이그램, 2글자 씩 잘라낸 것을 바이그램이라고 하기도 합니다.

n-gram 이용해 연인덱스를 구성한다면 검색 누락을 방지할 수 있습니다.

하테나의 마스코트인 시나몬 -> '하테', '테나', '나의', '마스', '스코', '코트' ....

쿼리도 n-gram으로 분할하여 검색하기

사용자가 '하테나'를 입력하면 '하테', '테나'로 분할하여 검색을 수행하고, 양쪽에 포함된 공통문서를 교집합(intersection)하여 검색을 진행합니다.

이러한 방법은 지금까지도 이어지며 ElasticSearch - N-gram tokenizer에서도 확인 가능합니다.

n-gram 분할 문제와 필터링

동경소녀를 검색했을 때 도쿄타워가 검색된다면 난처할 것입니다. 따라서 보통 검색겨로가가 나온 후에 필터링을 수행합니다. 실제 검색결과를 조사해서 동경소녀라는 검색어가 포함되어 있는지 확인하는 것입니다.

grep형과 동일한 검색시간이 소요되게 되므로 하테나에서는 제목, 코멘트, URL을 대상으로만 필터링을 수행하고, 본문은 n-gram을 활용하지 않고 단어 기반을 사용합니다.

검색어의 재현률과 적합률

검색 엔진의 척도를 파악할 떄 쓰이는 단위를 의미합니다.

• 재현율 : 올바른 결과를 반환했는가?
  • 올바른 결과의 수 / 반환한 결과 총 수
• 재현율 : 이것저것 망라해서 반환했는가?
  • 올바른 결과의 수 / 적합한 결과 총 수

Postings 작성 법

Postings란 해당 단어를 포함하는 문서 번호 또는 ID를 지니고 있는 배열입니다.

Dictionary	Postings
하테나	1, 3, 4
시나몬	1, 3
교토	3
도쿄	1
홋카이도	2
kurain	2, 3

위의 예에서는 단순하게 문서ID만을 보유하고 있는데, 단어가 해당 문서 내의 어느 위치에 출현하는지 그 출현위치도 저장하는 경우도 있습니다. 이것을 Full Inverted Index라고 합니다.

문서 ID만 저장하는 - Inverted File Index

출현 위치를 저장하지 않으면 처음에 본 것처럼 단어에 대응하는 문서ID가 나열된 배열에 불가하므로 VB Code를 활용해 압축할 수 있습니다.

더해 역 인덱스라는 것은 결국엔 key-value스토어로 저장하기에 적합합니다. 따라서 O(1)로 인덱스에 접근할 수 있습니다.

정리

이상으로 전문 검색기술을 만들기 위한 이론과 구조를 알아봤습니다.

본 챕터에서 알아가면 좋을 것은

• 검색엔진의 동류에 대하여
  • 역 인덱스형
  • grep형
  • Suffix형
• 역인덱스의 구조
  • Dictionary, Postings
    • Dictionary에 들어갈 단어 정하기
    • Postings 구성 방법

정도가 있을 것 같으며 책에서 설명한 대부분의 이론들 또한 ElaticSearch에도 사용되고 있음으로 이또한 같이 알아두면 좋을 듯 합니다.