162

I'm looking for a string similarity algorithm that yields better results on variable length strings than the ones that are usually suggested (levenshtein distance, soundex, etc).

For example,

Given string A: "Robert",

Then string B: "Amy Robertson"

would be a better match than

String C: "Richard"

Also, preferably, this algorithm should be language agnostic (also works in languages other than English).

2

25 Answers 25

161

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!

7
  • 1
    Interestingly, Simon's approach has a lot in common with approaches such as q-grams and Dice's Coefficient. Mar 17, 2009 at 7:38
  • 1
    FWIW, your algorithm is 5 times faster (according to Benchmark.bmbm over 50,000 repetitions) than the one presented on en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice's_coefficient Oct 20, 2011 at 3:51
  • 1
    Just something to add that might help folks out - in marzagao's implementation (Java) on his site, and it looks like the ports as well, they're determining on matches of 2 character parts. I've found that you can tailor this to 3 or 4 character string parts for matches which will assume less typo's but also filter more junk in long search queries or with big search sets. Your mileage may vary, just thought I'd toss it out there.
    – Ross
    Apr 3, 2012 at 18:18
  • 6
    @JasonSundram is right -- in fact, this is the well-known Dice coefficient on character-level bigrams, as the author writes in the "addendum" (bottom of the page).
    – Fred Foo
    Sep 4, 2012 at 11:54
  • 5
    This returns a "score" of 1 (100% match) when comparing strings having a single isolated letter as difference, like this exemple: string_similarity("vitamin B", "vitamin C") #=> 1, is there an easy way to prevent this kind of behavior?
    – MrYoshiji
    Jul 30, 2013 at 20:21
80

marzagao's answer is great. I converted it to C# so I thought I'd post it here:

Pastebin Link

/// <summary>
/// This class implements string comparison algorithm
/// based on character pair similarity
/// Source: http://www.catalysoft.com/articles/StrikeAMatch.html
/// </summary>
public class SimilarityTool
{
    /// <summary>
    /// Compares the two strings based on letter pair matches
    /// </summary>
    /// <param name="str1"></param>
    /// <param name="str2"></param>
    /// <returns>The percentage match from 0.0 to 1.0 where 1.0 is 100%</returns>
    public double CompareStrings(string str1, string str2)
    {
        List<string> pairs1 = WordLetterPairs(str1.ToUpper());
        List<string> pairs2 = WordLetterPairs(str2.ToUpper());

        int intersection = 0;
        int union = pairs1.Count + pairs2.Count;

        for (int i = 0; i < pairs1.Count; i++)
        {
            for (int j = 0; j < pairs2.Count; j++)
            {
                if (pairs1[i] == pairs2[j])
                {
                    intersection++;
                    pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                    break;
                }
            }
        }

        return (2.0 * intersection) / union;
    }

    /// <summary>
    /// Gets all letter pairs for each
    /// individual word in the string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private List<string> WordLetterPairs(string str)
    {
        List<string> AllPairs = new List<string>();

        // Tokenize the string and put the tokens/words into an array
        string[] Words = Regex.Split(str, @"\s");

        // For each word
        for (int w = 0; w < Words.Length; w++)
        {
            if (!string.IsNullOrEmpty(Words[w]))
            {
                // Find the pairs of characters
                String[] PairsInWord = LetterPairs(Words[w]);

                for (int p = 0; p < PairsInWord.Length; p++)
                {
                    AllPairs.Add(PairsInWord[p]);
                }
            }
        }

        return AllPairs;
    }

    /// <summary>
    /// Generates an array containing every 
    /// two consecutive letters in the input string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private string[] LetterPairs(string str)
    {
        int numPairs = str.Length - 1;

        string[] pairs = new string[numPairs];

        for (int i = 0; i < numPairs; i++)
        {
            pairs[i] = str.Substring(i, 2);
        }

        return pairs;
    }
}
4
  • 1
    Very nice! The only suggestion I have, would to make this into an extension.
    – Levitikon
    Feb 7, 2012 at 17:12
  • +1! Great that it works, with slight modifications for Java too. And it does seem to return better responses than Levenshtein.
    – Xyene
    Sep 20, 2012 at 16:20
  • 1
    I added a version converting this to an extension method below. Thanks for the original version and the awesome translation. Aug 11, 2013 at 22:47
  • @Michael La Voie Thank you, it is very nice! Though a little problem with (2.0 * intersection) / union - I get Double.NaN when comparing two empty strings. Oct 2, 2014 at 8:38
45

Here is another version of marzagao's answer, this one written in Python:

def get_bigrams(string):
    """
    Take a string and return a list of bigrams.
    """
    s = string.lower()
    return [s[i:i+2] for i in list(range(len(s) - 1))]

def string_similarity(str1, str2):
    """
    Perform bigram comparison between two strings
    and return a percentage match in decimal form.
    """
    pairs1 = get_bigrams(str1)
    pairs2 = get_bigrams(str2)
    union  = len(pairs1) + len(pairs2)
    hit_count = 0
    for x in pairs1:
        for y in pairs2:
            if x == y:
                hit_count += 1
                break
    return (2.0 * hit_count) / union

if __name__ == "__main__":
    """
    Run a test using the example taken from:
    http://www.catalysoft.com/articles/StrikeAMatch.html
    """
    w1 = 'Healed'
    words = ['Heard', 'Healthy', 'Help', 'Herded', 'Sealed', 'Sold']

    for w2 in words:
        print('Healed --- ' + w2)
        print(string_similarity(w1, w2))
        print()
4
  • 2
    There's a small bug in string_similarity when there are duplicate ngrams in a word, resulting in a score >1 for identical strings. Adding a 'break' after "hit_count += 1" fixes it.
    – jbaiter
    May 25, 2013 at 19:30
  • 1
    @jbaiter: Good catch. I changed it to reflect your changes. May 29, 2013 at 2:04
  • 3
    In Simon White's article, he says "Note that whenever a match is found, that character pair is removed from the second array list to prevent us from matching against the same character pair multiple times. (Otherwise, 'GGGGG' would score a perfect match against 'GG'.)" I would alter this statement to say that it would give a higher than perfect match. Without taking this into account, it also seems to have the result that the algorithm is not transitive (similarity(x,y) =/= similarity(y,x)). Adding pairs2.remove(y) after the line hit_count += 1 fixes the problem. Jul 9, 2013 at 23:32
  • just a note, you HAVE to copy @NinjaMeTimbers' solution, which is fairly simple. If you use code above unaltered, string_similarity('GGGGG', GG'') would return 1.6, which is absurd.
    – Long Vuong
    Dec 16, 2020 at 1:26
21

A shorter version of John Rutledge's answer:

def get_bigrams(string):
    '''
    Takes a string and returns a list of bigrams
    '''
    s = string.lower()
    return {s[i:i+2] for i in xrange(len(s) - 1)}

def string_similarity(str1, str2):
    '''
    Perform bigram comparison between two strings
    and return a percentage match in decimal form
    '''
    pairs1 = get_bigrams(str1)
    pairs2 = get_bigrams(str2)
    return (2.0 * len(pairs1 & pairs2)) / (len(pairs1) + len(pairs2))
1
  • Even the intersection variable is a line waste. Sep 9, 2017 at 20:02
17

Here's my PHP implementation of suggested StrikeAMatch algorithm, by Simon White. the advantages (like it says in the link) are:

  • A true reflection of lexical similarity - strings with small differences should be recognised as being similar. In particular, a significant substring overlap should point to a high level of similarity between the strings.

  • A robustness to changes of word order - two strings which contain the same words, but in a different order, should be recognised as being similar. On the other hand, if one string is just a random anagram of the characters contained in the other, then it should (usually) be recognised as dissimilar.

  • Language Independence - the algorithm should work not only in English, but in many different languages.

<?php
/**
 * LetterPairSimilarity algorithm implementation in PHP
 * @author Igal Alkon
 * @link http://www.catalysoft.com/articles/StrikeAMatch.html
 */
class LetterPairSimilarity
{
    /**
     * @param $str
     * @return mixed
     */
    private function wordLetterPairs($str)
    {
        $allPairs = array();

        // Tokenize the string and put the tokens/words into an array

        $words = explode(' ', $str);

        // For each word
        for ($w = 0; $w < count($words); $w++)
        {
            // Find the pairs of characters
            $pairsInWord = $this->letterPairs($words[$w]);

            for ($p = 0; $p < count($pairsInWord); $p++)
            {
                $allPairs[] = $pairsInWord[$p];
            }
        }

        return $allPairs;
    }

    /**
     * @param $str
     * @return array
     */
    private function letterPairs($str)
    {
        $numPairs = mb_strlen($str)-1;
        $pairs = array();

        for ($i = 0; $i < $numPairs; $i++)
        {
            $pairs[$i] = mb_substr($str,$i,2);
        }

        return $pairs;
    }

    /**
     * @param $str1
     * @param $str2
     * @return float
     */
    public function compareStrings($str1, $str2)
    {
        $pairs1 = $this->wordLetterPairs(strtoupper($str1));
        $pairs2 = $this->wordLetterPairs(strtoupper($str2));

        $intersection = 0;

        $union = count($pairs1) + count($pairs2);

        for ($i=0; $i < count($pairs1); $i++)
        {
            $pair1 = $pairs1[$i];

            $pairs2 = array_values($pairs2);
            for($j = 0; $j < count($pairs2); $j++)
            {
                $pair2 = $pairs2[$j];
                if ($pair1 === $pair2)
                {
                    $intersection++;
                    unset($pairs2[$j]);
                    break;
                }
            }
        }

        return (2.0*$intersection)/$union;
    }
}
0
14

This discussion has been really helpful, thanks. I converted the algorithm to VBA for use with Excel and wrote a few versions of a worksheet function, one for simple comparison of a pair of strings, the other for comparing one string to a range/array of strings. The strSimLookup version returns either the last best match as a string, array index, or similarity metric.

This implementation produces the same results listed in the Amazon example on Simon White's website with a few minor exceptions on low-scoring matches; not sure where the difference creeps in, could be VBA's Split function, but I haven't investigated as it's working fine for my purposes.

'Implements functions to rate how similar two strings are on
'a scale of 0.0 (completely dissimilar) to 1.0 (exactly similar)
'Source:   http://www.catalysoft.com/articles/StrikeAMatch.html
'Author: Bob Chatham, bob.chatham at gmail.com
'9/12/2010

Option Explicit

Public Function stringSimilarity(str1 As String, str2 As String) As Variant
'Simple version of the algorithm that computes the similiarity metric
'between two strings.
'NOTE: This verision is not efficient to use if you're comparing one string
'with a range of other values as it will needlessly calculate the pairs for the
'first string over an over again; use the array-optimized version for this case.

    Dim sPairs1 As Collection
    Dim sPairs2 As Collection

    Set sPairs1 = New Collection
    Set sPairs2 = New Collection

    WordLetterPairs str1, sPairs1
    WordLetterPairs str2, sPairs2

    stringSimilarity = SimilarityMetric(sPairs1, sPairs2)

    Set sPairs1 = Nothing
    Set sPairs2 = Nothing

End Function

Public Function strSimA(str1 As Variant, rRng As Range) As Variant
'Return an array of string similarity indexes for str1 vs every string in input range rRng
    Dim sPairs1 As Collection
    Dim sPairs2 As Collection
    Dim arrOut As Variant
    Dim l As Long, j As Long

    Set sPairs1 = New Collection

    WordLetterPairs CStr(str1), sPairs1

    l = rRng.Count
    ReDim arrOut(1 To l)
    For j = 1 To l
        Set sPairs2 = New Collection
        WordLetterPairs CStr(rRng(j)), sPairs2
        arrOut(j) = SimilarityMetric(sPairs1, sPairs2)
        Set sPairs2 = Nothing
    Next j

    strSimA = Application.Transpose(arrOut)

End Function

Public Function strSimLookup(str1 As Variant, rRng As Range, Optional returnType) As Variant
'Return either the best match or the index of the best match
'depending on returnTYype parameter) between str1 and strings in rRng)
' returnType = 0 or omitted: returns the best matching string
' returnType = 1           : returns the index of the best matching string
' returnType = 2           : returns the similarity metric

    Dim sPairs1 As Collection
    Dim sPairs2 As Collection
    Dim metric, bestMetric As Double
    Dim i, iBest As Long
    Const RETURN_STRING As Integer = 0
    Const RETURN_INDEX As Integer = 1
    Const RETURN_METRIC As Integer = 2

    If IsMissing(returnType) Then returnType = RETURN_STRING

    Set sPairs1 = New Collection

    WordLetterPairs CStr(str1), sPairs1

    bestMetric = -1
    iBest = -1

    For i = 1 To rRng.Count
        Set sPairs2 = New Collection
        WordLetterPairs CStr(rRng(i)), sPairs2
        metric = SimilarityMetric(sPairs1, sPairs2)
        If metric > bestMetric Then
            bestMetric = metric
            iBest = i
        End If
        Set sPairs2 = Nothing
    Next i

    If iBest = -1 Then
        strSimLookup = CVErr(xlErrValue)
        Exit Function
    End If

    Select Case returnType
    Case RETURN_STRING
        strSimLookup = CStr(rRng(iBest))
    Case RETURN_INDEX
        strSimLookup = iBest
    Case Else
        strSimLookup = bestMetric
    End Select

End Function

Public Function strSim(str1 As String, str2 As String) As Variant
    Dim ilen, iLen1, ilen2 As Integer

    iLen1 = Len(str1)
    ilen2 = Len(str2)

    If iLen1 >= ilen2 Then ilen = ilen2 Else ilen = iLen1

    strSim = stringSimilarity(Left(str1, ilen), Left(str2, ilen))

End Function

Sub WordLetterPairs(str As String, pairColl As Collection)
'Tokenize str into words, then add all letter pairs to pairColl

    Dim Words() As String
    Dim word, nPairs, pair As Integer

    Words = Split(str)

    If UBound(Words) < 0 Then
        Set pairColl = Nothing
        Exit Sub
    End If

    For word = 0 To UBound(Words)
        nPairs = Len(Words(word)) - 1
        If nPairs > 0 Then
            For pair = 1 To nPairs
                pairColl.Add Mid(Words(word), pair, 2)
            Next pair
        End If
    Next word

End Sub

Private Function SimilarityMetric(sPairs1 As Collection, sPairs2 As Collection) As Variant
'Helper function to calculate similarity metric given two collections of letter pairs.
'This function is designed to allow the pair collections to be set up separately as needed.
'NOTE: sPairs2 collection will be altered as pairs are removed; copy the collection
'if this is not the desired behavior.
'Also assumes that collections will be deallocated somewhere else

    Dim Intersect As Double
    Dim Union As Double
    Dim i, j As Long

    If sPairs1.Count = 0 Or sPairs2.Count = 0 Then
        SimilarityMetric = CVErr(xlErrNA)
        Exit Function
    End If

    Union = sPairs1.Count + sPairs2.Count
    Intersect = 0

    For i = 1 To sPairs1.Count
        For j = 1 To sPairs2.Count
            If StrComp(sPairs1(i), sPairs2(j)) = 0 Then
                Intersect = Intersect + 1
                sPairs2.Remove j
                Exit For
            End If
        Next j
    Next i

    SimilarityMetric = (2 * Intersect) / Union

End Function
1
12

I'm sorry, the answer was not invented by the author. This is a well known algorithm that was first present by Digital Equipment Corporation and is often referred to as shingling.

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1997-015.pdf

10

I translated Simon White's algorithm to PL/pgSQL. This is my contribution.

<!-- language: lang-sql -->

create or replace function spt1.letterpairs(in p_str varchar) 
returns varchar  as 
$$
declare

    v_numpairs integer := length(p_str)-1;
    v_pairs varchar[];

begin

    for i in 1 .. v_numpairs loop
        v_pairs[i] := substr(p_str, i, 2);
    end loop;

    return v_pairs;

end;
$$ language 'plpgsql';

--===================================================================

create or replace function spt1.wordletterpairs(in p_str varchar) 
returns varchar as
$$
declare
    v_allpairs varchar[];
    v_words varchar[];
    v_pairsinword varchar[];
begin
    v_words := regexp_split_to_array(p_str, '[[:space:]]');

    for i in 1 .. array_length(v_words, 1) loop
        v_pairsinword := spt1.letterpairs(v_words[i]);

        if v_pairsinword is not null then
            for j in 1 .. array_length(v_pairsinword, 1) loop
                v_allpairs := v_allpairs || v_pairsinword[j];
            end loop;
        end if;

    end loop;


    return v_allpairs;
end;
$$ language 'plpgsql';

--===================================================================

create or replace function spt1.arrayintersect(ANYARRAY, ANYARRAY)
returns anyarray as 
$$
    select array(select unnest($1) intersect select unnest($2))
$$ language 'sql';

--===================================================================

create or replace function spt1.comparestrings(in p_str1 varchar, in p_str2 varchar)
returns float as
$$
declare
    v_pairs1 varchar[];
    v_pairs2 varchar[];
    v_intersection integer;
    v_union integer;
begin
    v_pairs1 := wordletterpairs(upper(p_str1));
    v_pairs2 := wordletterpairs(upper(p_str2));
    v_union := array_length(v_pairs1, 1) + array_length(v_pairs2, 1); 

    v_intersection := array_length(arrayintersect(v_pairs1, v_pairs2), 1);

    return (2.0 * v_intersection / v_union);
end;
$$ language 'plpgsql'; 
2
  • Works on my PostgreSQL that has no plruby support! Thank you!
    – hostnik
    Feb 6, 2013 at 8:03
  • This port is incorrect. Exact string do not return 1. Jul 17, 2017 at 21:34
10

A version in beautiful Scala:

  def pairDistance(s1: String, s2: String): Double = {

    def strToPairs(s: String, acc: List[String]): List[String] = {
      if (s.size < 2) acc
      else strToPairs(s.drop(1),
        if (s.take(2).contains(" ")) acc else acc ::: List(s.take(2)))
    }

    val lst1 = strToPairs(s1.toUpperCase, List())
    val lst2 = strToPairs(s2.toUpperCase, List())

    (2.0 * lst2.intersect(lst1).size) / (lst1.size + lst2.size)

  }
9

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.

9

A faster PHP version of the algorithm:

/**
 *
 * @param $str
 * @return mixed
 */
private static function wordLetterPairs ($str)
{
    $allPairs = array();

    // Tokenize the string and put the tokens/words into an array

    $words = explode(' ', $str);

    // For each word
    for ($w = 0; $w < count($words); $w ++) {
        // Find the pairs of characters
        $pairsInWord = self::letterPairs($words[$w]);

        for ($p = 0; $p < count($pairsInWord); $p ++) {
            $allPairs[$pairsInWord[$p]] = $pairsInWord[$p];
        }
    }

    return array_values($allPairs);
}

/**
 *
 * @param $str
 * @return array
 */
private static function letterPairs ($str)
{
    $numPairs = mb_strlen($str) - 1;
    $pairs = array();

    for ($i = 0; $i < $numPairs; $i ++) {
        $pairs[$i] = mb_substr($str, $i, 2);
    }

    return $pairs;
}

/**
 *
 * @param $str1
 * @param $str2
 * @return float
 */
public static function compareStrings ($str1, $str2)
{
    $pairs1 = self::wordLetterPairs(mb_strtolower($str1));
    $pairs2 = self::wordLetterPairs(mb_strtolower($str2));


    $union = count($pairs1) + count($pairs2);

    $intersection = count(array_intersect($pairs1, $pairs2));

    return (2.0 * $intersection) / $union;
}

For the data I had (approx 2300 comparisons) I had a running time of 0.58sec with Igal Alkon solution versus 0.35sec with mine.

7

Posting marzagao's answer in C99, inspired by these algorithms

double dice_match(const char *string1, const char *string2) {

    //check fast cases
    if (((string1 != NULL) && (string1[0] == '\0')) || 
        ((string2 != NULL) && (string2[0] == '\0'))) {
        return 0;
    }
    if (string1 == string2) {
        return 1;
    }

    size_t strlen1 = strlen(string1);
    size_t strlen2 = strlen(string2);
    if (strlen1 < 2 || strlen2 < 2) {
        return 0;
    }

    size_t length1 = strlen1 - 1;
    size_t length2 = strlen2 - 1;

    double matches = 0;
    int i = 0, j = 0;

    //get bigrams and compare
    while (i < length1 && j < length2) {
        char a[3] = {string1[i], string1[i + 1], '\0'};
        char b[3] = {string2[j], string2[j + 1], '\0'};
        int cmp = strcmpi(a, b);
        if (cmp == 0) {
            matches += 2;
        }
        i++;
        j++;
    }

    return matches / (length1 + length2);
}

Some tests based on the original article:

#include <stdio.h>

void article_test1() {
    char *string1 = "FRANCE";
    char *string2 = "FRENCH";
    printf("====%s====\n", __func__);
    printf("%2.f%% == 40%%\n", dice_match(string1, string2) * 100);
}


void article_test2() {
    printf("====%s====\n", __func__);
    char *string = "Healed";
    char *ss[] = {"Heard", "Healthy", "Help",
                  "Herded", "Sealed", "Sold"};
    int correct[] = {44, 55, 25, 40, 80, 0};
    for (int i = 0; i < 6; ++i) {
        printf("%2.f%% == %d%%\n", dice_match(string, ss[i]) * 100, correct[i]);
    }
}

void multicase_test() {
    char *string1 = "FRaNcE";
    char *string2 = "fREnCh";
    printf("====%s====\n", __func__);
    printf("%2.f%% == 40%%\n", dice_match(string1, string2) * 100);

}

void gg_test() {
    char *string1 = "GG";
    char *string2 = "GGGGG";
    printf("====%s====\n", __func__);
    printf("%2.f%% != 100%%\n", dice_match(string1, string2) * 100);
}


int main() {
    article_test1();
    article_test2();
    multicase_test();
    gg_test();

    return 0;
}
2
  • 1
    I don't think this is an accurate implementation of the original article
    – MatG
    Sep 27, 2022 at 14:28
  • This is comparing only consecutive pairs and even then it’s full of errors
    – Lothar
    May 17, 2023 at 9:28
6

Here is the R version:

get_bigrams <- function(str)
{
  lstr = tolower(str)
  bigramlst = list()
  for(i in 1:(nchar(str)-1))
  {
    bigramlst[[i]] = substr(str, i, i+1)
  }
  return(bigramlst)
}

str_similarity <- function(str1, str2)
{
   pairs1 = get_bigrams(str1)
   pairs2 = get_bigrams(str2)
   unionlen  = length(pairs1) + length(pairs2)
   hit_count = 0
   for(x in 1:length(pairs1)){
        for(y in 1:length(pairs2)){
            if (pairs1[[x]] == pairs2[[y]])
                hit_count = hit_count + 1
        }
   }
   return ((2.0 * hit_count) / unionlen)
}
1
  • This algorithm is better but quite slow for large data. I mean if one has to compare 10000 words with 15000 other words, its too slow. Can we increase its performrmance in terms of speed?? Dec 18, 2014 at 12:29
5

Building on Michael La Voie's awesome C# version, as per the request to make it an extension method, here is what I came up with. The primary benefit of doing it this way is that you can sort a Generic List by the percent match. For example, consider you have a string field named "City" in your object. A user searches for "Chester" and you want to return results in descending order of match. For example, you want literal matches of Chester to show up before Rochester. To do this, add two new properties to your object:

    public string SearchText { get; set; }
    public double PercentMatch
    {
        get
        {
            return City.ToUpper().PercentMatchTo(this.SearchText.ToUpper());
        }
    }

Then on each object, set the SearchText to what the user searched for. Then you can sort it easily with something like:

    zipcodes = zipcodes.OrderByDescending(x => x.PercentMatch);

Here's the slight modification to make it an extension method:

    /// <summary>
    /// This class implements string comparison algorithm
    /// based on character pair similarity
    /// Source: http://www.catalysoft.com/articles/StrikeAMatch.html
    /// </summary>
    public static double PercentMatchTo(this string str1, string str2)
    {
        List<string> pairs1 = WordLetterPairs(str1.ToUpper());
        List<string> pairs2 = WordLetterPairs(str2.ToUpper());

        int intersection = 0;
        int union = pairs1.Count + pairs2.Count;

        for (int i = 0; i < pairs1.Count; i++)
        {
            for (int j = 0; j < pairs2.Count; j++)
            {
                if (pairs1[i] == pairs2[j])
                {
                    intersection++;
                    pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                    break;
                }
            }
        }

        return (2.0 * intersection) / union;
    }

    /// <summary>
    /// Gets all letter pairs for each
    /// individual word in the string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private static List<string> WordLetterPairs(string str)
    {
        List<string> AllPairs = new List<string>();

        // Tokenize the string and put the tokens/words into an array
        string[] Words = Regex.Split(str, @"\s");

        // For each word
        for (int w = 0; w < Words.Length; w++)
        {
            if (!string.IsNullOrEmpty(Words[w]))
            {
                // Find the pairs of characters
                String[] PairsInWord = LetterPairs(Words[w]);

                for (int p = 0; p < PairsInWord.Length; p++)
                {
                    AllPairs.Add(PairsInWord[p]);
                }
            }
        }

        return AllPairs;
    }

    /// <summary>
    /// Generates an array containing every 
    /// two consecutive letters in the input string
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    private static  string[] LetterPairs(string str)
    {
        int numPairs = str.Length - 1;

        string[] pairs = new string[numPairs];

        for (int i = 0; i < numPairs; i++)
        {
            pairs[i] = str.Substring(i, 2);
        }

        return pairs;
    }
1
  • I think you would be better off using a bool isCaseSensitive with a default value of false - even if it's true the implementation is much cleaner
    – Jordan
    Apr 30, 2014 at 20:27
5

My JavaScript implementation takes a string or array of strings, and an optional floor (the default floor is 0.5). If you pass it a string, it will return true or false depending on whether or not the string's similarity score is greater than or equal to the floor. If you pass it an array of strings, it will return an array of those strings whose similarity score is greater than or equal to the floor, sorted by score.

Examples:

'Healed'.fuzzy('Sealed');      // returns true
'Healed'.fuzzy('Help');        // returns false
'Healed'.fuzzy('Help', 0.25);  // returns true

'Healed'.fuzzy(['Sold', 'Herded', 'Heard', 'Help', 'Sealed', 'Healthy']);
// returns ["Sealed", "Healthy"]

'Healed'.fuzzy(['Sold', 'Herded', 'Heard', 'Help', 'Sealed', 'Healthy'], 0);
// returns ["Sealed", "Healthy", "Heard", "Herded", "Help", "Sold"]

Here it is:

(function(){
  var default_floor = 0.5;

  function pairs(str){
    var pairs = []
      , length = str.length - 1
      , pair;
    str = str.toLowerCase();
    for(var i = 0; i < length; i++){
      pair = str.substr(i, 2);
      if(!/\s/.test(pair)){
        pairs.push(pair);
      }
    }
    return pairs;
  }

  function similarity(pairs1, pairs2){
    var union = pairs1.length + pairs2.length
      , hits = 0;

    for(var i = 0; i < pairs1.length; i++){
      for(var j = 0; j < pairs2.length; j++){
        if(pairs1[i] == pairs2[j]){
          pairs2.splice(j--, 1);
          hits++;
          break;
        }
      }
    }
    return 2*hits/union || 0;
  }

  String.prototype.fuzzy = function(strings, floor){
    var str1 = this
      , pairs1 = pairs(this);

    floor = typeof floor == 'number' ? floor : default_floor;

    if(typeof(strings) == 'string'){
      return str1.length > 1 && strings.length > 1 && similarity(pairs1, pairs(strings)) >= floor || str1.toLowerCase() == strings.toLowerCase();
    }else if(strings instanceof Array){
      var scores = {};

      strings.map(function(str2){
        scores[str2] = str1.length > 1 ? similarity(pairs1, pairs(str2)) : 1*(str1.toLowerCase() == str2.toLowerCase());
      });

      return strings.filter(function(str){
        return scores[str] >= floor;
      }).sort(function(a, b){
        return scores[b] - scores[a];
      });
    }
  };
})();
1
  • 1
    Bug/Typo! for(var j = 0; j < pairs1.length; j++){ should be for(var j = 0; j < pairs2.length; j++){
    – Searle
    Apr 13, 2018 at 21:37
4

The Dice coefficient algorithm (Simon White / marzagao's answer) is implemented in Ruby in the pair_distance_similar method in the amatch gem

https://github.com/flori/amatch

This gem also contains implementations of a number of approximate matching and string comparison algorithms: Levenshtein edit distance, Sellers edit distance, the Hamming distance, the longest common subsequence length, the longest common substring length, the pair distance metric, the Jaro-Winkler metric.

2

A Haskell version—feel free to suggest edits because I haven't done much Haskell.

import Data.Char
import Data.List

-- Convert a string into words, then get the pairs of words from that phrase
wordLetterPairs :: String -> [String]
wordLetterPairs s1 = concat $ map pairs $ words s1

-- Converts a String into a list of letter pairs.
pairs :: String -> [String]
pairs [] = []
pairs (x:[]) = []
pairs (x:ys) = [x, head ys]:(pairs ys)

-- Calculates the match rating for two strings
matchRating :: String -> String -> Double
matchRating s1 s2 = (numberOfMatches * 2) / totalLength
  where pairsS1 = wordLetterPairs $ map toLower s1
        pairsS2 = wordLetterPairs $ map toLower s2
        numberOfMatches = fromIntegral $ length $ pairsS1 `intersect` pairsS2
        totalLength = fromIntegral $ length pairsS1 + length pairsS2
2

Clojure:

(require '[clojure.set :refer [intersection]])

(defn bigrams [s]
  (->> (split s #"\s+")
       (mapcat #(partition 2 1 %))
       (set)))

(defn string-similarity [a b]
  (let [a-pairs (bigrams a)
        b-pairs (bigrams b)
        total-count (+ (count a-pairs) (count b-pairs))
        match-count (count (intersection a-pairs b-pairs))
        similarity (/ (* 2 match-count) total-count)]
    similarity))
2

Here is another version of Similarity based in Sørensen–Dice index (marzagao's answer), this one written in C++11:

/*
 * Similarity based in Sørensen–Dice index.
 *
 * Returns the Similarity between _str1 and _str2.
 */
double similarity_sorensen_dice(const std::string& _str1, const std::string& _str2) {
    // Base case: if some string is empty.
    if (_str1.empty() || _str2.empty()) {
        return 1.0;
    }

    auto str1 = upper_string(_str1);
    auto str2 = upper_string(_str2);

    // Base case: if the strings are equals.
    if (str1 == str2) {
        return 0.0;
    }

    // Base case: if some string does not have bigrams.
    if (str1.size() < 2 || str2.size() < 2) {
        return 1.0;
    }

    // Extract bigrams from str1
    auto num_pairs1 = str1.size() - 1;
    std::unordered_set<std::string> str1_bigrams;
    str1_bigrams.reserve(num_pairs1);
    for (unsigned i = 0; i < num_pairs1; ++i) {
        str1_bigrams.insert(str1.substr(i, 2));
    }

    // Extract bigrams from str2
    auto num_pairs2 = str2.size() - 1;
    std::unordered_set<std::string> str2_bigrams;
    str2_bigrams.reserve(num_pairs2);
    for (unsigned int i = 0; i < num_pairs2; ++i) {
        str2_bigrams.insert(str2.substr(i, 2));
    }

    // Find the intersection between the two sets.
    int intersection = 0;
    if (str1_bigrams.size() < str2_bigrams.size()) {
        const auto it_e = str2_bigrams.end();
        for (const auto& bigram : str1_bigrams) {
            intersection += str2_bigrams.find(bigram) != it_e;
        }
    } else {
        const auto it_e = str1_bigrams.end();
        for (const auto& bigram : str2_bigrams) {
            intersection += str1_bigrams.find(bigram) != it_e;
        }
    }

    // Returns similarity coefficient.
    return (2.0 * intersection) / (num_pairs1 + num_pairs2);
}
2
  • 1
    Ehm, I wonder your upper_string could be a function similar to: std::string to_upper(std::string s) { for(char& c : s) c=static_cast<char>(std::toupper(c)); return s; }
    – MatG
    Sep 27, 2022 at 14:13
  • Nice. Now I would love to turn this into a hi speed function with simd and preprocessed str1. Could make it 100 times faster
    – Lothar
    May 17, 2023 at 9:33
2

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:

intersection

  • Result:

algorithm

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.

1

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.

2
  • However, to quote another post on this topic, what it returns is often "erratic". It ranks 'echo' as quite similar to 'dog'.
    – Xyene
    Sep 20, 2012 at 16:28
  • @Nox: The "divided by the length of the first string" portion of this reply is significant. Also, this performs better than the much-lauded Dice's algorithm for typos and transposition errors, and even common conjugations (consider comparing "swim" and "swam", for example). Jul 19, 2013 at 0:17
1

Hey guys i gave this a try in javascript, but I'm new to it, anyone know faster ways to do it?

function get_bigrams(string) {
    // Takes a string and returns a list of bigrams
    var s = string.toLowerCase();
    var v = new Array(s.length-1);
    for (i = 0; i< v.length; i++){
        v[i] =s.slice(i,i+2);
    }
    return v;
}

function string_similarity(str1, str2){
    /*
    Perform bigram comparison between two strings
    and return a percentage match in decimal form
    */
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hit_count = 0;
    for (x in pairs1){
        for (y in pairs2){
            if (pairs1[x] == pairs2[y]){
                hit_count++;
            }
        }
    }
    return ((2.0 * hit_count) / union);
}


var w1 = 'Healed';
var word =['Heard','Healthy','Help','Herded','Sealed','Sold']
for (w2 in word){
    console.log('Healed --- ' + word[w2])
    console.log(string_similarity(w1,word[w2]));
}
1
  • This implementation is incorrect. The bigram function breaks for input of length 0. The string_similarity method does not properly break inside the second loop, which may lead to counting pairs multiple times, leading to a return value which exceeds 100%. And you've also forgotten to declare x and y, and you should not loop through loops using a for..in.. loop (use for(..;..;..) instead).
    – Rob W
    Feb 23, 2013 at 21:17
1

I was looking for pure ruby implementation of the algorithm indicated by @marzagao's answer. Unfortunately, link indicated by @marzagao is broken. In @s01ipsist answer, he indicated ruby gem amatch where implementation is not in pure ruby. So I searchd a little and found gem fuzzy_match which has pure ruby implementation (though this gem use amatch) at here. I hope this will help someone like me.

0
**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;
  }
}
0

Here's another c++ implementation that follows the original article, that minimizes dynamic memory allocations.

It obtains the same matching values in the examples, but I think it's better to take into account also the single character words.

//---------------------------------------------------------------------------
// Similarity based on Sørensen–Dice index
double calc_similarity( const std::string_view s1, const std::string_view s2 )
{
    // Check banal cases
    if( s1.empty() || s2.empty() )
       {// Empty string is never similar to another
        return 0.0;
       }
    else if( s1==s2 )
       {// Perfectly equal
        return 1.0;
       }
    else if( s1.length()==1 || s2.length()==1 )
       {// Single (not equal) characters have zero similarity
        return 0.0;
       }

    /////////////////////////////////////////////////////////////////////////
    // Represents a pair of adjacent characters
    class charpair_t final
    {
     public:
         charpair_t(const char a, const char b) noexcept : c1(a), c2(b) {}
         [[nodiscard]] bool operator==(const charpair_t& other) const noexcept { return c1==other.c1 && c2==other.c2; }
     private:
        char c1, c2;
    };

    /////////////////////////////////////////////////////////////////////////
    // Collects and access a sequence of adjacent characters (skipping spaces)
    class charpairs_t final
    {
     public:
         charpairs_t(const std::string_view s)
            {
             assert( !s.empty() );
             const std::size_t i_last = s.size()-1;
             std::size_t i = 0;
             chpairs.reserve(i_last);
             while( i<i_last )
               {
                // Accepting also single-character words (the second is a space)
                //if( !std::isspace(s[i]) ) chpairs.emplace_back( std::tolower(s[i]), std::tolower(s[i+1]) );
                // Skipping single-character words (as in the original article)
                if( std::isspace(s[i]) ) ; // Skip
                else if( std::isspace(s[i+1]) ) ++i; // Skip also next
                else chpairs.emplace_back( std::tolower(s[i]), std::tolower(s[i+1]) );
                ++i;
               }
            }

         [[nodiscard]] auto size() const noexcept { return chpairs.size(); }
         [[nodiscard]] auto cbegin() const noexcept { return chpairs.cbegin(); }
         [[nodiscard]] auto cend() const noexcept { return chpairs.cend(); }
         auto erase(std::vector<charpair_t>::const_iterator i) { return chpairs.erase(i); }

     private:
        std::vector<charpair_t> chpairs;
    };

    charpairs_t chpairs1{s1},
                chpairs2{s2};
    const double orig_avg_bigrams_count = 0.5 * static_cast<double>(chpairs1.size() + chpairs2.size());
    std::size_t matching_bigrams_count = 0;
    for( auto ib1=chpairs1.cbegin(); ib1!=chpairs1.cend(); ++ib1 )
       {
        for( auto ib2=chpairs2.cbegin(); ib2!=chpairs2.cend(); )
           {
            if( *ib1==*ib2 )
               {
                ++matching_bigrams_count;
                ib2 = chpairs2.erase(ib2); // Avoid to match the same character pair multiple times
                break;
               }
            else ++ib2;
           }
       }
    return static_cast<double>(matching_bigrams_count) / orig_avg_bigrams_count;
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.