Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

Question

There are similar question, but not regarding C# libraries I can use in my source code.

Thank you all for your help.

I've already saw lucene, but I need something more easy to search for similar strings and without the overhead of the indexing part.

The answer I marked has got two very easy algorithms, and one uses LINQ too, so it's perfect.

Why this is off-topic escapes me. The OP is asking if there is a function in a library that SO supports in-depth. — 101010, Sep 12 '14 at 13:17

score 35 · Accepted Answer · edited Sep 07 '12 at 11:15

35

Levenshtein distance implementation:

Using LINQ (not really, see comments)
Not using LINQ

I have a .NET 1.1 project in which I use the latter. It's simplistic, but works perfectly for what I need. From what I remember it needed a bit of tweaking, but nothing that wasn't obvious.

edited Sep 07 '12 at 11:15

brianpeiris

10,735
1
31
44

answered Sep 17 '08 at 14:38

George Mauer

117,483
131
382
612

2

Why do you say "Using LINQ" ? None of these implementations uses Linq... – Thomas Levesque Sep 04 '09 at 07:57
1

Actually these implementations are identical, except that the latter uses Substring, which is much slower than using the indexer because it creates new String instances each time... – Thomas Levesque Sep 04 '09 at 08:11
Indeed you are correct. I could have sworn that there was some LINQ-love in it, or at least that the headline claimed it was LINQy or something. – George Mauer Sep 04 '09 at 15:37
What if I have 100,000 entries to search, and I want to show the top 20 candidates each time? – Hamish Grubijan May 12 '11 at 00:56
Dead link may now be here http://www.dotnetperls.com/levenshtein – Roman Nov 22 '11 at 16:24

score 32 · Answer 2 · edited Feb 26 '20 at 15:31

32

you can also look at the very impressive library titled Sam's String Metrics https://github.com/StefH/SimMetrics.Net . this includes a host of algorithms.

Hamming distance
Levenshtein distance
Needleman-Wunch distance or Sellers Algorithm
Smith-Waterman distance
Gotoh Distance or Smith-Waterman-Gotoh distance
Block distance or L1 distance or City block distance
Monge Elkan distance
Jaro distance metric
Jaro Winkler
SoundEx distance metric
Matching Coefficient
Dice’s Coefficient
Jaccard Similarity or Jaccard Coefficient or Tanimoto coefficient
Overlap Coefficient
Euclidean distance or L2 distance
Cosine similarity
Variational distance
Hellinger distance or Bhattacharyya distance
Information Radius (Jensen-Shannon divergence)
Harmonic Mean
Skew divergence
Confusion Probability
Tau
Fellegi and Sunters (SFS) metric
TFIDF or TF/IDF
FastA
BlastP
Maximal matches
q-gram
Ukkonen Algorithms

edited Feb 26 '20 at 15:31

Tangurena

2,121
1
22
41

answered Jul 08 '09 at 02:04

Zaffiro

4,834
5
36
47

14

The link in this answer is giving me a 403 error. You can use the [Wayback Machine](http://web.archive.org/web/http://staffwww.dcs.shef.ac.uk/people/sam.chapman@k-now.co.uk/stringmetrics.html) instead. – Paul Ruane Aug 04 '11 at 15:41
I believe the .NET version of the library mentioned above is [here](http://sourceforge.net/projects/simmetrics/files/). After I converted it to Visual Studio 2010, and updated NUnit references, it builds. It also passes 87 tests. – dalenewman Feb 08 '12 at 17:14
1

I found a .net library version of this library on [SimMetrics.Net on GitHub](https://github.com/StefH/SimMetrics.Net). The same as the suggestion from @dalenewman, just on github perhaps? – Spiralis Oct 10 '17 at 11:21

score 14 · Answer 3 · edited Jul 23 '15 at 14:03

14

They are not my own invention, but they are my favorites and I've just blogged about them and published my own tweaked versions of Dice Coefficient, Levenshtein Distance, Longest Common Subsequence and Double Metaphone in a blog post called Four Functions for Finding Fuzzy String Matches in C# Extensions.

edited Jul 23 '15 at 14:03

trailmax

34,305
22
140
234

answered May 28 '11 at 01:42

Tyler Jensen

811
6
12

1

These are ready-made in a class that you can just drop into your project. This is the easy man's way to go. – cjbarth Jun 11 '12 at 19:25
code now on GitHub https://github.com/tylerjensen/duovia-fuzzystrings – DanO Mar 03 '15 at 21:19
Updated link to the blog post: http://www.tsjensen.com/blog/post/2011/05/27/Four+Functions+For+Finding+Fuzzy+String+Matches+In+C+Extensions.aspx – Good Night Nerd Pride Apr 02 '15 at 09:30

score 2 · Answer 4 · answered Sep 17 '08 at 14:33

2

Have you taken a look at Lucene.net? It is a port of the Java Lucene search engine API to the .Net platform. That library offers a lot of search functionality. I played around with it a year or so ago, so don't take my suggestion as based on tons of experience. I saw it in the book Windows Developer Power Tools and took it for a test drive. You might look through their API documentation to see if it offers something like the Fuzzy Search for which you are looking.

answered Sep 17 '08 at 14:33

Jason Jackson

17,016
8
49
74

Could you please tell how to get the degree of similarity using Lucene? – Eugeniu Torica Feb 11 '10 at 11:24
Sorry, I have not used it professionally. As I mentioned in my post, I just played around with it probably around 2007/2008. – Jason Jackson Feb 12 '10 at 00:21
Maybe the book [Lucene in Action, 2ed](http://goo.gl/0sKkw7) could tell how to get the degree of similarity. – AechoLiu Mar 06 '14 at 07:35

score 1 · Answer 5 · answered Sep 17 '08 at 14:35

1

This code project paper has a string similarity function using the Levenshtein distance.

answered Sep 17 '08 at 14:35

Ed Schwehm

2,163
4
32
55

score 1 · Answer 6 · edited Aug 26 '17 at 01:21

1

There is the following Levenshtein Distance Algorithm which assigns a value to the similarity of two strings (well, the difference actually), that could be used to build upon: http://www.merriampark.com/ldcsharp.htm

edited Aug 26 '17 at 01:21

josliber

43,891
12
98
133

answered Sep 17 '08 at 14:37

benefactual

7,079
5
23
16

score 0 · Answer 7 · answered Sep 17 '08 at 14:28

The Beagle Project for Linux is written in c# (mono) and is a google-desktop like search tool. It may have some code in there for these kind of string matching.

If I recall correctly, it uses the Lucene library for searching and retrieving data. Maybe that can be useful for your project too.

score 0 · Answer 8 · answered Sep 17 '08 at 16:26

0

I have used "Ternary Search Tree Dictionary in C#" (http://www.codeproject.com/KB/recipes/tst.aspx) to search for similar strings.

Regards, Patricio

answered Sep 17 '08 at 16:26

Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

8 Answers8

Linked

Related