How can I measure string similarity between sentences?

Question

I have the following task.

Given is a list of strings like so:

        var strings = [
            'Steve jobs created the iPod when he was at Apple',
            'I really like the new Macbook by Apple',
            'Jony Ive was concerned being fired by Steve Jobs after his return to Apple',
            'The new Macbook has just one USB-C type connector',
            'I like bananas',
            'The brezels I can buy in my local store are much better than the ones in the supermarket',
            'the',
            'foo',
            'Steve'
        ];

I now want to compare each string with each other and for each comparison I want to find out how similar they are to each other on a scale from 0-1 (or 0%-100%).

So, I googled around a little and found this: Similarity String Comparison in Java

So, I followed the instruction there, and ported the method similarity(String s1, String s2) to JavaScript:

        function similarity(s1, s2) {
            var longer = s1;
            var shorter = s2;
            if (s1.length < s2.length) {
                longer = s2;
                shorter = s1;
            }
            var longerLength = longer.length;
            if (longerLength == 0) {
                return 1.0;
            }
            return (longerLength - longer.LevenshteinDistance(shorter)) / longerLength;
        }

As comparison algorithm I used Levenshtein:

        String.prototype.LevenshteinDistance = function (s2) {
            var array = new Array(this.length + 1);
            for (var i = 0; i < this.length + 1; i++)
                array[i] = new Array(s2.length + 1);

            for (var i = 0; i < this.length + 1; i++)
                array[i][0] = i;
            for (var j = 0; j < s2.length + 1; j++)
                array[0][j] = j;

            for (var i = 1; i < this.length + 1; i++) {
                for (var j = 1; j < s2.length + 1; j++) {
                    if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1];
                    else {
                        array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1);
                        array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1);
                    }
                }
            }
            return array[this.length][s2.length];
        };

So, as a test I ran a full loop comparing each string with each other and printing the result like this:

            for (var i in strings){
                var s = strings[i];
                print('Checking string: "' + s + '"');
                for (var j in strings){
                    print('-----');
                    var s2 = strings[j];
                    print('vs "' + s2 + '"');
                    var sim = similarity(s, s2);
                    print('Similarity: ' + Math.round(sim*100) + '%');
                }
                print('<br>////// NEXT /////////////////////////////////////////////////<br>');
            }

Ok, now this is the result: https://jsfiddle.net/wxksfa4w/

Now, looking at the results I get some good matches but also some that are completely unrelated to each other, for example:

"Steve jobs created the iPod when he was at Apple" and "I like bananas" match for 13%?

"Steve jobs created the iPod when he was at Apple" and just "Steve" match for just 10% although the exact same word "Steve" is used as in the first sentence?

How can I get better semantic results? Is Levenshtein the wrong algorithm? From what I understood is that Levenshtein counts the numbers of steps of how to change sentence 1 to sentence 2. So, the length of a string seems to have a major impact on the result even if there is semantic similarity.

Any advice?

Answer 1

You should probably be using the presence of words in both sentences as a high hint of similarity. A simple way of doing it is using each sentence as a bag of words and using tf-idf

Answer 2

What you could use is normalized Longest Common Subsequence (LCS) similarity: you compute the length of the longest common subsequence, then you divide by the length of the smallest string.

By the way, the longest common subsequence should not be confused with the longest common substring: for the two strings "This is a long string" and "This is another string, really..."

The longest common subsequence is "This is a string"
The longest common substring is "This is a"

And the relative LCS similarity is 16/21 = 0.76

You can find a Java implementation of LCS similarity here: https://github.com/tdebatty/java-string-similarity

And a Javascript implementation is available on wikibooks: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence#JavaScript

Answer 3

SimMetrics has java code for the Smith Waterman Gotoh algorithm which is great for comparing string sentences. I've found Smith Waterman Gotoh to be the superior algorithm for comparing larger strings such as sentences and article titles.