Удивите своих пользователей поиском, допускающим опечатки. Дайте им понять, что они вам небезразличны и постараетесь изо всех сил показать результаты.

Все совершают ошибки. Вот почему отмена / повтор является обязательным условием для интерфейсов, где вы над чем-то работаете. Вот почему мы добавляем дополнительную обивку вокруг интерактивных элементов для сенсорных экранов, чтобы было легче улавливать прикосновения. Вот почему Google пытается показать некоторые результаты, даже если набранный вами текст далек от совершенства.

Пользователям это очень нравится, и они не могут представить себе программное обеспечение без ctrl+z и просмотра страницы «Нет результатов», когда они что-то опечатали. Кажется, планка высока ... но все же многие программы делают только то, что удобно для разработчиков, когда дело касается поиска и отображения результатов.

Изучение проблемы

Ниже представлен простой поиск, который будет работать как фильтрация по списку. Список короткий, поэтому будет легко понять, что происходит. Другими словами, у нас уже есть все элементы на экране, но поиск поможет нам найти эту вещь.

Пожалуйста, посмотрите на список и наблюдайте, как я что-то там печатаю, опечатываю что-то или печатаю что-то совершенно другое. Вы можете поиграть с ним на моей странице.

Мы только что использовали здесь простой запрос «на содержание». Или, если вы знакомы с 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`
}

Введение толерантности

Как насчет терпимости к мелким ошибкам, известным как опечатки? Давай еще раз попробуем. Ищите фрукты в списке, но на этот раз пишите с ошибками. Может, яблоко вместо яблока?

Апл, я имею в виду, что Apple все еще в списке, верно? То же самое с бананой, блубери, чери, сверстником и т. Д. Должен признать, алгоритм не удобен для автопоиска. Использование кнопки [Search] намного лучше, потому что вы не увидите здесь ложных друзей во время набора текста. Но это намного лучше для понимания того, как это работает ...

Например, давайте попробуем pee 🤭. В списке вы должны увидеть яблоко и грушу. Оба являются довольно близкими совпадениями в соответствии с используемым нами алгоритмом:

Алгоритм

Используемый здесь алгоритм называется расстояние Левенштейна. Я процитирую Википедию по этому поводу:

[…] расстояние Левенштейна между двумя словами - это минимальное количество односимвольных изменений (вставок, удалений или замен), необходимых для преобразования одного слова в другое.

Это одновременно огромное преимущество, а иногда и проблема. Чем короче имена элементов, доступных для поиска, тем хуже для алгоритма. Очень короткие слова, такие как груша, предпочтительнее при наборе текста, потому что количество правок, необходимых для «поиска совпадения», будет относительно небольшим по сравнению с очень длинным словом, которое требует много вставок.

Как указано в определении, в основе этого алгоритма вычисляется расстояние. Затем мы решаем, приемлемо ли это расстояние - так каков минимум правок, которые мы принимаем? Давайте визуализируем это и посмотрим, насколько далеко слова находятся от искомого текста:

Вернемся к нашему смущающему pee примеру 🤭. На экране вы должны увидеть яблоко (3) и грушу (2). Как измеряется расстояние? Пожалуйста, посмотрите ниже:

В случае Apple нам нужно выполнить 3 операции, чтобы попасть туда из «pee»: добавить A и p и изменить первый e на l. Когда дело доходит до Груши, нужно выполнить всего две операции: заменить вторую e на a и добавить r в конце. Как видите, из заданного ввода проще получить Pear.

До сих пор мы просто сохраняли порядок элементов, как он был (здесь в алфавитном порядке). Но на самом деле Pear ближе к тому, что нам нужно, чем Apple, и этот вариант должен занять первое место в списке.

Не бойтесь, мы просто разберемся с этим! Взглянем:

Реализация

Итак, как это работает? Вкратце, мы только что изменили алгоритм поиска / фильтрации (см. Выделенные строки).

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
}

Мы сравниваем расстояние, используя метод г-на Левенштейна, и если расстояние превышает минимальное расстояние, которое мы принимаем, мы решаем отфильтровать эти записи.

Что касается самого алгоритма, вы можете реализовать его самостоятельно на основе определения в Википедии. Но если я что-то знаю о вычислениях, так это то, что существуют методы, которые намного быстрее, чем то, что приходит вам в голову в первую очередь, когда вы смотрите на математическое уравнение.

Идеальная переносимость (расстояние)

Я не смог найти никакого уравнения для этого, но я предполагаю, что минимальный допуск (расстояние), который вы должны принять, должен быть немного меньше, чем самое короткое слово в вашем набор данных. В противном случае есть вероятность, что это слово будет встречаться слишком часто.

Гибридный подход

Если вы еще не заметили, я использую комбинацию %LIKE% match и метод Левенштейна. Поэтому мы возвращаемся ко второму методу только в том случае, если у нас нет типичных совпадений. Это удобно, потому что пользователи, вероятно, хотят «точного» совпадения. Их, вероятно, не волнуют другие варианты искомого текста, которые можно рассматривать как «исправленную» опечатку, если у них есть именно то, что они искали.

Это идеальный метод?

Что ж, это не так. Как и большинство решений, оно не обязательно должно быть идеальным. Если это приносит больше пользы, чем может вызвать путаницу (иногда из-за ложных друзей в результатах), тогда это полезно.

Метод Левенштейна - один из многих для данного предмета. Если вы хотите увидеть больше подобных экспериментов, дайте мне знать.

Бонус: делает ли Google то же самое?

Неа. Их «Вы имели в виду?» функциональность в поиске сильно отличается от этой. Насколько мне известно, они основывались на нас (пользователях), которые исправляют запросы, когда мы не можем найти ничего полезного из-за опечаток. Таким образом, с невероятным количеством данных, которыми они обладают, они могут научить алгоритм, как лучше всего угадывать данные «опечатки». Он намного сложнее, но может быть очень эффективным для длинных запросов.

В любом случае, для наших внешних потребностей и в качестве первой попытки помочь пользователям с опечатками в поиске я думаю, что мы достаточно хороши с методом Левенштейна. Как вы думаете?

Этот пост изначально был опубликован на https://tomekdev.com/posts/search-with-typo-tolerance. То, что вы видите здесь как GIF, там интерактивно. ✌️