Autocomplete com fuzzy search e Fuse.js
Aprenda como criar uma lista de sugestões enquanto você digita um nome de navegador
O 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.
O 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.
Hamming 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.
Escolhendo um algoritmo de Fuzzy search
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.
HTML 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.
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>
.
Fuzzy 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
.
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;
JavaScriptexport 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
.
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);
JavaScriptconst 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
.
export const fuzzySearch = (list, keys = []) => {
const fuse = new Fuse(list, { ...FUSE_OPTIONS, keys });
return (pattern) => fuse.search(pattern);
};
JavaScriptexport 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.
// 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);
});
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
const FUSE_OPTIONS = {
isCaseSensitive: false,
includeScore: true,
shouldSort: true,
threshold: 0.6
};
JavaScriptconst 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
Conclusã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
Tenha um bom dia, e eu vejo você na próxima.
Referências
- Exemplos de código no GitHub - Lucas Paganini
- Como uma Fuzzy Text Search Funciona - Tomáš Karabela no canal do youtube do Big Python (@BigPythonDev)
- O que é Fuse.js? - Documentação do Fuse.js (por@kirorisk)
- HTML datalist - Mozilla Developer Network
- HTML option - Mozilla Developer Network
- Há uma maneira de fazer uma HTML5 datalist usar uma fuzzy search? - Stack Overflow (answered by @AlexandreElsho1)
- Approximate String Matching - Wikipedia
- Algoritmo de Fuzzy string matching baseado na fonética - Mehul Gupta (@mehulgupta7991)
- Soundex - Algoritmo de string searching baseado na fonética - Wikipedia
- Hamming distance - Wikipedia
- RapidFuzz: Acelerando a fuzzing via Generative Adversarial Networks - Aoshuang Ye, Lina Wang, Lei Zhao, Jianpeng Ke, Wenqi Wang, and Qinliang Liu
- Trabalhos recentes relacionados ao Fuzzing - Cheng Wen