String Similarity .NET

Shingle-based algorithms convert strings into sets or profiles of n-grams. There are two ways to use them:

1. Directly compute distance: Use the Distance method on the algorithm object (e.g., QGram).
2. Pre-compute profiles for large datasets: Use GetProfile(string) to create a profile, then use Similarity(profile1, profile2) to compare them.

Important: When using profiles, you must use the same algorithm instance (e.g., the same Cosine object) to parse all input strings to ensure consistency.

// Direct distance calculation
var dig = new QGram(2);
Console.WriteLine(dig.Distance("ABCD", "ABCE"));

// Profile-based similarity for large datasets
var cosine = new Cosine(2);
var profile1 = cosine.GetProfile("My first string");
var profile2 = cosine.GetProfile("My other string...");
Console.WriteLine(cosine.Similarity(profile1, profile2));

To use the String Similarity .NET library in your project, install the NuGet package using the following command:

Install-Package F23.StringSimilarity

The RatcliffObershelp class implements Gestalt Pattern Matching. It returns a similarity value in the interval [0.0, 1.0]. The distance is computed as 1 - Ratcliff/Obershelp similarity.

using System;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        var ro = new RatcliffObershelp();
        
        // substitution of s and t
        Console.WriteLine(ro.Similarity("My string", "My tsring"));
        
        // substitution of s and n
        Console.WriteLine(ro.Similarity("My string", "My ntrisg"));
    }
}

The Levenshtein algorithm calculates the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another. It is a metric distance and uses dynamic programming with $O(m \cdot n)$ complexity.

using System;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        var l = new Levenshtein();

        Console.WriteLine(l.Distance("My string", "My $tring"));
    }
}

The Sift4 class is an experimental algorithm inspired by JaroWinkler and LCS. It aims to match human perception of string distance by considering substitution, character distance, and LCS. It includes a MaxOffset property to configure its behavior.

using System;
using System.Diagnostics;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        var s1 = "This is the first string";
        var s2 = "And this is another string";
        var sift4 = new Sift4();
        sift4.MaxOffset = 5;
        double result = sift4.Distance(s1, s2);
        Debug.Assert(Math.Abs(result - 11.0) < 0.1);
    }
}

The MetricLCS class provides a distance metric based on the Longest Common Subsequence. The distance is computed as 1 - |LCS(s1, s2)| / max(|s1|, |s2|).

using System;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        var lcs = new MetricLCS();

        string s1 = "ABCDEFG";   
        string s2 = "ABCDEFHJKL";
        // LCS: ABCDEF => length = 6
        // longest = s2 => length = 10
        // => 1 - 6/10 = 0.4
        Console.WriteLine(lcs.Distance(s1, s2));

        Console.WriteLine(lcs.Distance("ABDEF", "ABDIF"));
    }
}

The NGram class implements normalized N-Gram distance. It uses affixing with the special character \n to increase the weight of the first characters. The normalization is achieved by dividing the total similarity score by the original length of the longest word. You must provide the n value (the size of the n-gram) in the constructor.

using System;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        // produces 0.583333
        var twogram = new NGram(2);
        Console.WriteLine(twogram.Distance("ABCD", "ABTUIO"));
        
        // produces 0.97222
        string s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp";
        string s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x";
        var ngram = new NGram(4);
        Console.WriteLine(ngram.Distance(s1, s2));
    }
}

The LongestCommonSubsequence class finds the longest subsequence common to two sequences. Unlike substrings, subsequences do not need to be consecutive. The distance is calculated as n + m - 2 |LCS(X, Y)|, where n and m are the lengths of the strings. This implementation uses a dynamic programming approach with $O(m imes n)$ time and space complexity.

using System;
using F23.StringSimilarity;

public class Program
{
    public static void Main(string[] args)
    {
        var lcs = new LongestCommonSubsequence();

        // Will produce 4.0
        Console.WriteLine(lcs.Distance("AGCAT", "GAC"));
        
        // Will produce 1.0
        Console.WriteLine(lcs.Distance("AGCAT", "AGCT"));
    }
}