잘못된 검색 허용

이 글은 최초로 https://tomekdev.com/posts/search-with-typo-tolerance에 발표되었다.네가 여기서 본 GIF는 상호작용적이다.✌️
누구나 실수를 할 수 있다.이것이 바로 어떤 내용을 처리하는 인터페이스의 필수 도구인 이유입니다.이것이 바로 우리가 터치스크린의 클릭 가능한 요소 주위에 터치하기 쉽게 추가 충전물을 추가하는 이유이다.구글이 입력한 내용이 완벽하지 않아도 결과를 보여주려고 시도하는 이유다.
사용자들은 이 점을 절대적으로 좋아한다. 소프트웨어가 ctrl+z이 없으면, 그들이 오류를 입력했을 때 '결과 없음' 페이지를 볼 수 있을 것이라고 상상할 수 없다.문턱이 높은 것 같아...그러나 많은 소프트웨어가 검색과 결과를 표시할 때 개발자가 편리한 일만 한다.

문제를 검토하다

다음은 필터 목록처럼 작동하는 간단한 검색입니다.리스트가 짧아서 무슨 일이 일어났는지 쉽게 이해할 수 있다.다시 말하면, 우리는 화면에 이미 모든 요소가 있지만, 검색은 우리가 그 물건을 찾을 수 있도록 도와줄 것이다.
목록을 보십시오. 내가 거기에 무엇을 입력했는지, 맞춤법이 틀렸는지, 아니면 완전히 다른 것을 입력했는지 보십시오.You can play with it on my page .

우리가 방금 사용한 것은 간단한 포함 조회이다.또는 SQL에 대해 잘 알고 있다면 %LIKE%을 실행하겠습니다.안 좋아요?괜찮습니다.엄격한 것보다 나을 거야.그러나 이것은 결코 매우 우호적인 것이 아니다. 왜냐하면 너는 반드시 옳아야 하기 때문이다.
아래의 코드는 이런 방법의 핵심을 두드러지게 보여 준다.우리는 모든 과일 이름이 검색 텍스트를 포함하는지 검사해서 목록을 필터합니다.여기에는 대소문자를 구분하지 않고 검색하는 사용자 친화적인 방법이 있습니다. 이것은 대부분의 텍스트 검색에 필요한 작업입니다.

const FRUITS = ['Apple', 'Banana', 'Blueberry', 'Cherries' /* etc... */];

function searchHandler(event) {
  const searchText = event.target.value.toLowerCase();

  const filteredFruits = FRUITS.filter((fruit) => {
    return fruit.toLowerCase().includes(searchText); // HERE
  });

  // render the list of `filteredFruits`
}

관용을 베풀다

작은 실수를 용인하는 것을 맞춤법 오류라고 하는 것이 어떻습니까?다시 한번 해보자.나는 목록에 있는 과일을 검색하고 있지만 이번에는 철자가 틀렸다.사과가 아닌 aple일지도 몰라요?

Aple, 내 말은 애플이 여전히 명단에 있다는 거지?반나, 블루베리, 키리, 페어 등도 마찬가지다.나는 이 알고리즘이 자동 검색에 불리하다는 것을 인정해야 한다.[Search] 버튼을 사용하는 체험이 훨씬 낫다. 왜냐하면 이곳에서 타자를 칠 때 가짜 친구를 볼 수 없기 때문이다.하지만 그것의 작업 원리를 이해하는 것이 훨씬 낫다...pee 해보겠습니다.🤭 예컨대.너는 명단에서 사과와 배를 보아야 한다.우리가 사용하는 알고리즘에 따르면 둘 다 매우 가깝다.

계산법

여기에 사용된 알고리즘을 Levenshtein 거리라고 합니다.나는 위키백과의 말을 인용할 것이다.

[...] the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

이것은 커다란 우세일 뿐만 아니라, 때로는 문제이기도 하다.검색 가능한 항목의 이름이 짧을수록 알고리즘의 성능이 떨어진다.Pear와 같은 매우 짧은 단어는 타자를 칠 때 인기가 많은데, 대량으로 삽입해야 하는 매우 긴 단어에 비해'일치'에 필요한 편집 횟수가 상대적으로 짧기 때문이다.
정의에서 말한 바와 같이 이 알고리즘의 핵심에서 우리는 거리를 계산한다.그리고 우리는 거리가 우리가 받아들일 수 있는지 없는지를 결정한다. 그러면 우리가 받아들일 수 있는 최소 편집량은 얼마입니까?단어와 검색 텍스트의 거리를 상상해 봅시다.

어색한 pee으로 돌아가겠습니다.🤭. 너는 스크린에서 사과(3)와 배(2)를 보아야 한다.거리는 어떻게 측정합니까?다음을 살펴보십시오.

애플의 경우'pee'에서 A과 p을 추가하고 첫 번째 e을 l으로 변경하는 세 가지 작업을 수행해야 한다.Pear의 경우 두 번째 e을 a으로 변경하고 마지막에 r을 추가합니다.보시다시피 주어진 입력에서 Pear를 얻는 것이 더 쉽습니다.
지금까지 우리는 단지 물품의 순서를 유지했을 뿐이다.하지만 사실 Pear는 애플보다 우리의 수요에 더 가깝기 때문에 이 옵션이 1위를 차지해야 한다.
걱정하지 마라, 우리는 단지 그것을 해결하러 갈 뿐이야!보기:

구현

그러면 그것은 어떻게 일을 합니까?간단히 말해서 검색/필터 알고리즘을 변경했습니다(강조 표시된 줄 참조).

const FRUITS = ['Apple', 'Banana', 'Blueberry', 'Cherries' /* etc... */];
const MIN_DISTANCE = 3;

function searchHandler(event) {
  const searchText = event.target.value.toLowerCase();

  const filteredFruits = FRUITS.filter((fruit) => {
    // HIGHLIGHT STARTS
    const distance = levenshtein(fruit.toLowerCase(), searchText);
    return distance <= MIN_DISTANCE;
    // HIGHLIGHT ENDS
  });

  // render the list of `filteredFruits`
}

function levenshtein(a, b) {
  // The Levenshtein's algorithm calculating the distance
}

우리는 Levenshtein씨의 방법을 사용하여 거리를 비교합니다. 만약 거리가 우리가 받아들인 최소 거리보다 높다면, 우리는 이 항목들을 필터하기로 결정했습니다.
알고리즘 자체와 관련이 있을 때, 위키백과의 정의에 따라 스스로 그것을 실현하기를 원할 수도 있습니다.그러나 내가 계산에 대해 아는 것이 있다면, 네가 먼저 생각한 것보다 훨씬 빠른 방법이 있다. 수학 방정식을 볼 때.
가장 좋은 것은 단지 인터넷에 이미 있는 것만 사용하는 것이다.the implementation I used입니다.

완벽한 공차(거리)

나는 어떤 공식도 찾을 수 없지만, 가장 좋은 추측은, 당신이 받아들여야 할 최소 공차 (거리) 가 데이터 집중의 가장 짧은 단어보다 조금 작아야 한다는 것이다.그렇지 않으면, 이 단어는 너무 자주 나타날 수 있다.

혼합 방법

만약 당신이 아직 눈치채지 못한다면, 나는 %LIKE%과 Levenshtein 방법의 조합을 사용했다.따라서 전형적인 일치가 없는 상황에서만 우리는 다음 방법으로 돌아갈 수 있다.이것은 매우 편리하다. 왜냐하면 정확한 일치는 사용자가 원하는 것일 수 있기 때문이다.그들은 텍스트의 다른 변형을 검색하는 것을 개의치 않을 수도 있다. 만약 그들이 원하는 내용을 찾았다면, 이 변형들은 '고정' 타자 오류로 간주될 수도 있다.

이게 완벽한 방법인가요?

사실은 아니야.대부분의 해결 방안과 마찬가지로, 그것이 반드시 완벽한 것은 아니다.만약 그것이 증가할 가치가 가져올 수 있는 곤혹을 초과한다면 (때로는 결과에 가짜 친구가 나타날 수도 있기 때문에) 그것은 유용하다.
Levenshtein 방법은 특정 주제에 대한 여러 가지 방법 중 하나입니다.만약 당신이 이런 실험을 더 많이 보고 싶다면, 나에게 알려주세요.

보상: 구글도 이렇게 하나요?

아뇨.그들의 "당신은 무슨 뜻입니까?"검색의 기능은 이와 매우 다르다.내가 아는 바에 의하면, 그들은 우리가 타자 오류로 인해 쓸모 있는 것을 찾지 못할 때, 조회를 바로잡을 것이다.이런 방식을 통해 그들은 믿을 수 없는 데이터량을 가지고 있다. 그들은 주어진'타자 오류'에 대해 가장 좋은 추측이 무엇인지 알고리즘을 가르칠 수 있다.그것은 훨씬 복잡하지만, 장시간의 조회에 있어서는 매우 효율적일 수 있다.
어쨌든, 우리의 전방 수요를 만족시키기 위해, 사용자가 검색에서 오류를 입력하는 것을 돕는 첫 번째 시도로서, 나는 Levenshtein 방법이 이미 충분하다고 생각한다.당신은 어떻게 생각합니까?