Autocomplete with fuzzy search and Fuse.js
Tags: webdev, tutorial, javascript
Published: 2022-05-30 20:41:08

Learn how to create a list of suggestions while you type a browser name

{% embed https://www.youtube.com/embed/85wmpNh3RRs %}
_See this and many other articles at [lucaspaganini.com](lucaspaganini.com)_

## What we are going to build

Today, I'll show you how to implement an input autocomplete feature using fuzzy search.
To put things in practice, we will create a page, where a list of suggestions will show while you type a browser name.

## What is fuzzy (approximate) search

What is a "fuzzy" search?

A fuzzy search searches for text that matches a term approximately instead of exactly.

In an exact search, "come" would never match "Chrome" because there's no "come" in "Chrome". There's no room for interpretation, it's either true or false. That, of course, is not very human-friendly. If we're searching for something, there's a chance that we might not even know how to spell it correctly.

Fuzzy search is a lot more flexible. Instead of true or false, we have degrees of truth. A fuzzy search will tell us how close two strings are. There are many different fuzzy search algorithms.

## Hamming distance

As an educational example, let me show you a very simple fuzzy search algorithm called Hamming distance.

Given two strings with the same length, the Hamming distance between them is the minimum number of substitutions required to change one string into the other. For example, the Hamming distance between "Daniel" and "Denise" is 3 because we'd have to change 3 letters for them to match.

D`a`ni`e``l` vs. D`e`ni`s``e`

We could implement a fuzzy search mechanism that calculates the Hamming distance between the search keyword and all possible results, and then we would sort the results, showing the ones with the lowest Hamming distance first.

Of course, that would be a terrible user experience since our algorithm only works with strings that have the same length. But it's a valid example. It uses the Hamming distance to determine how close two strings are.

## Choosing a fuzzy search algorithm

In practice, you have to choose the algorithm that best suits your needs. Most of the time, you will simply look for the most performant one, but other times, you might choose an algorithm based on some specialized features. For example, there's a fuzzy search algorithm that can search strings based on their phonetics, which might be more important than performance, depending on your use case.

You also need to consider how much data you're dealing with. If you want to perform a fuzzy search in a huge dataset, doing it in the frontend is probably not the best idea. Even if your end-users have a lot of computational power, they would need to download the whole dataset to run the search in the frontend.

Also, running searches in the backend gives you a lot more options. The two most popular ones are ElasticSearch and Algolia.

In this post, we will be dealing with a small dataset, so we will run our search in the frontend.

## Native HTML autocomplete with `<datalist>`

A simple way to add autocomplete to an input element is to use a `<datalist>`. This doesn't even require any JavaScript, just HTML.

![HTML datalist](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/540z8krb13vyoq0aurc3.png)
_Check this example [here](https://www.lucaspaganini.com/academy/autocomplete-with-fuzzy-search-and-fuse-js)_ 

The search algorithm is pretty fast. It uses exact search, removes spaces, and ignores the case sensitivity.

But there's a deal-breaker… the search algorithm is not customizable. And neither are the list styles. So that clearly won't work for real-world projects, where we have a custom design to comply with. That's why we are going to create a custom component instead of using a `<datalist>`.

## Custom fuzzy search with Fuse.js

For our fuzzy search algorithm, I choose to use Fuse.js. It's performant, well documented, and actively maintained.
I did everything with pure HTML, CSS, and JavaScript. I didn't want to use a framework for this example to avoid unnecessary complexity. I'm leaving a link to the code in the references section. You'll see that there's no compilation process, I'm just serving the files in the `public/` folder.

My constants are set in the `config.mjs` file.

```js
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;
```

The custom dropdown element is declared in the `dropdown-element.mjs` file.

```js
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);
```

Our fuzzy search function using Fuse.js is defined in the `fuzzy-search.mjs` file.

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

And the `main.mjs` file connects everything: it's listening to changes in our input, running the fuzzy search, and displaying the results.

```js
// 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 provides a lot of options, and they're all very descriptive. Pay special attention to the `threshold` option. It controls how close two strings should be for a match to happen. Setting it to 0 is the same as using an exact search, and setting it to 1 would match anything.

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

I created a playground for you to better understand Fuse.js! Check it out:

![Fuzzy playground](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kypj3qh04t0mqszkxyw6.png)
 _Check this example [here](https://www.lucaspaganini.com/academy/autocomplete-with-fuzzy-search-and-fuse-js)_ 

## Conclusion

As always, references are in the references section. Play around with the codebase, and feel free to contact me if you have any questions.

<p>If this post was helpful, consider <app-newsletter-modal-trigger>subscribing to the newletter</app-newsletter-modal-trigger> for more web development tutorials. And if your company is looking for remote web developers, consider contacting me and my team [here](https://www.lucaspaganini.com/contact)</p>

Have a great day, and I’ll see you in the next one.

## References

1. [Code examples](https://github.com/LucasPaganini/published-content/tree/master/autocomplete-fuzzy-search) - Lucas Paganini<br>
2. [How Fuzzy Text Search Works](https://www.youtube.com/watch?v=SoZ1CVU2DdE) - Tomáš Karabela at the Big Python YouTube Channel ([@BigPythonDev](https://twitter.com/BigPythonDev))<br>
3. [What is Fuse.js?](https://fusejs.io/) - Fuse.js Documentation (by [@kirorisk](https://twitter.com/kirorisk))<br>
4. [HTML datalist](https://developer.mozilla.org/en-US/docs/Web/HTML/Element/datalist) - Mozilla Developer Network<br>
5. [HTML option](https://developer.mozilla.org/en-US/docs/Web/HTML/Element/option) - Mozilla Developer Network<br>
6. [Is there a way to make an HTML5 datalist use a fuzzy search?](https://stackoverflow.com/questions/59326096/is-there-a-way-to-make-an-html5-datalist-use-a-fuzzy-search) - Stack Overflow (answered by [@AlexandreElsho1](https://twitter.com/AlexandreElsho1))<br>
7. [Approximate String Matching](https://en.wikipedia.org/wiki/Approximate_string_matching) - Wikipedia<br>
8. [Phonetics based Fuzzy string matching algorithms](https://medium.com/data-science-in-your-pocket/phonetics-based-fuzzy-string-matching-algorithms-8399aea04718) - Mehul Gupta (@mehulgupta7991)<br>
9. [Soundex - Phonetics based string searching algorithm](https://en.wikipedia.org/wiki/Soundex) - Wikipedia<br>
10. [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) - Wikipedia<br>
11. [RapidFuzz: Accelerating fuzzing via Generative Adversarial Networks](https://www.sciencedirect.com/science/article/abs/pii/S0925231221010122) - Aoshuang Ye, Lina Wang, Lei Zhao, Jianpeng Ke, Wenqi Wang, and Qinliang Liu<br>
12. [Recent Papers Related To Fuzzing](https://github.com/wcventure/FuzzingPaper) - Cheng Wen<br>