[Elasticsearch] Fuzzy 쿼리

오타

• 사전적 의미: 타자를 칠 때에 잘못 찍는 일 또는 그 글자
• 영어: typo, typographical error
• 오타는 '검색 결과 없음'의 주요 원인
• 발생하는 이유는 다음과 같이 다양함
  • 키보드 타이핑 시 왼손과 오른손의 반응 속도 차이
  • 모바일에서 터치 실수 (Fat Finger)
  • 정타를 오타로 잘 못 인지하는 경우
  • 정타 자체를 인지하지 못하는 경우
  • etc.

 

Fuzzy Matching

• 오타 입력 시 의도한 정타로 검색어를 전환하는 기법
• 이를 지원하면 검색어의 결과가 나오지 않는 문제를 일부 해결 가능
  • UX를 향상 시키는 일
  • 검색 서비스에 신뢰하는 요소

 

Elasticsearch가 오타를 지원하는 방법

 

1. Levenshtein distance 기반의 알고리즘 Damerau-Lavenshtein

• 두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘
• 자연어 영역뿐 아니라 의료 공학에서 유전자 유사도 판별에도 쓰임
•  Levenshtein distance는 Edit Distance 알고리즘이라고도 불림
  
  • 백준 15483번 최소 편집 문제 참고

 

https://yuminlee2.medium.com/levenshtein-distance-1080038a4d9

 

* Elasticsearch는 Edit Distance 알고리즘을 그대로 사용하지는 않고 순서의 변경을 유효한 작업으로 간주하는 Damerau-Lavenshtein 알고리즘을 사용함

 

	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	int optimalStringAlignmentDistance(string s1, string s2) {
	// Create a table to store the results of subproblems
	vector<vector<int>> dp(s1.length() + 1, vector<int>(s2.length() + 1));
	// Initialize the table
	for (int i = 0; i <= s1.length(); i++) {
	dp[i][0] = i;
	}
	for (int j = 0; j <= s2.length(); j++) {
	dp[0][j] = j;
	}
	// Populate the table using dynamic programming
	for (int i = 1; i <= s1.length(); i++) {
	for (int j = 1; j <= s2.length(); j++) {
	if (s1[i-1] == s2[j-1]) {
	dp[i][j] = dp[i-1][j-1];
	} else {
	dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));
	}
	}
	}
	// Return the edit distance
	return dp[s1.length()][s2.length()];
	}
	int main() {
	cout << optimalStringAlignmentDistance("geeks", "forgeeks") << endl;
	return 0;
	}
	// This code is contributed by Vikram_Shirsat

view raw .cpp hosted with ❤ by GitHub

 

https://www.geeksforgeeks.org/damerau-levenshtein-distance/

 

Fuzzy 쿼리

• 검색어와 유사한 단어를 찾기 위해 사용되는 강력한 기능
• 오타, 철자 오류, 단어 변형 등을 처리할 때 매우 유용
• Edit Distance 알고리즘 기반인 Damerau-Lavenshtein 알고리즘을 사용하여 두 단어 간의 유사성을 측정하고 지정한 fuzziness(편집 거리)를 통해 검색어인 오타와 일치하는 단어를 찾음

 

	GET /index_name/_search
	{
	"query": {
	"fuzzy": {
	"field_name": {
	"value": "search_term",
	"fuzziness": "AUTO"
	}
	}
	}
	}

view raw .json hosted with ❤ by GitHub

 

부연 설명

• value: 검색할 단어
• fuzziness: 편집 거리(edit distance)
  • AUTO로 지정할 경우 Elasticsearch가 단어 길이에 따라 적절한 값을 자동으로 설정
  • term의 길이가 [0, 2] 일 경우 완전 매칭만 허용
  • term의 길이가 [3, 5] 일 경우 편집 거리 1까지 허용
  • term의 길이가 6 이상일 경우 편집 거리 2까지 허용

 

1. Fuzzy Query와 다른 검색 조합

 

1.1 match query + fuzzy query

• term 쿼리와 유사하게 동작하기 때문에 분석기를 거친 text 필드를 사용하지 않음

 

	POST test-fuzzy/_search
	{
	"query": {
	"match": {
	"message": {
	"query": "hello world",
	"fuzziness": 1
	}
	}
	}
	}

view raw .json hosted with ❤ by GitHub

 

1.2 suggester query + fuzzy query

• 'did you mean' 스타일의 자동완성에 적합한 용도로 사용

 

	POST test-fuzzy/_search
	{
	"suggest": {
	"song-suggest": {
	"prefix": "누진스",
	"completion": {
	"field": "suggest",
	"fuzzy": {
	"fuzziness": 1
	}
	}
	}
	}
	}

view raw .json hosted with ❤ by GitHub

 

2. Fuzzy Query 성능

• 비교적 빠른 편이지만 일반적인 match query에 비해 느림
• 쿼리의 실행 시간은 인덱스 내 고유 term 수에 비례하여 증가
  • Lucene 내부의 term 인덱스 구조를 통해서 빠르게 포함된 문서를 확인이 가능하지만 Fuzzy 쿼리는 그러지 못하기 때문에 느림
  • prefix_length를 길게 할 수록 큰 속도 향상 효과를 이룰 수 있지만 앞부분의 철자 오류를 잡지는 못함

 

3. Fuzzy Query 주의 사항

• Elasticsearch는 텍스트 검색 가능하게 되기 전에 분석기를 통과 (keyword의 경우 분석기 거치지 않음)
• Fuzzy Query를 수행할 때 쿼리 텍스트가 분석 결과로서 예상치 못한 어휘 값과 비교될 수 있으므로 때로는 혼동스러운 결과가 발생할 수 있음
• 필드에서 동의어가 활성화 되어 있을 경우 동의어가 일치할 수 있으며, 실제 원본 테그스트에 해당 단어가 전혀 난타나지 않더라도 일치할 수 있음을 의미
• ex) ngram 분석된 필드에 Fuzzy Query를 사용할 경우 결과는 매우 이상할 수 있음
• ex) snowball 분석기 사용할 경우 'running'에 대한 Fuzzy 검색은 'run'으로 어간이 축소될 것이지만 철자가 틀린 'runninga'와는 일치하지 않게 됨
• 따라서 Fuzzy Query에 사용할 텍스트의 경우 간단한 분석기만 사용하는 것이 합리적일 가능성이 높으며 가능하다면 synonym도 비활성화하는 것을 권장

 

오타 정보를 수집하는 방법

• 공개 데이터 활용: Commonly misspelled words
• 사용자의 쿼리 세션 정보를 기반으로 로그 수집
  • 오타 -> '결과 없음' -> 정타 -> 결과 반환
  • 위와 같은 프로세스를 거쳤다면 같은 세션 내 Edit Distance가 짧을 경우 오타로 간주

 

• 자연어 처리 기술을 활용한 오타 분석
  • 노이즈 채널 모델(Bayesian noisy channel)
  • 언어 모델과 오류 모델을 통해 주어진 '오타' 무낮열이 각각의 '정타' 후보들로부터 어떻게 유도될 수 있는지, 그리고 각 '정타' 후보들이 얼마나 '자연스러운' 문장인지를 종합적으로 판단하는 모델

 

참고

• 패스트 캠퍼스 -  고성능 검색 엔진 구축으로 한 번에 끝내는 Elasticsearch