컨텐츠검색 스토리(2) – 컨텐츠검색은 어떻게 만들어질까 라는 글을 보다가 쿼리 자동완성에 마이닝 기술과 클러스터링 기술이 들어 갔다고 해서 생각 좀 해봤다.

문제의 그림….

요걸 보니까.. 딱 생각나는 방법이 있다.

쿼리의 유형을 빠르게 분석하기 위해서는 형태소 분석의 방법을 쓰는게 좋을까?
개인적으로는 n-gram방법이 효율적이라고 생각한다.  특히나 다국어나 인터넷 신조어 처리를 해야 한다면 말이다.
위의 결과를 보자면 “꽃보다남자”라는게 클러스터링 되어서 미리 쿼리 자동완성 데이터 셋에 들어가 있음으로 해서 자동완성에 대한 complexity를 줄이는 역할을 했을 것이다. 이런식의 전처리를 하지 않으면 edit distance 알고리즘 복잡도상으로 봤을때 평균 n^2의 복잡도로 수많은 쿼리 로그를 헤집어 보는 결과를 가져올 것이다. ( trie 구조를 쓰면 어느정도 실시간 리소스를 줄일 수 있겠지만…)
따라서 미리 클러스터링을 해놓는 전처리 작업이 필요할것이다. 그래서 아마도 네이버 블로그에서 클러스터링 방법을 자동완성에 썼다고 하지 않았나 유추해 본다.

예상하는 방법은 이렇다. ㅋㅋ ^^;

가장 최근의 쿼리 셋에서 각각의 쿼리에 대한 n-gram을 긴것부터 차례대로 뽑아서 다음에 이미 들어온 쿼리 로그를 look up해서 최장매칭 부분집합의 count를 구해 그 기반으로 클러스터링을 하지 않았을까 한다. 최장 매칭이기 때문에 긴 부분 query가 매칭이 되었을 경우  그 sub string에 대한 look up은 생략된다.
일단 이렇게 최장 매칭 sub string으로 묶어 놓으면 대략적인 클러스터링은 끝이 난다. 물론 작업을 하기 전에 쿼리에 대한 전처리도 필요하겠고, 대상이 되는 쿼리셋에 대한 약간의 선별작업도 있을것이다.
이런식으로 쿼리 마이닝을 해보면 “꽃보다남자”라는 룰은 쉽게 뽑혀지지 않을까 한다.

네이버의 Query 마이닝 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.