제품

Elasticsearch에서 퍼지 검색을 사용하는 방법

By
Andrew Cholakian

업데이트: 이 글에서는 호스팅 Elasticsearch 서비스를 이전 명칭인 Found로 지칭합니다. Found는 현재 Elastic Cloud라는 이름으로 제공됩니다.

Elasticsearch의 퍼지 쿼리는 다양한 상황에서 사용할 수 있는 강력한 도구입니다. 사용자 이름 검색, 철자 오류 및 기타 특이한 문제는 이 색다른 쿼리로 해결할 수 있는 경우가 많습니다. 이 글에서는 퍼지 검색의 때때로 혼란스러운 옵션을 명확히 설명하고, Lucene의 FuzzyQuery 내부 작동 방식도 자세히 살펴봅니다.

소개

자연어 검색은 본질적으로 부정확합니다. 컴퓨터는 자연어를 이해할 수 없으므로 검색을 위한 접근 방식은 매우 다양하며, 각각 장점과 단점이 있습니다. Elasticsearch의 기반 기술인 Lucene은 다양한 텍스트 처리 도구로 구성된 만능 도구입니다. 그 안의 각 도구는 진정한 언어 이해를 대신하는 알고리즘 기반 지름길인 휴리스틱입니다. Snowball 어간 추출기나 Metaphone 음성 분석기와 같은 일부 도구는 매우 정교합니다. 이 도구들은 각각 언어 이해의 문법적 측면과 음성학적 측면을 모방합니다. 다른 도구는 단어의 첫 글자만 단순히 일치시키는 접두사 쿼리 유형처럼 매우 기본적입니다. 퍼지 쿼리는 정교함 측면에서 이러한 도구 모음의 중간쯤에 위치합니다. 쿼리와 일치하기 위해 '편집'이라고 하는 최대 일정 횟수의 문자 수정이 필요한 단어를 찾습니다. 예를 들어 'ax'에 대한 퍼지 검색은 'axe'라는 단어와 일치합니다. 두 단어를 일치시키려면 'e'를 제거하는 한 번의 삭제만 필요하기 때문입니다.

간단한 퍼지 일치

퍼지 쿼리는 다음 단락 아래의 예와 같이 match 쿼리 유형에 추가 인수를 지정하여 가장 쉽게 수행할 수 있습니다. 이 예에서 A가 하나 더 포함된 'vaacuum'을 검색하는 마지막 요청은 여전히 'Vacuum' 제품을 찾아야 합니다. fuzziness 인수는 결과가 최대 편집 거리 2 내에서 일치하도록 지정합니다. fuzziness는 1과 2의 값으로만 사용해야 한다는 점에 유의해야 합니다. 즉, 쿼리와 문서의 용어 사이에는 최대 2회의 편집만 허용됩니다. 이보다 큰 차이는 효율적으로 계산하기에 훨씬 더 많은 비용이 들며 Lucene에서 처리하지 않습니다. 공식 설명서에서는 여전히 fuzziness를 0.5와 같은 부동 소수점 값으로 설정하는 방법을 언급하지만, 이러한 값은 실제로 더 이상 사용되지 않으며 이해하기도 더 어렵습니다.

# 인덱스 생성
PUT /fuzzy_products
# Create the product mapping
PUT /fuzzy_products/product/_mapping
{
  "product": {
    "properties": {
      "name": {
        "type": "string",
        "analyzer": "simple"
      }
    }
  }
}
# 일부 문서 업로드
PUT /fuzzy_products/product/1
{"name": "Vacuum Cleaner"}
PUT /fuzzy_products/product/2
{"name": "Turkey Baster"}
# 퍼지 검색 수행!
POST /fuzzy_products/product/_search
{
  "query": {
    "match": {
      "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      }
    }
  }
}

편집 거리 결정하기

퍼지 쿼리가 일치 여부를 판단하는 데 사용하는 측정 기준은 Damerau-Levenshtein 거리 공식입니다. 간단히 말해, 두 텍스트 사이의 Damerau-Levenshtein 거리는 한 문자열을 다른 문자열과 일치시키기 위해 필요한 삽입, 삭제, 치환 및 전치의 횟수입니다. 예를 들어 'ax'와 'axe'라는 단어 사이의 Levenshtein 거리는 한 번의 삭제가 필요하므로 1입니다.

Damerau-Levenshtein 거리 공식은 전치를 유효한 작업으로 추가하여 고전적인 Levenshtein 거리 공식을 수정한 것입니다. 두 공식 모두 지원되며, Damerau-Levenshtein이 기본값입니다. 쿼리에서 transpositions를 false로 설정하면 고전적인 Levenshtein을 선택할 수 있습니다.전치의 유용성은 'aex'와 'axe' 문자열을 비교하는 경우에 확인할 수 있습니다. 고전적인 Levenshtein 거리 공식을 사용하면 'aex'는 한 번이 아니라 두 번의 편집 거리에 있습니다. 'e'를 삭제한 후 올바른 위치에 새 'e'를 삽입해야 합니다. 반면 Damerau-Levenshtein에서는 'e'와 'x'를 서로 바꾸는 한 번의 작업이면 충분합니다. 이를 확장해서 생각해 보면, 고전적인 Levenshtein을 사용하면 'aex'는 'faxes'만큼이나 'axe'와 멀리 떨어져 있다는 의미가 됩니다. 이는 대부분의 경우 Damerau-Levenshtein이 직관적으로 더 타당한 이유를 보여 주는 예입니다.

특히 퍼지 검색을 다룰 때는 Elasticsearch에서 텍스트가 검색에 사용되기 전에 먼저 분석기를 거친다는 점을 이해하는 것이 매우 중요합니다. 데이터가 인덱싱되면 실제 데이터베이스에서 검색 가능한 단위인 '용어'로 처리됩니다. 검색되는 대상은 실제로 저장된 문서가 아니라 분석된 용어입니다. 용어에 관한 내용은 Elasticsearch from the Bottom Up에서 다룹니다. 즉, 퍼지 쿼리를 수행할 때 분석 결과로 인해 쿼리 텍스트가 예상하지 못한 용어 값과 비교될 수 있으며, 이로 인해 때때로 혼란스러운 결과가 발생할 수 있습니다. 또한 필드에서 동의어를 활성화한 경우 원본 텍스트에 해당 단어가 전혀 나타나지 않더라도 동의어가 일치할 수 있습니다. 예를 들어 n-gram 분석 필드에서 퍼지 쿼리를 사용하면 결과가 이상할 가능성이 높습니다. n-gram은 단어를 여러 개의 작은 문자 조합으로 분할하며, 실제 단어는 매우 다르더라도 이들 문자 조합 중 다수는 한두 번의 편집 거리밖에 차이 나지 않기 때문입니다. 또한 Snowball 분석기를 사용한다면 'running'에 대한 퍼지 검색은 'run'으로 어간 추출되지만, 'runninga'는 'runninga'으로 어간 추출되므로 철자가 잘못된 단어 'runninga'와 일치하지 않습니다. 'run'과 'runninga'는 2회보다 많은 편집 거리가 있기 때문입니다. 이는 상당한 혼란을 일으킬 수 있으므로, 퍼지 쿼리에 사용할 텍스트에는 단순 분석기만 사용하고 동의어도 비활성화하는 것이 적절한 경우가 많습니다. 이를 명확히 설명하기 위해 Snowball 분석 문서에 대해 퍼지 쿼리를 실행하는 다이어그램을 아래에서 확인할 수 있습니다.

A fuzzy query using a snowball analyzer

Snowball 분석기를 사용하는 퍼지 쿼리

다양한 유형의 퍼지 검색

Elasticsearch는 여러 유형의 퍼지 검색을 지원하며, 그 차이를 혼동하기 쉽습니다. 아래 목록에서는 이러한 다양한 유형을 구분해 설명합니다.

  • match 쿼리 + fuzziness 옵션: match 쿼리에 fuzziness 매개변수를 추가하면 일반 match 쿼리가 퍼지 쿼리로 바뀝니다. 검색을 수행하기 전에 쿼리 텍스트를 분석합니다.
  • fuzzy 쿼리: Elasticsearch의 fuzzy 쿼리 유형은 일반적으로 사용하지 않는 것이 좋습니다. term 쿼리와 매우 유사하게 작동하며, 먼저 쿼리 텍스트를 분석하지 않습니다.
  • fuzzy_like_this/fuzzy_like_this_field: more_like_this 쿼리이지만 퍼지 기능을 지원하며, 퍼지 일치 결과의 특성을 더 잘 처리하도록 조정된 점수 산정 알고리즘을 사용합니다.*
  • 제안기: 제안기는 실제 쿼리 유형이 아니라, 쿼리와 함께 또는 독립적으로 실행할 수 있는 별도의 작업 유형입니다. 내부적으로는 퍼지 쿼리를 기반으로 합니다. 제안기는 '이것을 찾으셨나요?' 유형의 기능에 적합합니다.

fuzziness 매개변수가 설정된 match 쿼리는 퍼지 쿼리 중에서 가장 다양한 방식으로 활용할 수 있습니다. fuzzy 쿼리 유형은 쿼리 텍스트를 분석할 수 없다는 점을 제외하면 정확히 동일한 동작을 지원합니다. 또한 fuzzy 쿼리 유형은 match 쿼리 기능의 일부이므로 유용하기보다 혼란을 줄 수 있습니다.

fuzzy_like_this, 즉 FLT 쿼리는 편집 거리로 구분되는 오타나 기타 부정확성이 포함될 수 있는 큰 원본 텍스트 조각을 기반으로 추천을 제공하는 데 유용합니다. 이 범주에는 fuzzy_like_this 및 fuzzy_like_this_field라는 두 가지 쿼리가 있으며, 둘 다 동일한 기능을 제공합니다. 후자의 쿼리는 단일 필드만 사용하는 경우 구문을 간소화합니다.이러한 쿼리는 기사 본문과 같은 큰 텍스트 조각으로 구성된 like_text 매개변수를 받아, 해당 문서와 '유사한' 문서를 찾으려고 합니다. 기사의 텍스트를 확인하고, like_text 내 빈도를 기반으로 쿼리 용어에 가중치를 부여합니다. 이때 원본 텍스트의 여러 용어를 결합하기 위해 특수 조정(coord 요인 비활성화, 원본 텍스트 기반 IDF)을 적용합니다. FLT 쿼리는 코퍼스에 많은 수의 철자 오류가 포함된 경우에 가장 적합하며, 그렇지 않은 경우에는 표준 more_like_this 쿼리의 성능이 더 우수합니다. 자세한 내용은 Fuzzy More Like This 공식 설명서에서 확인할 수 있습니다.

제안기는 사용자가 'New York'을 입력하려 했지만 검색에 'New Yrok'을 입력한 경우에 유용합니다. 애플리케이션은 제안기를 사용하여 사용자 인터페이스에 가능한 수정 사항을 추천하는 '이것을 찾으셨나요?' 상자를 표시할 수 있습니다. 다만 자동 완성 검색의 구체적인 경우에는 자동 완성 검색이 지연 시간에 민감하므로 completion API가 더 나은 성능을 제공합니다. 제안기에 관한 자세한 내용은 검색 제안기 페이지에서 확인할 수 있습니다.

성능 고려 사항

Lucene의 Levenshtein 거리 구현은 최신 기술에 속하고 상당히 빠르지만, 일반 match 쿼리보다 여전히 훨씬 느립니다. 쿼리의 실행 시간은 인덱스의 고유 용어 수에 따라 증가합니다. 즉, 퍼지 검색을 수행할 때 주요 기준은 반환되는 문서 수가 아니라 검색하는 필드에 대해 클러스터 전반에 존재하는 고유 용어 수입니다. 문서 100개에 각각 10,000개의 고유 단어가 있는 경우, 해당 인덱스를 검색하는 작업은 검색 대상 필드에 고유 단어가 100개뿐인 문서 10,000개를 검색하는 작업보다 느립니다.

이 속도 저하의 주된 이유는 표준 match 쿼리가 Lucene에서 사용하는 내부 데이터 구조인 용어 인덱스에서 일치 항목을 빠르게 확인하고, 이진 검색을 사용해 문서를 매우 빠르게 찾을 수 있기 때문입니다. 이진 검색은 확장성이 뛰어나므로 대형 사전에서도 이 프로세스는 빠릅니다. 반면 퍼지 쿼리는 많은 수의 용어를 처리해야 하는 DFA가 포함된 고급 알고리즘을 사용합니다. 퍼지 검색에 필요한 훨씬 더 많은 수의 용어를 처리하는 작업은 단순 이진 검색보다 항상 느립니다. 예를 들어 영어 Wikipedia 데이터 세트에서 min_similarity가 2일 때 'history'라는 용어에 퍼지 검색을 실행하면 약 320ms가 걸리는 반면, 동일한 용어에 대한 일반 match 검색은 단 35ms만에 실행됩니다. 이는 한 자릿수 차이입니다. min_similarity가 1이면 검색 시간은 150ms에 불과합니다. 이 테스트는 통계적으로 타당한 방식으로 수행되지 않았으며, 이러한 시간은 개별 애플리케이션에 특화된 요인의 영향을 크게 받을 수 있다는 점에 유의해야 합니다. 특히 Wikipedia 데이터 세트에는 다수의 일반적인 사용 사례보다 훨씬 많은 용어가 포함되어 있습니다.

일치 항목이 쿼리와 정확한 접두사 일치를 갖도록 요구하면 성능을 크게 개선할 수 있습니다. 이렇게 하면 앞부분에 철자 오류가 있는 단어를 찾지 못하는 대신 검색 공간이 크게 줄어듭니다. 접두사 길이가 길수록 속도 향상 폭도 커집니다. 위에서 언급한 320ms 쿼리에서 prefix_length를 1로 지정하면 실행 시간을 단 104ms로 줄일 수 있습니다. 이 숫자를 높이면 속도가 더욱 향상됩니다. 일반적으로 용어 수가 많은 데이터 세트에서는 접두사를 요구하는 것이 좋습니다. 그렇지 않으면 성능이 저하되어 수백 밀리초에 이르는 경우가 많습니다.

검색을 중단하기 전에 퍼지 쿼리가 일치시키는 최대 용어 수를 정의하는 max_expansions 설정도 퍼지 쿼리 성능에 큰 영향을 미칠 수 있습니다. 그러나 쿼리 용어 수를 줄이면 쿼리가 조기에 종료되어 유효한 일부 결과를 찾지 못할 수 있다는 부정적인 영향이 있습니다. max_expansions 쿼리 제한은 샤드 수준에서 작동한다는 점을 이해하는 것이 중요합니다. 즉, 값을 1로 설정하더라도 서로 다른 샤드에서 나온 여러 용어가 일치할 수 있습니다. 이 동작으로 인해 max_expansions가 적용되지 않는 것처럼 보일 수 있으므로, 반환되는 고유 용어 수를 세는 것은 max_expansions가 작동하는지 판단하는 유효한 방법이 아니라는 점에 유의하세요.

퍼지 일치의 대안

퍼지 일치가 항상 작업에 적합한 도구인 것은 아니며, 부정확한 일치는 다른 기법으로 찾을 수 있는 경우가 많습니다. 음성 분석 플러그인에는 다른 단어와 비슷하게 들리는 단어를 찾는 Metaphone 분석기와 같이 근사 일치에 사용할 수 있는 흥미로운 도구가 다수 포함되어 있습니다. 예를 들어 'run'과 'ran' 같은 단어가 모두 동등하게 취급되도록 해야 한다면 Snowball 분석기와 같은 지능형 분석기가 더 적합합니다. 또는 철자 오류를 확인하려면 이 짧은 튜토리얼에서 설명하는 n-gram 분석이 데이터 세트에 따라 쿼리 시점에서 훨씬 더 빠르게 실행될 수 있습니다. 그러나 n-gram에는 추가 스토리지/메모리 사용, 인덱싱 시점의 처리 증가 및 정확한 일치 결과 뒤에 길게 이어지는 오탐이라는 비용이 따릅니다.

추가 자료

  • Elasticsearch에서 퍼지 쿼리의 성능을 더 자세히 알아보려면 Lucene 핵심 기여자인 Mike McCandless가 이 주제에 관해 작성한 흥미로운 블로그 글을 확인해 보세요. Levenshtein과 Lucene의 기타 오토마타를 다루는 Dawid Weiss의 발표 영상 Finite State Automata in Lucene and Solr('Lucene 및 Solr의 유한 상태 오토마타')도 있습니다.
  • Levenshtein 오토마타에 관해 더 알고 싶다면 Nick Johnson의 훌륭한 글 Damn Cool Algorithms: Levenshtein Automata('정말 멋진 알고리즘: Levenshtein 오토마타')를 확인해 보세요.