DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Lucas Paganini
Lucas Paganini

Posted on • Originally published at lucaspaganini.com

Autocomplete with fuzzy search and Fuse.js

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


See this and many other articles at 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.

Daniel vs. Denise

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
Check this example here

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.

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;
Enter fullscreen mode Exit fullscreen mode

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

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);
Enter fullscreen mode Exit fullscreen mode

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

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

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

// 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);
});
Enter fullscreen mode Exit fullscreen mode

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.

const FUSE_OPTIONS = {
  isCaseSensitive: false,
  includeScore: true,
  shouldSort: true,
  threshold: 0.6
};
Enter fullscreen mode Exit fullscreen mode

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

Fuzzy playground
Check this example here

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.

If this post was helpful, consider subscribing to the newletter 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)

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

References

  1. Code examples - Lucas Paganini
  2. How Fuzzy Text Search Works - TomΓ‘Ε‘ Karabela at the Big Python YouTube Channel (@BigPythonDev)
  3. What is Fuse.js? - Fuse.js Documentation (by @kirorisk)
  4. HTML datalist - Mozilla Developer Network
  5. HTML option - Mozilla Developer Network
  6. Is there a way to make an HTML5 datalist use a fuzzy search? - Stack Overflow (answered by @AlexandreElsho1)
  7. Approximate String Matching - Wikipedia
  8. Phonetics based Fuzzy string matching algorithms - Mehul Gupta (@mehulgupta7991)
  9. Soundex - Phonetics based string searching algorithm - Wikipedia
  10. Hamming distance - Wikipedia
  11. RapidFuzz: Accelerating fuzzing via Generative Adversarial Networks - Aoshuang Ye, Lina Wang, Lei Zhao, Jianpeng Ke, Wenqi Wang, and Qinliang Liu
  12. Recent Papers Related To Fuzzing - Cheng Wen

Top comments (0)

This post blew up on DEV in 2020:

js visualized

πŸš€βš™οΈ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! πŸ₯³

Happy coding!