String Similarity .NET

A .NET port of java-string-similarity: https://github.com/tdebatty/java-string-similarity

---

What if your day job was contributing to open-source projects and custom AI solutions — and you got paid for it?<br /> We're hiring remote engineers to contribute to cutting-edge AI and custom software projects. 100% remote, 100% real impact. https://www.feature23.com/careers

Overview

A library implementing different string similarity and distance measures. A dozen of algorithms (including Levenshtein edit distance and sibblings, Jaro-Winkler, Longest Common Subsequence, cosine similarity etc.) are currently implemented. Check the summary table below for the complete list...

• Download
• Overview
• Normalized, metric, similarity and distance
• Shingles (n-gram) based similarity and distance
• Levenshtein
• Normalized Levenshtein
• Weighted Levenshtein
• Damerau-Levenshtein
• Jaro-Winkler
• Longest Common Subsequence
• Metric Longest Common Subsequence
• N-Gram
• Shingle (n-gram) based algorithms
  • Q-Gram
  • Cosine similarity
  • Jaccard index
  • Sorensen-Dice coefficient
• Ratcliff-Obershelp
• Experimental
  • SIFT4
• License

Download

Using NuGet:

Install-Package F23.StringSimilarity

Overview

The main characteristics of each implemented algorithm are presented below. The "cost" column gives an estimation of the computational cost to compute the similarity between two strings of length m and n respectively.

| | | Normalized? | Metric? | Type | Cost | |-------- |------- |------------- |---------- | ------ | ---- | | Levenshtein |distance | No | Yes | | O(mn) ¹ | | Normalized Levenshtein |distance<br>similarity | Yes | No | | O(mn) ¹ | | Weighted Levenshtein |distance | No | No | | O(mn) ¹ | | Damerau-Levenshtein ³ |distance | No | Yes | | O(mn) ¹ | | Optimal String Alignment ³ |not implemented yet | No | No | | O(mn) ¹ | | Jaro-Winkler |similarity<br>distance | Yes | No | | O(mn) | | Longest Common Subsequence |distance | No | No | | O(mn) ^1,2 | | Metric Longest Common Subsequence |distance | Yes | Yes | | O(mn) ^1,2 | | N-Gram |distance | Yes | No | | O(m*n) | | Q-Gram |distance | No | No | Profile | O(m+n) | | Cosine similarity |similarity<br>distance | Yes | No | Profile | O(m+n) | | Jaccard index |similarity<br>distance | Yes | Yes | Set | O(m+n) | | Sorensen-Dice coefficient |similarity<br>distance | Yes | No | Set | O(m+n) | | Ratcliff-Obershelp |similarity<br>distance | Yes | No | | ? | |

[1] In this library, Levenshtein edit distance, LCS distance and their sibblings are computed using the dynamic programming method, which has a cost O(m.n). For Levenshtein distance, the algorithm is sometimes called Wagner-Fischer algorithm ("The string-to-string correction problem", 1974). The original algorithm uses a matrix of size m x n to store the Levenshtein distance between string prefixes.

If the alphabet is finite, it is possible to use the method of four russians (Arlazarov et al. "On economic construction of the transitive closure of a directed graph", 1970) to speedup computation. This was published by Masek in 1980 ("A Faster Algorithm Computing String Edit Distances"). This method splits the matrix in blocks of size t x t. Each possible block is precomputed to produce a lookup table. This lookup table can then be used to compute the string similarity (or distance) in O(nm/t). Usually, t is choosen as log(m) if m > n. The resulting computation cost is thus O(mn/log(m)). This method has not been implemented (yet).

[2] In "Length of Maximal Common Subsequences", K.S. Larsen proposed an algorithm that computes the length of LCS in time O(log(m).log(n)). But the algorithm has a memory requirement O(m.n²) and was thus not implemented here.

[3] There are two variants of Damerau-Levenshtein string distance: Damerau-Levenshtein with adjacent transpositions (also sometimes called unrestricted Damerau–Levenshtein distance) and Optimal String Alignment (also sometimes called restricted edit distance). For Optimal String Alignment, no substring can be edited more than once.

Normalized, metric, similarity and distance

Although the topic might seem simple, a lot of different algorithms exist to measure text similarity or distance. Therefore the library defines some interfaces to categorize them.

(Normalized) similarity and distance

• StringSimilarity : Implementing algorithms define a similarity between strings (0 means strings are completely different).
• NormalizedStringSimilarity : Implementing algorithms define a similarity between 0.0 and 1.0, like Jaro-Winkler for example.
• StringDistance : Implementing algorithms define a distance between strings (0 means strings are identical), like Levenshtein for example. The maximum distance value depends on the algorithm.
• NormalizedStringDistance : This interface extends StringDistance. For implementing classes, the computed distance value is between 0.0 and 1.0. NormalizedLevenshtein is an example of NormalizedStringDistance.

Generally, algorithms that implement NormalizedStringSimilarity also implement NormalizedStringDistance, and similarity = 1 - distance. But there are a few exceptions, like N-Gram similarity and distance (Kondrak)...

Metric distances

The MetricStringDistance interface : A few of the distances are actually metric distances, which means that verify the triangle inequality d(x, y) <= d(x,z) + d(z,y). For example, Levenshtein is a metric distance, but NormalizedLevenshtein is not.

A lot of nearest-neighbor search algorithms and indexing structures rely on the triangle inequality. You can check "Similarity Search, The Metric Space Approach" by Zezula et al. for a survey. These cannot be used with non metric similarity measures.

<!--[Read Javadoc for a detailed description](http://api123.web-d.be/api/java-string-similarity/head/index.html)--> <!-- TODO.JB - API documentation link? -->

Shingles (n-gram) based similarity and distance

A few algorithms work by converting strings into sets of n-grams (sequences of n characters, also sometimes called k-shingles). The similarity or distance between the strings is then the similarity or distance between the sets.

Some ot them, like jaccard, consider strings as sets of shingles, and don't consider the number of occurences of each shingle. Others, like cosine similarity, work using what is sometimes called the profile of the strings, which takes into account the number of occurences of each shingle.

For these algorithms, another use case is possible when dealing with large datasets:

1. compute the set or profile representation of all the strings
2. compute the similarity between sets or profiles

Levenshtein

The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

It is a metric string distance. This implementation uses dynamic programming (Wagner–Fischer algorithm), with only 2 rows of data. The space requirement is thus O(m) and the algorithm runs in O(m.n).

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"));
        Console.WriteLine(l.Distance("My string", "My $tring"));
        Console.WriteLine(l.Distance("My string", "My $tring"));
    }    
}

Normalized Levenshtein

This distance is computed as levenshtein distance divided by the length of the longest string. The resulting value is always in the interval [0.0 1.0] but it is not a metric anymore!

The similarity is computed as 1 - normalized distance.

using System;
using F23.StringSimilarity;

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

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

Weighted Levenshtein

An implementation of Levenshtein that allows to define different weights for different character substitutions.

This algorithm is usually used for optical character recognition (OCR) applications. For OCR, the cost of substituting P and R is lower then the cost of substituting P and M for example because because from and OCR point of view P is similar to R.

It can also be used for keyboard typing auto-correction. Here the cost of substituting E and R is lower for example because the