이전 포스팅에 Edit Distance를 설명하고 Lucene의 Fuzzy Query에 대해서 설명을 했는데, 곰곰히 생각을 해보니 Google에서 Edit Distance를 “이것을 원하셨습니까?”에서 사용하지 않을까 생각을 해봤다.

(주의 : 전적으로 나의 생각이고 이렇게 하고 있을수도 아니면 다른방법을 쓸수도 있다.)

우리가 단어를 잘못 입력했다는것은 대부분 1글자내지 2글자의 삭제, 갱신, 삽입의 연산 내에 있다는 가정하에…..

1) Delete, Update, Insert에 대한 cost를 1로 모두 잡는다.

2) 색인 DB에 있는 히트수(임계치) 몇번 이상의 색인어에 대해서만 입력된 쿼리와의 Edit Distance를 계산한다.(모두 계산할 경우에 상당히 많은 리소스를 먹게 되므로 이 부분에 대한 적절한 임계치 설정이 중요할거 같다.)

3) 그것들의 cost에 대해서 힙소트를 해서 cost가 가장 작은 것만을 구한다.

4) “이것을 원하셨습니까?” 로 제시를 한다.

5) 끝

적절한 시나리오라고 생각이 된다.

Edit Distanc로 검색한 결과로 나온 Edit Distance

우리 나라 포탈에서는 이런기능을 쓰지 않지만 알고리즘으로 적당하게 구글과 같은 suggest 기능을 구현할 수 있지 않을까 한다.

근데 한글은 어떻게 Edit Distance를 구현하면 될까?

모두 한글일 경우와 한글과 영어가 섞인 경우 모두 생각해야 된다.

이번 바쁜일 끝나면 한번 생각해 보도록 하자. ^^;

Google may use ‘Edit Distance’ in ‘Query suggestion’? by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.