4 ms·

I've used Levenshtein distance to sort fuzzysearch results by order of relevance. Worked very well combined with a special-case to sort exact matches first.

• Filligree 7y ago
  Why would a special case be necessary? The edit distance for two identical strings is zero.
  • simcop2387 7y ago
    Probably a case of speed, edit distance can take longer to calculate even in the case of 0.
  • pitaj 7y ago
    It's an autocompletion for emoji, so several letters will be missing regardless. I'm that case, a long word like "helicopter" will be placed at a greater distance than "elipsis" despite being what I want "heli" to actually match, so I just added a "startsWith" check to override such issues.
    • LorenPechtel 7y ago
      Weight missing characters very low.
    • tomjakubowski 7y ago
      Have you experimented with n-grams for approximate matching? I've found it works very well, especially if you add special characters to the alphabet to mark "start of string" and "end of string": like "heli" would have trigrams {"^he", "hel", "eli", "li$"}, which would certainly be a better trigram match to "helicopter" than to "elipsis" (sic). https://en.wikipedia.org/wiki/N-gram#n-grams_for_approximate_matching https://en.wikipedia.org/wiki/N-gram#n-grams_for_approximate...
      • pitaj 7y ago
        I haven't, mostly because it's fast enough already and I don't really feel like implementing this stuff myself.
        • simcop2387 7y ago
          Postgres has support for trigrams and indexes on them. I used them to help match addresses at a previous company, worked fantastically for the part we used them for.
          • pitaj 7y ago
            It's a client-side library.
• mattrp 7y ago
  Yes I liked its implementation in the fuzzywuzzy python library.. worked like a charm when trying to match street addresses and business names.
• Rafert 7y ago
  I used the Jaro-Winkler algorithm[0] for this and and it worked pretty well. It ranks common prefixes higher. [0]: https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance