Alternative to Levenshtein and Trigram

Question

Say I have the following two strings in my database:

(1) 'Levi Watkins Learning Center - Alabama State University'
(2) 'ETH Library'

My software receives free text inputs from a data source, and it should match those free texts to the pre-defined strings in the database (the ones above).

For example, if the software gets the string 'Alabama University', it should recognize that this is more similar to (1) than it is to (2).

At first, I thought of using a well-known string metric like Levenshtein-Damerau or Trigrams, but this leads to unwanted results as you can see here:

http://fuzzy-string.com/Compare/Transform.aspx?r=Levi+Watkins+Learning+Center+-+Alabama+State+University&q=Alabama+University

http://fuzzy-string.com/Compare/Transform.aspx?r=ETH+Library&q=Alabama+University

Difference to (1): 37
Difference to (2): 14

(2) wins because it is much shorter than (1), even though (1) contains both words (Alabama and University) of the search string.

I also tried it with Trigrams (using the Javascript library fuzzySet), but I got similar results there.

Is there a string metric that would recognize the similarity of the search string to (1)?

Answer 1

You could try the Word Mover's Distance https://github.com/mkusner/wmd instead. One brilliant advantage of this algorithm is that it incorporates the implied meanings while computing the differences between words in documents. The paper can be found here

Answer 2

You should change your approach:

levenshtein Distance is good at calculating similarities in units either they are 'characters' or 'words'.

Conceptually you are considering Alabama and university (2 words) as 2 units and you want to calculate the distance between the words for which levenshtein distance should mean how many words are in between Alabama and University which should be 1.

But, you are trying to apply levenshtein algorithm that is implemented for characters within a word. This implementation will only work for matching the single words NOT sentences.

Its better you should implement your own levenshtein algorithm (using BK-Tree) for 'words' on the top and within each match, you again match the each word using levenshtein for 'characters'.

your result for (1) should be a match with distance 1 with that algorithm and No match for (2).