나의 큰 O는 log x야

'포도 주스'라고 검색한다면 '포도'가 포함된 문헌과 '주스'가 포함된 문헌의 교집합을 보여줄수도 있지만(이는 고전적인 불리언 검색 모형에서의 AND 연산자를 이용하는 것과 동일합니다), 정확하게 '포도'라는 단어 다음에 '주스'라는 단어가 등장하는 문헌만을 보여줄 수도 있죠. 후자의 경우를 구문 검색(Phrase Query)이라고 합니다. 단어 하나 만으로는 원하는 결과를 정확하게 얻지 못할 수 있기 때문에 사람들은 두 단어 이상의 구문을 질의어로 입력하는 경우가 많습니다. 문제는 고전적인 불리언 검색 모형에서는 구문 검색 시 구문의 길이가 길어질수록 검색 속도가 현격하게 떨어진다는 것입니다. 당연히 이를 극복하기 위한 방법들이 제시되었겠죠? 본 포스팅에서는 다음 논문의 내용을 기반으로 큰 성능 손실 ..

수업노트 2018. 10. 14. 18:44

정보 검색 모형 중 벡터 공간 모형(질의와 문헌을 벡터 공간 상의 좌표로 표현하고, 검색 시 질의와 문헌 좌표 간의 코사인 유사도를 계산하여 정렬하는 모형)은 안정적이면서 뛰어난 성능 덕분에 현재 다양한 검색 엔진에 널리 쓰이고 있습니다. 문제는 두 좌표 상의 코사인 유사도를 계산하는 것이 생각보다 비싼 연산이라는 것입니다. 벡터 공간의 dimension이 V일 경우, 총 V번의 곱셈과 덧셈이 필요하죠. 이게 모든 쿼리-문헌에 대해 계산되어야 전체 문헌에 대한 순위화가 가능하므로, 문헌이 총 D개라고 할 경우 최소 D*V 번의 곱셈이 필요합니다. 문헌 갯수 D가 커질수록 덩달아 V도 커질테니, 사실상 그 전체 연산 비용은 어마어마하게 늘어날 것이라고 예상할 수 있겠습니다. 이는 대량의 정보를 처리해야하는..

수업노트 2018. 10. 13. 14:57