SQL - Similarity between two strings of varying length

David Budiac picture David Budiac · Sep 5, 2013 · Viewed 9.9k times · Source

I have a SQL Server table of products, and each product has a description that is publicly available on our website. I want to prevent, or at least warn our users when, a description is too similar to another product's description. Each product's description length can greatly vary.

I'd like query for products with descriptions that include duplicate/similar paragraphs/blocks of text between one another. i.e. String A has a bunch of unique content, but shares a similar/identical paragraph w/ string B. However, I'm not sure which similarity algorithm is best to use:

Fuzzy hashing sort of sounds what I'm looking for, but I'm not just looking for duplicate content w/ subtle differences. I'm also looking for duplicate content w/ subtle differences injected within a unique block of text. And I'd have no idea how to implement fuzzy hashes in SQL. SOUNDEX() and DIFFERENCE() appear to use fuzzy hashing, but are quite imprecise for my use case.

Ideally the similarity SQL function would be fast, but I could store cached similarity values in another table and schedule a job to occasionally update.

What is the best algorithm/SQL (or CLR integration) implementation to accomplish this?

Answer

Stefan Steiger picture Stefan Steiger · Sep 10, 2013

I not-so-recently had to join group names by fuzzy string matching.
I have tried about 40 different algorithms, but none was good enough to do this,even though the groupnames writing only differed by some spelling mistakes, missing whitespaces, and occasional added _mLF at the end.

So if you attempt a similar thing, I strongly suggest you stop right now, and send the data (in my case Excel-file) back to the users for correction, where it belongs.

If you're really just interested in comparing strings, this link may be just what you need:
http://anastasiosyal.com/POST/2009/01/11/18.ASPX

I found the Jaro-Winkler function to yield the best results in my case, but you can test that for yourselfs.