[elasticsearch] fuzzy 알고리즘 (무엇을 찾고 있는가?)

일래스틱서치는 fuzzy query를 지원한다. 

Fuzzy query와 Range query의 around 에서 사용하는 내용으로 조금 공부가 필요하다.

일래스틱서치는 내부적으로 사용하는 레펜스타인 알고리즘과 다메라우-레펜스타인 알고리즘, 자로 윙클러, ngram등을 지원하고 있으니, 아래 내용을 미리 살펴보고 이해하는 것이 좋다. 내용은 아래 설명이 잘 되어 있어서 특별히 하지 않는다.

http://ntz-develop.blogspot.de/2011/03/fuzzy-string-search.html

http://juggernaut.tistory.com/14 (한글 번역)

일래스틱서치는 레펜스타인 알고리즘(https://en.wikipedia.org/wiki/Levenshtein_distance)은 편집 거리(modified distance)의 을 사용하고 있다. 이 편집 거리의 개념을 매개변수로 받아들인다.

0, 1, 2

the maximum allowed Levenshtein Edit Distance (or number of edits)

AUTO

generates an edit distance based on the length of the term. For lengths:

0..2

must match exactly

3..5

one edit allowed

>5

two edits allowed

AUTO should generally be the preferred value for fuzziness.

출처 : https://www.elastic.co/guide/en/elasticsearch/reference/1.7/common-options.html#_numeric_date_and_ipv4_fields

키워드의 유사도 검사시 단순히 유사도 검색 뿐 아니라 오타(전치)까지도 포함하는 알고리즘인  다메라우 레펜스타인 알고리즘은 

fuzziness 기본 값은 AUTO가 디폴트일 때 사용될 때 쓰이니 보는 것이 좋은 것 같다..

https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

실제 elasticsearch에서 suggest 에 관련 거리(distance) 

https://github.com/elastic/elasticsearch/blob/5278cf0d5e1afa6cf6d0959e839c0ed2408908f8/core/src/main/java/org/elasticsearch/search/suggest/SuggestUtils.java

   public static StringDistance resolveDistance(String distanceVal) {

        if ("internal".equals(distanceVal)) {

            return DirectSpellChecker.INTERNAL_LEVENSHTEIN;

        } else if ("damerau_levenshtein".equals(distanceVal) || "damerauLevenshtein".equals(distanceVal)) {

            return new LuceneLevenshteinDistance();

        } else if ("levenstein".equals(distanceVal)) {

            return new LevensteinDistance();

          //TODO Jaro and Winkler are 2 people - so apply same naming logic as damerau_levenshtein  

        } else if ("jarowinkler".equals(distanceVal)) {

            return new JaroWinklerDistance();

        } else if ("ngram".equals(distanceVal)) {

            return new NGramDistance();

        } else {

            throw new IllegalArgumentException("Illegal distance option " + distanceVal);

        }

    }

일래스틱서치는 XFuzzySuggester 클래스에 다메라우 레펜스타인 알고리즘을 기반으로 하여 좀 더 놓은 Fuzzy 추천 알고리즘을 추가하기도 했다. 

https://github.com/elastic/elasticsearch/blob/b582de79ae1b669e76d0ffb70e90075bd9d0cddf/core/src/main/java/org/apache/lucene/search/suggest/analyzing/XFuzzySuggester.java

참고 :

https://www.elastic.co/guide/en/elasticsearch/reference/1.7/query-dsl-fuzzy-query.html

http://ko.cyclopaedia.asia/wiki/Jaro%E2%80%93Winkler_distance

https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

https://en.wikipedia.org/wiki/Levenshtein_distance