Autocomplete com fuzzy search e Fuse.js

Aprenda como criar uma lista de sugestões enquanto você digita um nome de navegador

LinkO que nós vamos construir hoje

Hoje, eu irei te mostrar como implementar uma funcionalidade de input autocomplete usando fuzzy search.

Para colocar as coisas em prática, nós iremos criar uma página, onde uma lista de sugestões irá mostrar um nome de navegador enquanto você escreve.

LinkO que é fuzzy search(busca aproximada)

O que é uma "fuzzy" search?

Uma fuzzy search procura por texto que corresponde a um termo aproximado ao invés de exato.

Em uma procura exata, "come" nunca irá corresponder a "Chrome" porque não há "come" em "Chrome". Não há lugar para interpretação, é verdadeiro ou falso. Isso, claro, não é muito amigável para humanos. Se nós estamos procurando por algo, há uma possibilidade de nem sequer sabermos como soletrar corretamente.

Fuzzy search é muito mais flexível. Ao invés de verdadeiro ou falso, nós temos graus de verdadeiro. Uma fuzzy search irá nos falar o quão perto duas strings estão. Há muitos algoritmos de fuzzy search, um deles é o hamming distance.

LinkHamming distance

Como um exemplo educacional, me deixe mostrar para você um algoritmo de fuzzy search bem simples chamado hamming distance.

Dadas duas strings com a mesma distância, a distância de martelamento(Hamming distance) entre elas é o número mínimo de substituições necessárias para que uma string seja convertida na outra string. Por exemplo, a hamming distance entre "Daniel" e "Denise" é 3 pois teriamos que mudar 3 letras para que correspondessem.

Daniel vs. Denise

Nós poderiamos implementar um mecanismo de fuzzy search que calcula a hamming distance entre a palavra chave e todas as possibilidades de resultado, e então ordenaríamos os resultados, mostrando os que possuem menor hamming distance primeiro.

Claro, seria uma experiência de usuário horrível já que nosso algoritmo apenas funciona com strings que possuem o mesmo comprimento. Mas é um exemplo válido. Ele usa a hamming distance pata determinar o quão próximas duas strings estão.

Na prática, você precisa escolher o algoritmo que melhor se encaixa na suas necessidades. Na maior parte do tempo, você simplesmente olhará para o que tiver mais performance, mas em outros casos, Você poderá escolher um algoritmo baseado em algumas funcionalidades especializadas. Por exemplo, há um algoritmo de fuzzy search que pode procurar strings baseado nas vogais, que podem ser mais importantes que a performance, dependendo da sua necessidade.

Você também precisa considerar com quanto dado você esta lidando. Se você quer fazer uma fuzzy search com um enorme número de dados, fazer isso no frontend provavelmente não é a melhor ideia. Mesmo que os seus usuários finais tenham muito poder computacional, eles precisariam baixar todos os dados para executar a pesquisa no frontend.

Além disso, executar pesquisas no backend nos dá muito mais opções. As duas mais populares são ElasticSearch e Algolia.

Nesse post, nós iremos lidar com um número pequeno de dados, então executaremos nossa pesquisa no frontend.

LinkHTML autocomplete nativo com <datalist>

Uma forma simples de adicionar autocomplete em um elemento de input é usar um <datalist>. Isso nem sequer necessita de JavaScript, apenas HTML.

Faça você mesmo

O algoritmo de procura é muito rápido. Ele usa busca exata, remove espaços e ignora letras maúsculas e minúsculas.

Mas há uma problema... o algoritmo de pesquisa não é customizável. E os estilos de lista também não. Portanto, isso claramente não vai funcionar para projetos do mundo real, onde temos um design customizado a cumprir. É por isso que vamos criar um componente customizado em vez de utilizarmos um <datalist>.

LinkFuzzy search customizado com Fuse.js

Para o nosso algoritmo de fuzzy search, eu escolhi usar Fuse.js. É performático, bem documentado e mantido ativamente. Eu fiz tudo com HTML, CSS e JavaScript. Eu não queria usar um framework para esse exemplo para evitar complexidade desnecessária. Eu estou deixando um link para o código na sessão de referências. Você verá que não há processo de compilação, eu apenas estou servindo meus arquivos na pasta public/.

Minhas constantes estão definidas no arquivo config.mjs.

JavaScript
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;

O elemento customizado dropdown é declarado no arquivo dropdown-element.mjs.

JavaScript
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);

Nossa função de fuzzy search que usa Fuse.js é definida no arquivo fuzzy-search.mjs.

JavaScript
export const fuzzySearch = (list, keys = []) => {
  const fuse = new Fuse(list, { ...FUSE_OPTIONS, keys });
  return (pattern) => fuse.search(pattern);
};

E o arquivo main.mjs conecta tudo: ele está escutando mudanças no nosso input, executando a fuzzy search, e mostrando os resultados.

JavaScript
// 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 oferece muitas opções, e todas elas são muito descritivas. Dê uma atenção especial para a opção threshold. Ela controla o quão próximas duas strings devem estar para uma correspondência acontecer. Colocando em 0 é o mesmo que usar uma busca exata(exact search), e colocar ele no 1 corresponderia à qualquer coisa

JavaScript
const FUSE_OPTIONS = {
  isCaseSensitive: false,
  includeScore: true,
  shouldSort: true,
  threshold: 0.6
};

Eu montei um playground pra você entender melhor como funciona! Dá uma olhada:

Parâmetros do Fuse.js

Fuzzy Search

Google Chrome

Opera

Google Chrome for Android

Opera Mini

Blackberry Browser

Opera for Android

LinkConclusão

Como sempre, referências estão na sessão de referências. Brinque um pouco com a base de código e sinta-se livre para me contatar se você tiver qualquer dúvida.

Se esse post foi útil, considere se inscrever na minha newsletter para mais tutoriais de desenvolvimento web. Se sua empresa está procurando por desenvolvedores web remotos, considere contatar eu e meu time [aqui](https://www.lucaspaganini.com/contact)

Tenha um bom dia, e eu vejo você na próxima.

LinkReferências

  1. Exemplos de código no GitHub - Lucas Paganini
  2. Como uma Fuzzy Text Search Funciona - Tomáš Karabela no canal do youtube do Big Python (@BigPythonDev)
  3. O que é Fuse.js? - Documentação do Fuse.js (por@kirorisk)
  4. HTML datalist - Mozilla Developer Network
  5. HTML option - Mozilla Developer Network
  6. Há uma maneira de fazer uma HTML5 datalist usar uma fuzzy search? - Stack Overflow (answered by @AlexandreElsho1)
  7. Approximate String Matching - Wikipedia
  8. Algoritmo de Fuzzy string matching baseado na fonética - Mehul Gupta (@mehulgupta7991)
  9. Soundex - Algoritmo de string searching baseado na fonética - Wikipedia
  10. Hamming distance - Wikipedia
  11. RapidFuzz: Acelerando a fuzzing via Generative Adversarial Networks - Aoshuang Ye, Lina Wang, Lei Zhao, Jianpeng Ke, Wenqi Wang, and Qinliang Liu
  12. Trabalhos recentes relacionados ao Fuzzing - Cheng Wen

Assine a nossa Newsletter e seja avisado quando eu lançar um curso, postar um vídeo ou escrever um artigo.

Campo obrigatório
Campo obrigatório