Sometimes you need to know how similar words are, rather than whether they are identical. To get a general measure of similarity is tricky, impossible probably, because similarity is so strongly determined by culture. The Soundex algorithm can come up with some matches but insists that, for example, ‘voluptuousness’ and ‘velvet’ are similar. Family genealogists in Britain would never find a search algorithm that helped them to realise that some branches of the Theobald family spell their surname ‘Tibble’, though Soundex knows they are quite close. To gauge this sort of similarity, you need to know the context of language, pronunciation, culture and semantics. However, we can fall back on more scientific measures based on comparing sequences, though they will never be perfect.
‘Edit distance’ is the obvious way of measuring similarity of sequences of values, and strings are just sequences of characters. How many edits are needed to convert the first string into the second? Edits can be insertions, deletions, replacements or transpositions. Algorithms to do this ‘string-to-string correction problem‘ for any sequences have been current since the Sixties, and have become increasingly refined for a range of sciences such as genome research, Forensics, Dendrochronology, and for predictive text.
The Dynamic approach to finding an edit distance is best done with a matrix. Solutions for this exist for all manner of languages. SQL is handicapped by having no support for matrices. An equivalent relation can be used instead, but it is overkill, and slow. We don’t need all the wonderful things a relation gives us. The fastest dynamic solutions in SQL tend to use Unicode strings as cod matrices since these can be cajoled into use as integer matrixes, but they are painful to use and debug.
Fortunately, Third-party CLR functions exist for calculating Damerau-Levenshtein Distance in SQL Server. Levenshtein Distance, developed by Vladimir Levenshtein in 1965, is the algorithm we learn in college for measuring edit-difference. It doesn’t deal perfectly with transpositions because it doesn’t even attempt to detect them: it records one transposition as two edits: an insertion and a deletion. The Damerau-Levenshtein algorithm for Edit Distance solves this.
Here is a simple implementation of the Levenshtein algorithm, using the full matrix. In this version, I’ve restricted the length of string just so as to get a good performance. I doubled performance by removing the NVARCHAR(MAX)s. I is, hopefully, useful just to understand the algorithm, because once all the clever short-cuts are used, it can all get rather opaque.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
CREATE function LEVENSHTEIN ( @SourceString nvarchar(100), @TargetString nvarchar(100) ) --Returns the Levenshtein Distance between @SourceString string and @TargetString --Translated to TSQL by Joseph Gama --Updated slightly by Phil Factor returns int as BEGIN DECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int, @ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int, @Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells int -- Step 1: Set n to be the length of s. Set m to be the length of t. -- If n = 0, return m and exit. -- If m = 0, return n and exit. -- Construct a matrix containing 0..m rows and 0..n columns. if @SourceString is null or @TargetString is null return null Select @SourceStringLength=LEN(@SourceString), @TargetStringLength=LEN(@TargetString), @Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1)) If @SourceStringLength = 0 return @TargetStringLength If @TargetStringLength = 0 return @SourceStringLength if (@TargetStringLength+1)*(@SourceStringLength+1)> 4000 return -1 --Step 2: Initialize the first row to 0..n. -- Initialize the first column to 0..m. SET @ii=0 WHILE @ii<=@SourceStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))--d(i, 0) = i SET @ii=@ii+1 END SET @ii=0 WHILE @ii<=@TargetStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))--d(0, j) = j SET @ii=@ii+1 END --Step 3 Examine each character of s (i from 1 to n). SET @ii=1 WHILE @ii<=@SourceStringLength BEGIN --Step 4 Examine each character of t (j from 1 to m). SET @jj=1 WHILE @jj<=@TargetStringLength BEGIN --Step 5 and 6 Select --Set cell d[i,j] of the matrix equal to the minimum of: --a. The cell immediately above plus 1: d[i-1,j] + 1. --b. The cell immediately to the left plus 1: d[i,j-1] + 1. --c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost @Above=unicode(substring(@Matrix,@jj*(@SourceStringLength+1)+@ii-1+1,1))+1, @ToTheLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1,1))+1, @AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1)) + case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1)) then 0 else 1 end--the cost -- If s[i] equals t[j], the cost is 0. -- If s[i] doesn't equal t[j], the cost is 1. -- now calculate the minimum value of the three if (@Above < @ToTheLeft) AND (@Above < @AboveAndToLeft) select @MinimumValueOfCells=@Above else if (@ToTheLeft < @Above) AND (@ToTheLeft < @AboveAndToLeft) select @MinimumValueOfCells=@ToTheLeft else select @MinimumValueOfCells=@AboveAndToLeft Select @Matrix=STUFF(@Matrix, @jj*(@SourceStringLength+1)+@ii+1,1, nchar(@MinimumValueOfCells)), @jj=@jj+1 END SET @ii=@ii+1 END --Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m] return unicode(substring( @Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1 )) END go |
Here is the same basic code with the additions to turn it into the Damerau-Levenshtein algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
CREATE function DamerauLevenschtein ( @SourceString nvarchar(100), @TargetString nvarchar(100) ) --Returns the Damerau Levenshtein Distance between @SourceString string and @TargetString --Updated by Phil Factor to add transposition as an edit returns int as BEGIN --DECLARE @SourceString nvarchar(100)='achieve', @TargetString nvarchar(100)='acheive' DECLARE @Matrix Nvarchar(4000), @LD int, @TargetStringLength int, @SourceStringLength int, @ii int, @jj int, @CurrentSourceChar nchar(1), @CurrentTargetChar nchar(1),@Cost int, @Above int,@AboveAndToLeft int,@ToTheLeft int, @MinimumValueOfCells INT, @previous INT -- Step 1: Set n to be the length of s. Set m to be the length of t. SELECT @SourceString=RTRIM(LTRIM(COALESCE(@sourceString,''))), @TargetString=RTRIM(LTRIM(COALESCE(@TargetString,''))), @SourceStringLength=LEN(@SourceString), @TargetStringLength=LEN(@TargetString) -- remove matches at the beginning and end IF SUBSTRING(@sourceString,1,1)=SUBSTRING(@targetString,1,1) BEGIN SET @ii=1 WHILE SUBSTRING(@sourceString+'!!',@ii+1,1)=SUBSTRING(@targetString+'??',@ii+1,1) BEGIN SELECT @ii=@ii+1 END SELECT @sourceString=STUFF(@sourceString,1,@ii,''), @targetString=STUFF(@targetString,1,@ii,'') END SELECT @SourceStringLength =LEN(@sourceString), @TargetStringLength =LEN(@TargetString) IF SUBSTRING(@sourceString,@SourceStringLength,1)=SUBSTRING(@targetString,@TargetStringLength,1) BEGIN WHILE SUBSTRING(@sourceString,@SourceStringLength-1,1)=SUBSTRING(@targetString,@TargetStringLength-1,1) AND @SourceStringLength>0 AND @TargetStringLength>0 BEGIN SELECT @SourceStringLength=@SourceStringLength-1, @TargetStringLength=@TargetStringLength-1 END SELECT @sourceString=LEFT(@sourceString,@SourceStringLength) SELECT @targetString=LEFT(@targetString,@TargetStringLength) END -- If n = 0, return m and exit. -- If m = 0, return n and exit. If @SourceStringLength = 0 return @TargetStringLength If @TargetStringLength = 0 return @SourceStringLength if (@TargetStringLength+1)*(@SourceStringLength+1)> 4000 return -1 IF @SourceStringLength=1 RETURN @TargetStringLength -CASE WHEN CHARINDEX(@SourceString,@TargetString)>0 THEN 1 ELSE 0 end IF @TargetStringLength=1 RETURN @SourceStringLength -CASE WHEN CHARINDEX(@TargetString,@SourceString)>0 THEN 1 ELSE 0 end -- Construct a matrix containing 0..m rows and 0..n columns. SELECT @Matrix=replicate(nchar(0),(@SourceStringLength+1)*(@TargetStringLength+1)) --Step 2: Initialize the first row to 0..n. -- Initialize the first column to 0..m. SET @ii=0 WHILE @ii<=@SourceStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii+1,1,nchar(@ii))--d(i, 0) = i SET @ii=@ii+1 END SET @ii=0 WHILE @ii<=@TargetStringLength BEGIN SET @Matrix=STUFF(@Matrix,@ii*(@SourceStringLength+1)+1,1,nchar(@ii))--d(0, j) = j SET @ii=@ii+1 END --Step 3 Examine each character of s (i from 1 to n). SET @ii=1 WHILE @ii<=@SourceStringLength BEGIN --Step 4 Examine each character of t (j from 1 to m). SET @jj=1 WHILE @jj<=@TargetStringLength BEGIN --Step 5 and 6 Select --Set cell d[i,j] of the matrix equal to the minimum of: --a. The cell immediately above plus 1: d[i-1,j] + 1. --b. The cell immediately to the left plus 1: d[i,j-1] + 1. --c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost @Cost=case when (substring(@SourceString,@ii,1)) = (substring(@TargetString,@jj,1)) then 0 else 1 END,--the cost -- If s[i] equals t[j], the cost is 0. -- If s[i] doesn't equal t[j], the cost is 1. @Above =unicode(substring(@Matrix, @jj * (@SourceStringLength+1)+@ii-1+1,1))+1, @ToTheLeft =unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii+1 ,1))+1, @AboveAndToLeft=unicode(substring(@Matrix,(@jj-1)*(@SourceStringLength+1)+@ii-1+1,1))+@cost, @previous =unicode(substring(@Matrix,(@jj-2)*(@SourceStringLength+1)+@ii-2+1,1))+@cost -- now calculate the minimum value of the three if (@Above < @ToTheLeft) AND (@Above < @AboveAndToLeft) select @MinimumValueOfCells=@Above else if (@ToTheLeft < @Above) AND (@ToTheLeft < @AboveAndToLeft) select @MinimumValueOfCells=@ToTheLeft else select @MinimumValueOfCells=@AboveAndToLeft IF (substring(@SourceString,@ii,1) = substring(@TargetString,@jj-1,1) and substring(@TargetString,@jj,1) = substring(@SourceString,@ii-1,1)) begin SELECT @MinimumValueOfCells = CASE WHEN @MinimumValueOfCells< @previous THEN @MinimumValueOfCells ELSE @previous END end --write it to the matrix SELECT @Matrix=STUFF(@Matrix, @jj*(@SourceStringLength+1)+@ii+1,1, nchar(@MinimumValueOfCells)), @jj=@jj+1 END SET @ii=@ii+1 END --Step 7 After iteration steps (3, 4, 5, 6) are complete, distance is found in cell d[n,m] return unicode(substring( @Matrix,@SourceStringLength*(@TargetStringLength+1)+@TargetStringLength+1,1 )) end |
The best SQL solution I know of for the Levenshtein algorithm is the one attributed pseudonymously to ‘Arnold Fribble’ (possibly a reference to Arnold Rimmer of Red Dwarf, and his ‘friend’ Mr Flibble.) which is a SQL version of the improved Levenshtein algorithm that dispenses with the full matrix and just uses two vectors instead. It is featured here. There are improved versions around, such as the one here. They take around two thirds of the time to produce their result compared with the full-matrix version.
Can this be done in a relational way? Yes, but without support for matrixes, it is a bit painful, with the full-matrix version taking ten times as long as the string-based version. There is plenty of room for improvement though.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
alter FUNCTION LevenschteinDifference ( @FirstString nVarchar(255), @SecondString nVarchar(255) ) RETURNS int as begin Declare @PseudoMatrix table (location int identity primary key, firstorder int not null, Firstch nchar(1), secondorder int not null, Secondch nchar(1), Thevalue int not null default 0, PreviousRowValues varchar(200) ) insert into @PseudoMatrix (firstorder, firstch, secondorder, secondch, TheValue ) SELECT TheFirst.number,TheFirst.ch, TheSecond.number,TheSecond.ch,0 FROM --divide up the first string into a table of characters/sequence (SELECT number, SUBSTRING(@FirstString,number,1) AS ch FROM numbers WHERE number <= LEN(@FirstString) union all Select 0,Char(0)) TheFirst cross JOIN --divide up the second string into a table of characters/sequence (SELECT number, SUBSTRING(@SecondString,number,1) AS ch FROM numbers WHERE number <= LEN(@SecondString) union all Select 0,Char(0)) TheSecond --ON Thefirst.ch= Thesecond.ch --do all valid matches order by TheFirst.number, TheSecond.number Declare @current Varchar(255) Declare @previous Varchar(255) Declare @TheValue int Declare @Deletion int, @Insertion int, @Substitution int, @minim int Select @current='', @previous='' Update @PseudoMatrix Set @Deletion=@TheValue+1, @Insertion=ascii(substring(@previous,secondorder+1,1))+1, @Substitution=ascii(substring(@previous,(secondorder),1)) +1, @minim=case when @Deletion<@Insertion then @Deletion else @insertion end, @TheValue = Thevalue = case --when Firstorder+SecondOrder=0 then 0 when SecondOrder=0 then FirstOrder When FirstOrder=0 then Secondorder when FirstCh=SecondCh then ascii(substring(@previous,(secondorder),1)) else case when @Minim<@Substitution then @Minim else @Substitution end end, @Previous=PreviousRowValues=case when secondorder =0 then @current else @Previous end, @current= case when secondorder =0 then char(@TheValue) else @Current+char(@TheValue) end return @TheValue End Go |
What to use? If I need the performance, and I’m allowed CLR, I use the CLR approach. Otherwise, I still go for the ‘Arnold Fribble’ approach to comparing strings It scales reasonably well and is reasonably fast, but I can’t help thinking that with window functions and number table, it would be possible to get an ‘edit distance’ figure efficiently from a routine that is genuinely relational.
Load comments