When you compare two pieces of text, or strings, in SQL Server in an expression, you will get just get a value of ‘true’ returned if the two were the same, ‘false’ if they were not, or ‘null’ if one of the pieces of text was null. <\/p>\n
A simple matter of an extra space character is often enough to tip the balance. This is quite unlike real life – If we look at two pieces of text we judge them to be the same, almost the same, quite similar, nothing like each other and many shades in-between. Surely, we need to quantify differences? <\/p>\n
![\"435-mediaevalSmall.jpg\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/imported\/435-mediaevalSmall.jpg\")
<\/p>\nText difference algorithms are as
old as the hills- but not in TSQL<\/p>\n<\/div>\n
In IT applications, there are several times when one needs more of a measure of the differences between text, than a simple ‘yes they’re the same\/ no they are not’. A typical problem is in finding duplicates in database entries where the understanding of ‘duplicate’ allows for minor differences. Finding a reliable algorithm for quantifying similarity in text is quite hard, especially one that is set-based. TSQL has no native means to use regular expressions and other means of making life easier for this sort of work <\/p>\n
I find this problem quite intriguing. I think that there is a general consensus that the Levenshtein string distance algorithm is the best for giving you the difference on a character-by-character basis, and I provide some code at the end for doing this. The algorithm was developed by Vladimir Levenshtein in 1965. It tells you the number of edits required to turn one string into another by breaking down string transformation into three basic operations: adding, deleting, and replacing a character. Each operation is assigned a cost of 1. Leaving a character unchanged has a cost of 0. There are some other algorithms. I’m not at all convinced by ‘soundex’ algorithms- they don’t seem to help much. <\/p>\n
I decided that what I wanted was a difference based on words rather than characters. I find that the solution, the difference counter, that I give below pretty handy, though it sometimes gives a score for differences that I don’t like. Try it yourselves with a variety of strings and you’ll see it makes a pretty good attempt. It is, of course, slow, because of the tedium of breaking down text into words and white-space. In normal use, this is only done once, when importing text into the database, when it is placed in an ‘inversion table’. One can use this data to test the similarity of the original text, which is much faster. Just so as to include those stuck on SQL Server 2000, I’ve made the function use a nTEXT parameter rather than a VARCHAR(MAX) though the latter would have made for a simpler routine <\/p>\n
“Cleaning data is not
an exact science”<\/p>\n
In reality, every time one comes across a requirement where one has to check for differences, there are subtle requirements that are never the same. Cleaning data is not an exact science. I generally prefer to ignore ‘white-space’, including new-lines and punctuation, when checking for differences. My approach is to break down text into words and ‘not-words’, or white-space. I refer to these as different types of token. The table function I give below allows you to define a word in terms of the characters that make up a word. This is different in other languages. The routine is generally, though not always, much faster if one uses a ‘number table’ but I decided that creating one for this article was a distraction for the reader .<\/p>\n
With the use of the ‘parsing’ table-function, I then do a simple outer join between the two collections of words, and count the number of times that the minimum ‘best-fit’ between words changes in the sequence of words. This is of course, an approximation: I should be using sliders and other devices that use iteration. At some point one has to hand over to the computer scientists. I tend to stop at the point where the routine does the job I want. <\/p>\n
As a flourish, I’ve provided, at the end, a variation of the function that provides a single-row table giving the first point at which the two samples of text diverge. It is really just a by-product of the first routine but I slipped it in to give a suggestion of the many ways the routine can be adapted for particular purposes. It is surprisingly handy for applications such as summary reports of the latest changes made to stored procedures! <\/p>\n
First the ‘classic Levenshtein string distance in TSQ (using strings instead of arrays)<\/p>\n
\tcreate FUNCTION Levenshtein_Distance(@Source nvarchar(4000), @Target nvarchar(4000))\n\tRETURNS int\n\tAS\n\t\/*\n\tThe Levenshtein string distance algorithm was developed by Vladimir Levenshtein in 1965. It tells you the number of edits required to turn one string into another by breaking down string transformation into three basic operations: adding, deleting, and replacing a character. Each operation is assigned a cost of 1. Leaving a character unchanged has a cost of 0.\n\tThis is a translation of 'Fast, memory efficient Levenshtein algorithm' By Sten Hjelmqvist, originally converted to SQL by Arnold Fribble\n\thttp:\/\/www.codeproject.com\/Articles\/13525\/Fast-memory-efficient-Levenshtein-algorithm\n\t*\/\n\tBEGIN\n\t Declare @MaxDistance int\n\t Select @MaxDistance=200\n\t DECLARE @SourceStringLength int, @TargetStringLength int, @ii int, @jj int, @SourceCharacter nchar, @Cost int, @Cost1 int,\n\t -- create two work vectors of integer distances\n\t @Current_Row nvarchar(200), @Previous_Row nvarchar(200), @Min_Cost int\n\t SELECT @SourceStringLength = LEN(@Source), \n\t @TargetStringLength = LEN(@Target), \n\t @Previous_Row = '', \n\t @jj = 1, @ii = 1, \n\t @Cost = 0, @MaxDistance=200\n\t -- do the degenerate cases\n\t if @Source = @Target return (@Cost);\n\t if @SourceStringLength= 0 return @TargetStringLength;\n\t if @TargetStringLength= 0 return @SourceStringLength;\n\t \n\t -- initialize the previous row of distances\n\t -- this row is edit distance for an empty source string\n\t -- the distance is just the number of characters to delete from the target\n\t WHILE @jj <= @TargetStringLength\n\t SELECT @Previous_Row = @Previous_Row + NCHAR(@jj), @jj = @jj + 1\n\t\n\t WHILE @ii <= @SourceStringLength\n\t BEGIN\n\t SELECT @SourceCharacter = SUBSTRING(@Source, @ii, 1),\n\t @Cost1 = @ii, \n\t @Cost = @ii, \n\t @Current_Row = '', \n\t @jj = 1, \n\t @Min_Cost = 4000\n\t WHILE @jj <= @TargetStringLength\n\t BEGIN -- use formula to fill in the rest of the row\n\t SET @Cost = @Cost + 1\n\t --v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);\n\t SET @Cost1 = @Cost1 - CASE WHEN @SourceCharacter = SUBSTRING(@Target, @jj, 1) THEN 1 ELSE 0 END\n\t IF @Cost > @Cost1 SET @Cost = @Cost1\n\t SET @Cost1 = UNICODE(SUBSTRING(@Previous_Row, @jj, 1)) + 1\n\t IF @Cost > @Cost1 SET @Cost = @Cost1\n\t IF @Cost < @Min_Cost SET @Min_Cost = @Cost\n\t SELECT @Current_Row = @Current_Row + NCHAR(@Cost), @jj = @jj + 1\n\t END\n\t IF @Min_Cost > @MaxDistance return -1\n\t -- copy current row to previous row for next iteration\n\t SELECT @Previous_Row = @Current_Row, @ii = @ii + 1\n\t END\n\t RETURN @Cost \n\tEND\n\tGO\n\t<\/pre>\n…and now the equivalent system for detecting word differences<\/p>\n
IF OBJECT_ID(N'dbo.uftWordTokens') IS NOT NULL \n DROP FUNCTION dbo.uftWordTokens \nGO \n\n\/*------------------------------------------------------------*\/ \nCREATE FUNCTION [dbo].[uftWordTokens] \n ( \n @string NTEXT, \n @WordStartCharacters VARCHAR(255) = 'a-z', \n @WordCharacters VARCHAR(255) = '-a-z''' \n ) \nRETURNS @Results TABLE \n ( \n SeqNo INT IDENTITY(1, 1), \n Item VARCHAR(255), \n TokenType INT \n ) \nAS \/* \nThis table function produces a table which divides up the words and \nthe spaces between the words in some text and produces a table of the \ntwo types of token in the sequence in which they were found \n*\/ \n BEGIN \n DECLARE @Pos INT, --index of current search \n @WhereWeAre INT,--index into string so far \n @ii INT, --the number of words found so far \n @next INT, --where the next search starts \n @size INT --the total size of the text \n\n SELECT @ii = 0, @WhereWeAre = 1, @size = DATALENGTH(@string) \n\n\n WHILE @Size >= @WhereWeAre \n BEGIN \n SELECT @pos = PATINDEX('%[' + @wordStartCharacters + ']%', \n SUBSTRING(@string, @whereWeAre, 4000)) \n IF @pos > 0 \n BEGIN \n IF @pos > 1 \n INSERT INTO @Results \n ( item, tokentype ) \n SELECT SUBSTRING(@String, @whereWeAre, @pos - 1), 2 \n SELECT @next = @WhereWeAre + @pos, @ii = @ii + 1 \n SELECT @pos = PATINDEX('%[^' + @wordCharacters + ']%', \n SUBSTRING(@string, @next, 4000) + ' ') \n INSERT INTO @Results \n ( item, tokentype ) \n SELECT SUBSTRING(@String, @next - 1, @pos), 1 \n SELECT @WhereWeAre = @next + @pos - 1 \n END \n ELSE \n BEGIN \n IF LEN(REPLACE( \n SUBSTRING(@String, @whereWeAre, 4000), ' ', '!' \n )) > 0 \n INSERT INTO @Results \n ( item, tokentype ) \n SELECT SUBSTRING(@String, @whereWeAre, 4000), 2 \n SELECT @whereWeAre = @WhereWeAre + 4000 \n END \n END \n RETURN \n END \n\n\/* Tests: \nSELECT '[' + item + ']', tokentype \nFROM dbo.uftWordTokens('This has \n been relentlessly \n,^----tested', DEFAULT, DEFAULT) \nSELECT '[' + item + ']', tokentype \nFROM dbo.uftWordTokens('This has been relentlessly tested !', \n DEFAULT, DEFAULT) \nSELECT item, tokentype \nFROM dbo.uftWordTokens('This has been', DEFAULT, DEFAULT) \nSELECT '[' + item + ']', tokentype \nFROM dbo.uftWordTokens(' <!-- 23 343.43 <div>Hello there .... -->', \n DEFAULT, DEFAULT) \n\n*\/ \nGO \n\nIF OBJECT_ID(N'dbo.ufnDifferencesInText') IS NOT NULL \n DROP FUNCTION dbo.ufiDifferencesInText \nGO \n\/*------------------------------------------------------------*\/ \nCREATE FUNCTION dbo.ufiDifferencesInText \n ( \n @Sample NTEXT, \n @comparison NTEXT \n ) \nRETURNS INT \nAS BEGIN \n DECLARE @results TABLE \n ( \n token_ID INT IDENTITY(1, 1), \n sequenceNumber INT, \n Sample_ID INT, \n Item VARCHAR(255), \n TokenType INT \n ) \n\/* \nThis function returns the number of differences it found between two pieces \nof text \n*\/ \n INSERT INTO @results \n ( SequenceNumber, Sample_ID, Item, Tokentype ) \n SELECT seqno, 1, item, tokentype \n FROM dbo.uftWordTokens(@sample, DEFAULT, DEFAULT) \n\n INSERT INTO @results \n ( SequenceNumber, Sample_ID, Item, Tokentype ) \n SELECT seqno, 2, item, tokentype \n FROM dbo.uftWordTokens(@comparison, DEFAULT, DEFAULT) \n DECLARE @closestMatch TABLE \n ( \n sequenceNumber INT, \n skew INT \n ) \n INSERT INTO @closestMatch \n ( sequencenumber, skew ) \n SELECT COALESCE(a.sequencenumber, b.sequencenumber), \n COALESCEE(MIN(ABS(COALESCE(b.sequenceNumber, 1000) \n - COALESCE(a.sequencenumber, 1000))), \n -1) \n FROM ( SELECT * \n FROM @results \n WHERE sample_ID = 1 AND tokentype = 1 \n ) a FULL OUTER JOIN ( SELECT * \n FROM @results \n WHERE sample_ID = 2 \n AND tokentype = 1 \n ) b ON a.item = b.item \n GROUP BY COALESCE(a.sequencenumber, b.sequencenumber) \n ORDER BY COALESCE(a.sequencenumber, b.sequencenumber) \n\n\n\n RETURN ( SELECT SUM(CASE WHEN a.skew - b.skew = 0 THEN 0 \n ELSE 1 \n END) \n FROM @closestmatch a INNER JOIN @closestMatch b \n ON b.sequenceNumber = a.sequenceNumber + 2 \n ) \n END \nGO \n\nSELECT dbo.ufnDifferencesInText('I am a piece of text', \n 'I am a piece of text') \n--0 \nSELECT dbo.ufnDifferencesInText('I am a piece of text', \n 'I am not a piece of text') \n--1 \nSELECT dbo.ufnDifferencesInText('I am a piece of text', \n 'I am piece a a a of text') \n--2 \nSELECT dbo.ufnDifferencesInText('I piece of text', \n 'I am a piece of text') \n--1 \nSELECT dbo.ufnDifferencesInText('I am a pot of jam', \n 'I am a piece of text') \n--3 \nSELECT dbo.ufnDifferencesInText('I am a pot of jam', \n 'I am a pot of jam beloved by humans') \n--3 \nSELECT dbo.ufnDifferencesInText('I am a piece of text', \n 'text of piece a am I') \n--4 \nSELECT dbo.ufnDifferencesInText('I am a piece of text', \n 'this is completely different') \n--5 \nSELECT dbo.ufnDifferencesInText('I am a piece of text', '') \n--5 \nSELECT dbo.ufnDifferencesInText('', 'I am a piece of text') \n--5 \n\nSELECT dbo.ufnDifferencesInText('Call me Ishmael. Some years ago -- never mind how long precisely -- having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen, and regulating the circulation. Whenever I find myself growing grim about the mouth; whenever it is a damp, drizzly November in my soul; whenever I find myself involuntarily pausing before coffin warehouses, and bringing up the rear of every funeral I meet; and especially whenever my hypos get such an upper hand of me, that it requires a strong moral principle to prevent me from deliberately stepping into the street, and methodically knocking people''s hats off -- then, I account it high time to get to sea as soon as I can. This is my substitute for pistol and ball. With a philosophical flourish Cato throws himself upon his sword; I quietly take to the ship. There is nothing surprising in this. If they but knew it, almost all men in their degree, some time or other, cherish very nearly the same feelings towards the ocean with me.'\n, 'Call me Ishmael. Some years ago -- never mind how long precisely -- having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen, and regulating the circulation. Whenever I find myself growing grim about the mouth; whenever it is a damp, drizzly November in my soul; whenever I find myself involuntarily pausing before coffin warehouses, and bringing up the rear of every funeral I meet; and especially whenever my hypos get such an upper hand of me, that it requires a strong moral principle to prevent me from deliberately stepping into the street, and methodically knocking people''s hats off -- then, I account it high time to get to sea as soon as I can. This is my substitute for pistol and ball. With a philosophical flourish Cato throws himself upon his sword; I quietly take to the ship. There is nothing surprising in this. If they but knew it, almost all men in their degree, some time or other, cherish very nearly the same feelings towards the ocean with me.') \n\n\n-- ============================================= \n-- Description: A routine that returns a single-row which \n-- gives the context of the first difference between two \n-- strings \n-- ============================================= \nIF OBJECT_ID(N'dbo.uftShowFirstDifference') IS NOT NULL \n DROP FUNCTION dbo.uftShowFirstDifference \nGO \nCREATE FUNCTION uftShowFirstDifference \n ( \n -- Add the parameters for the function here \n @sample NTEXT, \n @comparison NTEXT \n ) \nRETURNS @result TABLE \n ( \n -- Add the column definitions for the TABLE variable here \n first VARCHAR(2000), \n second VARCHAR(2000), \n [where] INT \n ) \nAS BEGIN \n DECLARE @results TABLE \n ( \n token_ID INT IDENTITY(1, 1), \n sequenceNumber INT, \n Sample_ID INT, \n Item VARCHAR(255), \n TokenType INT \n ) \n INSERT INTO @results \n ( SequenceNumber, Sample_ID, Item, Tokentype ) \n SELECT seqno, 1, item, tokentype \n FROM dbo.uftWordTokens(@sample, DEFAULT, DEFAULT) \n\n INSERT INTO @results \n ( SequenceNumber, Sample_ID, Item, Tokentype ) \n SELECT seqno, 2, item, tokentype \n FROM dbo.uftWordTokens(@comparison, DEFAULT, DEFAULT) \n DECLARE @closestMatch TABLE \n ( \n sequenceNumber INT, \n skew INT \n ) \n INSERT INTO @closestMatch \n ( sequencenumber, skew ) \n SELECT COALESCE(a.sequencenumber, b.sequencenumber), \n COALESCE(MIN(ABS(COALESCE(b.sequenceNumber, 1000) \n - COALESCE(a.sequencenumber, 1000))), \n -1) \n FROM ( SELECT * \n FROM @results \n WHERE sample_ID = 1 AND tokentype = 1 \n ) a FULL OUTER JOIN ( SELECT * \n FROM @results \n WHERE sample_ID = 2 \n AND tokentype = 1 \n ) b ON a.item = b.item \n GROUP BY COALESCE(a.sequencenumber, b.sequencenumber) \n ORDER BY COALESCE(a.sequencenumber, b.sequencenumber) \n\n\n\n DECLARE @first VARCHAR(2000) \n DECLARE @firstDifference INT \n DECLARE @second VARCHAR(2000) \n SELECT @FirstDifference = MIN(sequenceNumber) \n FROM @closestMatch \n WHERE skew <> 0 \n SELECT @first = '', @second = '' \n SELECT TOP 10 \n @first = COALESCE(@First, '') + item \n FROM @results \n WHERE sample_ID = 1 AND sequenceNumber >= @FirstDifference \n ORDER BY SequenceNumber \n SELECT TOP 10 \n @second = COALESCE(@second, '') + item \n FROM @results \n WHERE sample_ID = 2 AND sequenceNumber >= @FirstDifference \n ORDER BY SequenceNumber \n INSERT INTO @result \n ( first, Second, [where] ) \n SELECT [first] = @First, [second] = @second, \n [where] = @FirstDifference \n\n RETURN \n END \nGO \n\nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', \n 'I am a piece of text') \n-- NULL \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', \n 'I am not a piece of text') \n--a piece of text not a piece of text 5 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', \n 'I am piece a a a of text') \n--a piece of text piece a a a of 5 \nSELECT * \nFROM dbo.uftShowFirstDifference('I piece of text', \n 'I am a piece of text') \n--piece of text am a piece of text 3 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a pot of jam', \n 'I am a piece of text') \n--pot of jam piece of text 7 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a pot of jam', \n 'I am a pot of jam beloved by humans') \n-- beloved by humans 13 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', \n 'text of piece a am I') \n--I am a piece of text of piece a am 1 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', \n 'this is completely different') \n--I am a piece of this is completely different 1 \nSELECT * \nFROM dbo.uftShowFirstDifference('I am a piece of text', '') \n--I am a piece of 1 \nSELECT * \nFROM dbo.uftShowFirstDifference('', 'I am a piece of text') \n-- I am a piece of 1 \n\n<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"In TSQL there is a limit to the way you can compare text strings. They’re either equal or not. Sooner or later, usually when cleaning data, something more subtle is required!…<\/p>\n","protected":false},"author":213195,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143531],"tags":[4150,4252,4190,4821],"coauthors":[],"class_list":["post-307","post","type-post","status-publish","format-standard","hentry","category-t-sql-programming-sql-server","tag-sql","tag-t-sql-programming","tag-tsql","tag-tsql-sql-server-quantify-text-differences-transact"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/307","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/213195"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=307"}],"version-history":[{"count":5,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/307\/revisions"}],"predecessor-version":[{"id":92566,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/307\/revisions\/92566"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=307"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}