JavaScript fuzzy search

Question

I'm working on this filtering thing where I have about 50-100 list items. And each items have markup like this:

<li>
  <input type="checkbox" name="services[]" value="service_id" />
  <span class="name">Restaurant in NY</span>
  <span class="filters"><!-- hidden area -->
    <span class="city">@city: new york</span>
    <span class="region">@reg: ny</span>
    <span class="date">@start: 02/05/2012</span>
    <span class="price">@price: 100</span>
  </span>
</li>

I created markup like this because I initally used List.js

So, probably you guessed already, what I want is to do searches like this:@region: LA @price: 124 and so on. The problem is that i also want to display more than one item, in order to select more than... one :)

I assume this needs fuzzy search, but the problem is that i didn't find anything functional.

Any idea or starting point?

// edit: because I have a fairly small amount of items, I would like a client side solution.

Answer 1

Another (simple) solution. Non case-sensitive and ignores order of the letters.

It performs a check for every letter of the search-term. If the original string contains that letter, it will count up (or down if it doesn't). Based on the ratio of matches / string-length it will return true or false.

String.prototype.fuzzy = function(term, ratio) {
    var string = this.toLowerCase();
    var compare = term.toLowerCase();
    var matches = 0;
    if (string.indexOf(compare) > -1) return true; // covers basic partial matches
    for (var i = 0; i < compare.length; i++) {
        string.indexOf(compare[i]) > -1 ? matches += 1 : matches -=1;
    }
    return (matches/this.length >= ratio || term == "")
};

Examples:

("Test").fuzzy("st", 0.5) // returns true
("Test").fuzzy("tes", 0.8) // returns false cause ratio is too low (0.75)
("Test").fuzzy("stet", 1) // returns true
("Test").fuzzy("zzzzzest", 0.75) // returns false cause too many alien characters ("z")
("Test").fuzzy("es", 1) // returns true cause partial match (despite ratio being only 0.5)

Answer 2

I was looking for "fuzzy search" in javascript but haven't found a solution here, so I wrote my own function that does what I need.

The algorithm is very simple: loop through needle letters and check if they occur in the same order in the haystack:

String.prototype.fuzzy = function (s) {
    var hay = this.toLowerCase(), i = 0, n = -1, l;
    s = s.toLowerCase();
    for (; l = s[i++] ;) if (!~(n = hay.indexOf(l, n + 1))) return false;
    return true;
};

e.g.:

('a haystack with a needle').fuzzy('hay sucks');    // false
('a haystack with a needle').fuzzy('sack hand');    // true