Javascript sort an array by matching to string

3
votes

I have an array containing results form a geolocation code. I want to sort it by the closest match to the term that I have searched.

Example. Search: Pizza. 

Array: Pizza Uno, Pizzeria Uno, Burgers and Pizzeria, Cino Pizzeria.

The sorted array should be:

Pizza Uno,
Pizzeria Uno,
Burgers and Pizzeria,
Cino Pizzeria.

Thanks for your help.

3
javascriptsorting
You'll have to describe the algorithm you want to use for determining "closest"-ness. Obviously a perfect match can be highest, but what determines the order of the other three items that all have the same partial match? – jfriend00
Why is "Burgers and Pizzeria" a closer match to "Pizza" than "Cino Pizzeria"? – Mark Byers
Good questions. I don't know what the best algorithm would be. I was thinking of matching the search string and then displaying the ones with same match by alphabetical order. Hence why Burgers and Pizzeria is closer then Cino Pizzeria. Same match but higher in alphabetical – Leonardo Amigoni

3 Answers

4
votes

A really basic algorithm that'd work, would be to sort based on what percentage of the total string length, the match takes up. So an exact match of "Pizza" would be 5/5 (100%), the "Pizza Uno" match would be 5/9, "Pizzeria Uno" is 4/12, and so on. This is one of the core components of the MySQL natural sorting algorithm at its most basic.

2
votes

What about something like this? It was my first approach for getting the closest color name, depending on a hex-color.

There's of course a better solution out there, you could for example take a look at the sift algorithm which is really much faster than levenshtein's approach.

However this should work for you as expected.

Array.closest = (function () {
    function levenshtein(s, t) {
        if (!s.length) return t.length;
        if (!t.length) return s.length;

        return Math.min(
            levenshtein((s.substring(1), t) + 1,
            levenshtein((t.substring(1), s) + 1,
            levenshtein((s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
        );
    }

    return function (arr, str) {
        return arr.sort(function (a, b) {
            return levenshtein((a, str) - levenshtein((b, str);
        });
    };
}());


var arr = ['Pizza Uno', 'Pizzeria Uno', 'Burgers and Pizzeria', 'Cino Pizzeria.'];
Array.closest(arr, 'Pizza') // => ['Pizza Uno', 'Pizzeria Uno', 'Cino Pizzeria.', 'Burgers and Pizzeria'];
1
votes

You can try calculating the Levenshtein Distance between 2 strings. It's basically the number of steps it will take to make the two strings identical.