A better similarity ranking algorithm for variable length strings

Simon White of Catalysoft wrote an article about a very clever algorithm that compares adjacent character pairs that works really well for my purposes:

http://www.catalysoft.com/articles/StrikeAMatch.html

Simon has a Java version of the algorithm and below I wrote a PL/Ruby version of it (taken from the plain ruby version done in the related forum entry comment by Mark Wong-VanHaren) so that I can use it in my PostgreSQL queries:

CREATE FUNCTION string_similarity(str1 varchar, str2 varchar)
RETURNS float8 AS '

str1.downcase! 
pairs1 = (0..str1.length-2).collect {|i| str1[i,2]}.reject {
  |pair| pair.include? " "}
str2.downcase! 
pairs2 = (0..str2.length-2).collect {|i| str2[i,2]}.reject {
  |pair| pair.include? " "}
union = pairs1.size + pairs2.size 
intersection = 0 
pairs1.each do |p1| 
  0.upto(pairs2.size-1) do |i| 
    if p1 == pairs2[i] 
      intersection += 1 
      pairs2.slice!(i) 
      break 
    end 
  end 
end 
(2.0 * intersection) / union

' LANGUAGE 'plruby';

Works like a charm!

String Similarity Metrics contains an overview of many different metrics used in string comparison (Wikipedia has an overview as well). Much of these metrics is implemented in a library simmetrics.

Yet another example of metric, not included in the given overview is for example compression distance (attempting to approximate the Kolmogorov's complexity), which can be used for a bit longer texts than the one you presented.

You might also consider looking at a much broader subject of Natural Language Processing. These R packages can get you started quickly (or at least give some ideas).

And one last edit - search the other questions on this subject at SO, there are quite a few related ones.

Why not for a JavaScript implementation, I also explained the algorithm.

Algorithm

• Input : France and French.
• Map them both to their upper case characters (making the algorithm insensitive to case differences), then split them up into their character pairs:

FRANCE: {FR, RA, AN, NC, CE}
FRENCH: {FR, RE, EN, NC, CH}

• Find there intersection:

• Result:

Implementation

function similarity(s1, s2) {
    const
        set1 = pairs(s1.toUpperCase()), // [ FR, RA, AN, NC, CE ]
        set2 = pairs(s2.toUpperCase()), // [ FR, RE, EN, NC, CH ]
        intersection = set1.filter(x => set2.includes(x)); // [ FR, NC ]
    // Tips: Instead of `2` multiply by `200`, To get percentage.
    return (intersection.length * 2) / (set1.length + set2.length);
}
function pairs(input) {
    const tokenized = [];
    for (let i = 0; i < input.length - 1; i++)
        tokenized.push(input.substring(i, 2 + i));

    return tokenized;
}
console.log(similarity("FRANCE", "FRENCH"));

Ranking Results By ( Word - Similarity )

1. Sealed - 80%
2. Healthy - 55%
3. Heard - 44%
4. Herded - 40%
5. Help - 25%
6. Sold - 0%

From same original source.

What about Levenshtein distance, divided by the length of the first string (or alternatively divided my min/max/avg length of both strings)? That has worked for me so far.

**I've converted marzagao's answer to Java.**

import org.apache.commons.lang3.StringUtils; //Add a apache commons jar in pom.xml

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SimilarityComparator {
public static void main(String[] args) {
    String str0 = "Nischal";
    String str1 = "Nischal";
    double v = compareStrings(str0, str1);
    System.out.println("Similarity betn " + str0 + " and " + str1 + " = " + v);

}

private static double compareStrings(String str1, String str2) {
    List<String> pairs1 = wordLetterPairs(str1.toUpperCase());
    List<String> pairs2 = wordLetterPairs(str2.toUpperCase());

    int intersection = 0;
    int union = pairs1.size() + pairs2.size();

    for (String s : pairs1) {
        for (int j = 0; j < pairs2.size(); j++) {
            if (s.equals(pairs2.get(j))) {
                intersection++;
                pairs2.remove(j);
                break;
            }
        }
    }
    return (2.0 * intersection) / union;
}

private static List<String> wordLetterPairs(String str) {
    List<String> AllPairs = new ArrayList<>();
    String[] Words = str.split("\\s");
    for (String word : Words) {
        if (StringUtils.isNotBlank(word)) {
            String[] PairsInWord = letterPairs(word);
            Collections.addAll(AllPairs, PairsInWord);
        }
    }
    return AllPairs;
}

private static String[] letterPairs(String str) {
    int numPairs = str.length() - 1;
    String[] pairs = new String[numPairs];
    for (int i = 0; i < numPairs; i++) {
        try {
            pairs[i] = str.substring(i, i + 2);
        } catch (Exception e) {
            pairs[i] = str.substring(i, numPairs);
        }
    }
    return pairs;
  }
}