빠른 구문 검색을 위한 인덱싱 기법

'포도 주스'라고 검색한다면 '포도'가 포함된 문헌과 '주스'가 포함된 문헌의 교집합을 보여줄수도 있지만(이는 고전적인 불리언 검색 모형에서의 AND 연산자를 이용하는 것과 동일합니다), 정확하게 '포도'라는 단어 다음에 '주스'라는 단어가 등장하는 문헌만을 보여줄 수도 있죠. 후자의 경우를 구문 검색(Phrase Query)이라고 합니다. 단어 하나 만으로는 원하는 결과를 정확하게 얻지 못할 수 있기 때문에 사람들은 두 단어 이상의 구문을 질의어로 입력하는 경우가 많습니다.

문제는 고전적인 불리언 검색 모형에서는 구문 검색 시 구문의 길이가 길어질수록 검색 속도가 현격하게 떨어진다는 것입니다. 당연히 이를 극복하기 위한 방법들이 제시되었겠죠? 본 포스팅에서는 다음 논문의 내용을 기반으로 큰 성능 손실 및 저장 용량 손실 없이 구문 검색을 구현하는 방법에 대해 정리해보도록 하겠습니다.

Williams, H. E., Zobel, J., & Bahle, D. (2004). Fast phrase querying with combined indexes. ACM Transactions on Information Systems (TOIS), 22(4), 573-594.

위치 정보가 포함된 역색인(inverted index with term position)

가장 기본적인 방법은 역색인 파일에 용어의 위치정보도 함께 포함하는 것입니다.

용어(Vocabulary)	빈도	문헌 목록(Postings Lists)
포도	22	11(2, 14, 26), 23(7, 10), 31(1), ...
주스	10	11(3, 29), 32(1, 9), ...

위는 전형적인 역 색인 파일의 구조입니다. 각각의 단어들에 대해 그 빈도가 저장되어 있고, 그 용어들이 출현하는 문헌의 목록을 나열합니다. 여기에 용어가 문헌 내에서 어떤 위치에 등장했는지도 함께 저장합니다. 문헌 목록의 괄호 안에 있는 값들이 용어의 출현 위치입니다.

그러면 '포도 주스'라는 질의어가 입력되면 질의어를 분할하여, 위치를 매겨주고 (포도-1, 주스-2), 문헌 내의 출현 위치와 질의어 내의 출현 위치의 차이를 계산하여 그 값이 같은 경우만 일치하는 것으로 처리하면 됩니다.

예를 들어 '포도'는 1번 문헌의 2, 14, 26번 위치에 등장하므로, 후보 목록을 다음과 같이 생성합니다. 

(문헌, 상대 위치) : (11, 2-1), (11, 14-1), (11, 26-1), ...

그리고 '주스'에 대해서도 마찬가지로 수행합니다.

(문헌, 상대 위치) : (11, 3-2), (11, 29-2), ...

(11, 1)이 '포도'와 '주스'에서 일치하므로, 11은 일치하는 문헌입니다.

이 방법의 장단점은 다음과 같습니다.

장점: 역색인 파일에 위치 정보만 추가하면 되므로, 비교적 공간 사용량이 적다

단점: 속도가 너무 느리다

불용어를 제거한 역색인 기법

구문 검색 시 자주 쓰이는 단어인 불용어들을 사전에 제거하고 일치 여부를 검토하는 변형된 기법입니다. 이 방법은 구문 검색 중 많은 시간이 불용어 등의 일치 여부를 계산하는데 걸린다는 것을 바탕으로 이를 줄이기 위해 묘수를 떠올리것이라고 할 수 있습니다.

구문의 길이가 길어질수록 불용어를 제거하지 않은 것에 비해 2~10배 이상의 속도 향상이 있었습니다만, 불용어가 포함된 질의들을 제대로 처리할 수 없다는 치명적인 문제가 있습니다.

장점: 기존 역색인 기법의 장점 + 빠른 속도

단점: 불용어를 검색에 포함시킬수 없으므로, 정확도 상실

부분 구문 색인(Partial Phrase Index)

다른 접근 방법은 아예 구문을 묶어서 단어처럼 색인하는 것입니다. 그러니깐 문헌을 색인할 때 '포도 주스'가 나오면 '포도'와 '주스'로도 색인하지만, 동시에 '포도 주스'로도 색인하는 것이죠. 그러면 역색인 기법을 통해 별도의 위치 정보 없이도 '포도 주스'를 바로 검색할 수 있습니다. 단, 길이가 2인 모든 구문을 색인한다면, 최악의 경우 전체 색인의 크기는 한 단어로 구성된 색인의 제곱이 됩니다. 길이가 3 이상인 경우도 포함하려면 기하급수적으로 색인 용량이 커지겠죠.

따라서 모든 조합가능한 구문을 색인한다는 것은 물리적으로 불가능합니다. 자주 쓰이는 구문들에 대해서만 색인을 실시하고, 그렇지 않은 경우는 기본적인 역색인 기법을 사용하는 방식을 써야 실현가능성 있는 방법이 되겠죠. 이를 부분 구문 색인 기법(Partial Phrase Index)이라고 부릅니다.

이 경우의 검색 전략은 크게 2가지가 됩니다.

1. 입력된 질의어 구문이 색인어 내에 존재하는지 검색
2. 존재한다면, 해당 색인의 문헌 목록을 가져와 출력
3. 그렇지 않다면, 구문을 분할하고 각 용어별 역색인을 이용하여 구문 검색을 실시

일종의 캐시 메모리랑 비슷한 느낌이 되겠습니다. 이 기법의 성능을 좌우할 키는 자주 쓰이는 구문을 얼마나 색인에 포함시킬 것이냐 입니다. 만약 너무 많은 양을 색인에 포함시키면, 전체 색인의 크기가 커져서, 색인 용량이 증가하고 동시에 색인 검색 속도도 떨어집니다. 반대로 너무 적은 양을 색인에 포함시키면, 구문 색인으로 얻을 수 있는 성능 향상이 거의 미미하게 될 것입니다.

논문의 실험결과에 따르면, 적절한 수의, 자주 쓰이는 구문 질의를 색인에 포함하였을 경우, 길이가 짧은 (2~3단어 이하) 구문 검색에 대해서는 10~30% 정도의 속도 향상이 있었지만, 그보다 긴 길이에 대해서는 거의 효과가 없었습니다.

장점: 색인에 포함된 구문에 대해서는 빠른 검색이 가능

단점: 색인의 크기가 크게 증가하며, 색인에 포함되지 않은 구문들에 대해서는 속도 향상이 미미

다음 단어 색인(Nextword Index)

이 방식은 일종의 트리 형태로 색인을 구성합니다. 단어 3개로 이뤄진 구문 A-B-C가 있다고 하면 먼저 A의 자식으로 B를 추가하여, A-B에 대한 색인을 실시하고, 다음에 B에 대해 C를 자식으로 추가하여, B-C에 대해 색인을 실시하는 방식입니다.

첫번째 단어(Firstword)	다음 단어(Nextword)	빈도	문헌 목록(Postings Lists)
포도	주스	22	11(2, 14, 26), 23(7, 10), 31(1), ...
	나무	12	16(3, 15, 27), 29(7, 10), 31(1), ...
주스	가게	10	11(3, 29), 32(1, 9), ...
	설탕	9	14(3, 29), 36(1, 9), ...

'포도 주스'와 같이 길이가 2인 구문의 경우 먼저 '포도'를 찾고, '포도'의 자식 중에서 '주스'를 찾아서 그 문헌목록을 반환하면 바로 검색이 끝납니다. 반면 '포도 주스 가게'처럼 길이가 3인 구문의 경우는 '포도'를 찾고 그 자식 중에서 '주스'를 찾아 그 문헌목록을 구하고, 또 '주스'를 찾고 그 자식 중에서 '가게'를 찾아서 위치가 일치하는 문헌만을 골라내면 됩니다.

첫번째 단어의 경우는 기존의 역색인과 동일한 크기를 가질 것이고, 각 첫번째 단어들이 자신만의 다음 단어를 가지므로 전체 색인 크기는 제곱이 될것만 같습니다만, 실제로 조합가능한 모든 단어가 전부 구문이 되는 것은 아니기에, 색인 크기는 약 2배정도가 된다고 합니다.

특히, 흔히 쓰이는 단어들이 포함된 색인의 경우 이 방법을 통해 큰 성능 향상을 얻을 수 있었고, 당연하게도 흔히 쓰이는 단어들로 구성된 구문이 많기 때문에 전반적인 속도는 단순한 역색인 기법에 비해 10배 이상 빨라질 수 있었다고 합니다.

장점: 빠른 속도로 검색이 가능

단점: 색인의 크기가 2배 이상 불어남

각자 기법들이 장단점이 다르니깐 서로 힘을 합쳐 잘해보자

지금까지 크게 3가지 기법을 살펴보았는데, 각자의 장단이 명확합니다. 그러면 각각의 기법을 결합하여 서로의 단점을 가려주도록 하면 어떨까요? 이것이 본 논문에서 제안하는 바입니다.

1. 먼저 자주 쓰이는 구문들에 대해서는 부분 구문 색인 기법을 적용합니다.
2. 그렇지 않은 경우, 구문의 첫번째 단어가 자주 쓰이는 용어이면 다음 단어 색인을 적용합니다.
3. 위의 두 가지의 경우가 아니거나, 질의어가 한 단어일 경우 일반 역색인 기법을 적용합니다.

이 합쳐진 방법은 크게 두 가지 파라미터에 의해 성능 및 저장용량이 영향을 받습니다. 

1. 부분 구문 색인을 적용할 구문의 개수
2. 다음 단어 색인을 적용할 첫번째 단어의 종류 개수

논문에서는 여러 실험을 통해 적절한 값을 구했는데, A는 상위 1만개, B는 첫번째 단어 24종으로 두었을 경우, 실행속도는 단순 역색인 기법에 비해 1/4에 불과하면서, 용량은 26% 추가적으로 밖에 쓰지 않았다고 보고하고 있습니다.

최적의 A, B값은 데이터베이스나 질의의 특성에 따라 달라지겠지만, 3가지 기법을 잘 적용하여 최적화를 잘 이뤄냈다고 볼 수 있겠습니다. 이런 기법 덕분에 오늘도 빠르고 편하게 구글링하고 네이버 검색을 할 수 있는거겠죠?