Автозаполнение с нечетким поиском и Fuse.js

Узнайте, как создать список предложений, пока вы набираете название браузера

Смотрите эту и многие другие статьи на сайте lucaspaganini.com

Что мы будем создавать

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

Что такое нечеткий (приблизительный) поиск

Что такое «нечеткий» поиск?

Нечеткий поиск ищет текст, который соответствует термину приблизительно, а не точно.

При точном поиске слово «come» никогда не будет соответствовать слову «Chrome», потому что в слове «Chrome» нет слова «come». Здесь нет места для интерпретации, это либо истина, либо ложь. Это, конечно, не очень удобно для человека. Если мы ищем что-то, есть вероятность, что мы даже не знаем, как это правильно пишется.

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

Расстояние Хэмминга

В качестве учебного примера позвольте мне показать вам очень простой алгоритм нечеткого поиска, называемый расстоянием Хэмминга.

Если даны две строки одинаковой длины, то расстояние Хэмминга между ними — это минимальное количество замен, необходимых для изменения одной строки на другую. Например, расстояние Хэмминга между «Daniel» и «Denise» равно 3, потому что для того, чтобы они совпали, нам придется заменить 3 буквы.

Daniel против Denise.

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

Конечно, это было бы ужасно удобно для пользователя, поскольку наш алгоритм работает только со строками, имеющими одинаковую длину. Но это корректный пример. Он использует расстояние Хэмминга, чтобы определить, насколько близки две строки.

Выбор алгоритма нечеткого поиска

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

Также необходимо учитывать, с каким объемом данных вы имеете дело. Если вы хотите выполнить нечеткий поиск в огромном наборе данных, то делать это во фронтенде, вероятно, не самая лучшая идея. Даже если ваши конечные пользователи обладают большой вычислительной мощностью, им придется загрузить весь набор данных, чтобы выполнить поиск во фронтенде.

Кроме того, запуск поиска в бэкенде дает вам гораздо больше возможностей. Два самых популярных из них — ElasticSearch и Algolia.

В этом посте мы будем иметь дело с небольшим набором данных, поэтому запустим поиск во фронтенде.

Нативное автозаполнение HTML с помощью <datalist>.

Простой способ добавить автозаполнение в элемент ввода — использовать <datalist>. Для этого даже не требуется JavaScript, только HTML.


Посмотрите этот пример здесь

Алгоритм поиска довольно быстрый. Он использует точный поиск, удаляет пробелы и игнорирует чувствительность к регистру.

Но есть один недостаток… алгоритм поиска не настраивается. Как и стили списка. Так что этот вариант явно не подойдет для реальных проектов, где нужно соблюдать индивидуальный дизайн. Вот почему мы собираемся создать пользовательский компонент вместо использования <datalist>.

Пользовательский нечеткий поиск с помощью Fuse.js

Для нашего алгоритма нечеткого поиска я решил использовать Fuse.js. Он эффективен, хорошо документирован и активно поддерживается.
Я сделал все на чистом HTML, CSS и JavaScript. Я не хотел использовать фреймворк для этого примера, чтобы избежать излишней сложности. Я оставляю ссылку на код в разделе ссылок. Вы увидите, что нет никакого процесса компиляции, я просто открываю файлы в папке public/.

Мои константы задаются в файле config.mjs.

export const BROWSERS_LIST = [
  { shortName: 'IE', longName: 'Microsoft Internet Explorer', type: 'desktop' },
  { shortName: 'Edge', longName: 'Microsoft Edge', type: 'desktop' },
  { shortName: 'Firefox', longName: 'Mozilla Firefox', type: 'desktop' },
  { shortName: 'Chrome', longName: 'Google Chrome', type: 'desktop' },
  { shortName: 'Safari', longName: 'Safari', type: 'desktop' },
  { shortName: 'Opera', longName: 'Opera', type: 'desktop' },
  { shortName: 'Safari on iOS', longName: 'Safari on iOS', type: 'mobile' },
  { shortName: 'Opera Mini', longName: 'Opera Mini', type: 'mobile' },
  {
    shortName: 'Android Browser',
    longName: 'Android Browser / Webview',
    type: 'mobile'
  },
  {
    shortName: 'Blackberry Browser',
    longName: 'Blackberry Browser',
    type: 'mobile'
  },
  { shortName: 'Opera Mobile', longName: 'Opera for Android', type: 'mobile' },
  {
    shortName: 'Chrome for Android',
    longName: 'Google Chrome for Android',
    type: 'mobile'
  },
  {
    shortName: 'Firefox for Android',
    longName: 'Mozilla Firefox for Android',
    type: 'mobile'
  },
  {
    shortName: 'IE Mobile',
    longName: 'Microsoft Internet Explorer Mobile',
    type: 'mobile'
  },
  {
    shortName: 'UC Browser for Android',
    longName: 'UC Browser for Android',
    type: 'mobile'
  },
  {
    shortName: 'Samsung Internet',
    longName: 'Samsung Internet Browser',
    type: 'mobile'
  },
  {
    shortName: 'QQ Browser',
    longName: 'QQ Browser for Android',
    type: 'mobile'
  },
  {
    shortName: 'Baidu Browser',
    longName: 'Baidu Browser for Android',
    type: 'mobile'
  },
  { shortName: 'KaiOS Browser', longName: 'KaiOS Browser', type: 'mobile' }
];

export const BROWSER_INPUT_ELEMENT_ID = 'browser-input';
export const BROWSER_SUGGESTIONS_ELEMENT_ID = 'browser-suggestions';
export const BROWSER_SUGGESTIONS_MAX_SIZE = 7;
Вход в полноэкранный режим Выход из полноэкранного режима

Пользовательский выпадающий элемент объявлен в файле dropdown-element.mjs.

const TEMPLATE = document.createElement('template');
TEMPLATE.innerHTML = '';

export class AppDropdownElement extends HTMLElement {
  /** @type {ShadowRoot} */
  #shadowRoot;

  constructor() {
    super();

    this.#shadowRoot = this.attachShadow({ mode: 'open' });
    this.#shadowRoot.appendChild(TEMPLATE.content.cloneNode(true));
  }

  // Other methods omitted for simplicity
}

window.customElements.define('app-dropdown', AppDropdownElement);
Вход в полноэкранный режим Выход из полноэкранного режима

Наша функция нечеткого поиска с использованием Fuse.js определена в файле fuzzy-search.mjs.

export const fuzzySearch = (list, keys = []) => {
  const fuse = new Fuse(list, { ...FUSE_OPTIONS, keys });
  return (pattern) => fuse.search(pattern);
};
Вход в полноэкранный режим Выход из полноэкранного режима

А файл main.mjs связывает все: он слушает изменения в нашем вводе, запускает нечеткий поиск и отображает результаты.

// Filter the browsers list when the browser input changes
browserInputElement.addEventListener('input', () => {
  const searchKeyword = browserInputElement.value;

  const filteredList = fuzzySearchBrowsersList(searchKeyword);
  const cleanFilteredList = filteredList
    .slice(0, BROWSER_SUGGESTIONS_MAX_SIZE)
    .map((el) => el.item.longName);

  renderInputSuggestions(browserInputElement, cleanFilteredList);
});
Вход в полноэкранный режим Выход из полноэкранного режима

Fuse.js предоставляет множество опций, и все они очень описательны. Обратите особое внимание на параметр threshold. Он определяет, насколько близко должны находиться две строки, чтобы произошло совпадение. Установка значения 0 соответствует точному поиску, а установка значения 1 приведет к совпадению всего.

const FUSE_OPTIONS = {
  isCaseSensitive: false,
  includeScore: true,
  shouldSort: true,
  threshold: 0.6
};
Войти в полноэкранный режим Выход из полноэкранного режима

Я создал для вас игровую площадку для лучшего понимания Fuse.js! Ознакомьтесь с ней:


Посмотрите этот пример здесь

Заключение

Как всегда, ссылки находятся в разделе ссылок. Играйте с кодовой базой и не стесняйтесь обращаться ко мне, если у вас есть вопросы.

Если этот пост был полезен, подпишитесь на рассылку, чтобы получать больше уроков по веб-разработке. А если ваша компания ищет удаленных веб-разработчиков, свяжитесь со мной и моей командой [здесь] (https://www.lucaspaganini.com/contact).

Хорошего дня, и до встречи в следующем.

Ссылки

  1. Примеры кода — Лукас Паганини
  2. Как работает нечеткий поиск текста — Томаш Карабела на канале Big Python YouTube Channel (@BigPythonDev)
  3. Что такое Fuse.js? — Документация по Fuse.js (автор @kirorisk)
  4. HTML datalist — Mozilla Developer Network
  5. Опция HTML — Mozilla Developer Network
  6. Есть ли способ заставить HTML5-даталист использовать нечеткий поиск? — Stack Overflow (ответил @AlexandreElsho1)
  7. Приблизительное сопоставление строк — Википедия
  8. Фонетические алгоритмы нечеткого сопоставления строк — Мехул Гупта (@mehulgupta7991)
  9. Soundex — алгоритм поиска строк на основе фонетики — Википедия
  10. Расстояние Хэмминга — Википедия
  11. RapidFuzz: Ускорение фаззинга с помощью генеративных адверсариальных сетей — Aoshuang Ye, Lina Wang, Lei Zhao, Jianpeng Ke, Wenqi Wang, and Qinliang Liu
  12. Последние работы, связанные с фаззингом — Чэн Вэнь

Оцените статью
Procodings.ru
Добавить комментарий