Filter JavaScript Objects with Fuzzy Search

From time to time you will a simple way to search through an collection of data to filter based on user input. Google often makes search seem like wizardy but you may be surprised how far you can get with using a fuzzy search.

What is Fuzzy Search?

The concept of fuzzy search is dead simple. It will search all of the properties in an object to see if any of them contain your search. Let's take a look at this example:

var items = [{
    name: "Jon Snow",
    actor: "Kit Harington"
}, {
    name: "Daenerys Targaryen",
    actor: "Emilia Clark"
}]

var search = 'Kit Har';
var found = [];
items.forEach(i => {
    var props = 0;
    // Take a look at each property in the object
    for (var prop in i) {
        // Check if property value contains search
        if (i[prop].indexOf(search) > -1) {
            props++;
        }
    }
    // If the search query was found in any properties
    if (props >= 1) {
        found.push(i)
    }
})

// found = [{ name: "Jon Snow", lastName: "Kit Harington"}]

The logic loops through each item in the array, breaks down the properties then checks if the search was found inside the value of the properties. Trying out different combinations you can start to see its usefulness. For example, searching for Jon S or Harington will both return Jon Sno.

For some applications this may be enough, but I find for requiring exact matching string in your query can make finding items annoying. For example, if you wanted to search all items with a first initial of D and last name Targaryen you are out of luck and reversing the query (use the last name first and first name second) will also get you nothing.

Keywords

By splitting our search into keywords we can now compare each word against the properties. Counting if all keywords were found with our fuzzy search will start narrowing your search the more specific you get.

Let's get right into the code while moving everything into a function for re-usability.

var items = [{
    name: "Jon Snow",
    lastName: "Kit Harington"
}, {
    name: "Daenerys Targaryen",
    actor: "Emilia Clark"
}]

function fuzzySearch(items, query) {
    // Split up the query by space
    var search = query.split(' ');
    var found = [];
    items.forEach(i => {
        // Extra step here to count each search query item (after splitting by space)
        var matches = 0;
        search.forEach(s => {
            var props = 0;
            for (var prop in i) {
                // Check if property value contains search
                if (i[prop].indexOf(s) > -1) {
                    props++;
                }
            }
            if (props >= 1) {
                // Found a matching prop, increase our match count
                matches++;
            }
        })
        if (matches == search.length) {
            // if all search paramters were found
            found.push(i);
        }
    })
    return found;
}

fuzzySearch(items, "D Tar");
// returns [ { name: "Daenerys Targaryen",  actor: "Emilia Clark" }]

As you can see our fuzzy logic still applies, but with extra logic of splitting the query into keywords before comparing against the properties.

There you have it! With just a few lines you now have a very powerful and versatile search function that can get good results on many data sets.

Using reduce()

It is no secret that the above function keeps things simple for demonstration sake. Creating a new result set for our found items is very redundant when we have tools like reduce() at our finger tips. Below is an example of the sample function using reduce for better performance:

function fuzzySearch(items, query) {
    var search = query.split(' ');
    var ret = items.reduce((found, i) => {
        var matches = 0;
        search.forEach(s => {
            var props = 0;
            for (var prop in i) {
                if (i[prop].indexOf(s) > -1) {
                    props++;
                }
            }
            if (props >= 1) {
                matches++;
            }
        })
        if (matches == search.length) {
            console.log(i, found, 'was found');
            found.push(i);
        }
        return found;
    }, [])
    return ret;
}

Extending to all Arrays

If you find you are using this a lot in a project, make your life easier by extending fuzzySearch to the Array object. This will make items.fuzzySearch("Kit Har") possible.

Array.prototype.fuzzySearch = function (query) {
    var search = query.split(' ');
    var ret = this.reduce((found, i) => {
        var matches = 0;
        search.forEach(s => {
            var props = 0;
            for (var prop in i) {
                if (i[prop].indexOf(s) > -1) {
                    props++;
                }
            }
            if (props >= 1) {
                matches++;
            }
        })
        if (matches == search.length) {
            console.log(i, found, 'was found');
            found.push(i);
        }
        return found;
    }, [])
    return ret;
}