Levenshtein Distance Algorithm (TSQL)

Levenshtein Distance represents the minimum number of letter changes required to convert a word to another word.

The below TSQL code gives the Levenshtein Distance (letter changes required) to convert "Saturday" to "Sunday".


SET NOCOUNT ON
DECLARE @a VARCHAR(100) = 'sunday', @b VARCHAR(100) = 'saturday'
DECLARE @lddistance VARCHAR(10)
DECLARE @lena INT = (SELECT LEN(@a)), @lenb INT = (SELECT LEN(@b)), @lena2 INT, @lenb2 INT
SELECT @lena2 = @lena, @lenb2 = @lenb
DECLARE @qry NVARCHAR(1000), @lblcntr INT = 3
DECLARE @colcount INT = 0, @colcount2 INT = 0, @rowcount INT = 0,@rowcount2 INT = 0

CREATE TABLE #LDAlg (lbl0 VARCHAR(10),lbl1 VARCHAR(10),[0] INT)
INSERT #LDAlg (lbl0,lbl1,[0]) SELECT 'R1',NULL,NULL UNION ALL SELECT 'R2',NULL,NULL

WHILE(@lenb >0)
BEGIN
SET @qry = 'ALTER TABLE #LDAlg ADD ['+ CAST(@lenb2+1-@lenb AS NVARCHAR)+'] VARCHAR(10)'
EXEC SP_EXECUTESQL @qry
SET @colcount = @colcount+1
SET @qry = ''
SET @qry = 'UPDATE #LDAlg SET ['+ CAST(@lenb2+1-@lenb AS NVARCHAR) + '] = (SELECT SUBSTRING('''+@b+''', '+CAST(@lenb2+1-@lenb AS NVARCHAR) +',1)) WHERE lbl0 = ''R1'''
EXEC SP_EXECUTESQL @qry
SET @qry = ''
SET @qry = 'UPDATE #LDAlg SET ['+ CAST(@lenb2+1-@lenb AS NVARCHAR) + '] = (SELECT ''' +CAST(@lenb2+1-@lenb AS NVARCHAR) +''') WHERE lbl0 = ''R2'''
EXEC SP_EXECUTESQL @qry
SET @lenb = @lenb - 1
END
--SET @lenb = @lenb2

WHILE(@lena > 0)
BEGIN
SET @qry = ''
SET @qry = 'INSERT #LDAlg (lbl1, [0]) SELECT SUBSTRING('''+@a+''', '+CAST(@lena2+1-@lena AS NVARCHAR) +',1),'+CAST(@lena2+1-@lena AS NVARCHAR)
EXEC SP_EXECUTESQL @qry
SET @lena = @lena-1
SET @lblcntr = @lblcntr +1
END

UPDATE #LDAlg SET [0] = 0 WHERE lbl0 = 'R2'

ALTER TABLE #LDAlg DROP COLUMN lbl0

SELECT @rowcount = (SELECT COUNT(*) FROM #LDAlg WHERE [0] > 0)
SET @rowcount2 = 1

CREATE TABLE #tbl(BValue NVARCHAR(10),ApexValue INT, HorizValue INT, VertValue INT)

DECLARE @apex VARCHAR(10) = 0, @horiz VARCHAR(10) = 1, @verti VARCHAR(10) =1, @aval VARCHAR(10), @bval VARCHAR(10)
DECLARE @valuecomp VARCHAR(10) = 0
--DECLARE @horizcolname INT = 1
WHILE (@rowcount2 <= @rowcount)
BEGIN
--PRINT 'Row'+CAST(@rowcount2 AS VARCHAR)
SET @colcount2 = 1
WHILE (@colcount2 <= @colcount)
BEGIN
--PRINT 'Column '+ CAST(@colcount2 AS VARCHAR)
SET @aval = (SELECT lbl1 FROM #LDAlg WHERE [0] = @rowcount2)

SET @qry = ''
SET @qry = 'SELECT ['+CAST(@colcount2 AS VARCHAR)+'] FROM #LDAlg WHERE [0] IS NULL'
INSERT INTO #tbl (BValue)
EXEC SP_EXECUTESQL @qry

SET @qry = ''
SET @qry = 'UPDATE #tbl SET ApexValue = (SELECT ['+CAST(@colcount2-1 AS VARCHAR)+'] FROM #LDAlg WHERE [0] = '+CAST(@rowcount2-1 AS VARCHAR)+')'
EXEC SP_EXECUTESQL @qry

SET @qry = ''
SET @qry = 'UPDATE #tbl SET HorizValue = (SELECT ['+CAST(@colcount2 AS VARCHAR)+'] FROM #LDAlg WHERE [0] = '+CAST(@rowcount2-1 AS VARCHAR)+')'
EXEC SP_EXECUTESQL @qry


SET @qry = ''
SET @qry = 'UPDATE #tbl SET VertValue = (SELECT ['+CAST(@colcount2-1 AS VARCHAR)+'] FROM #LDAlg WHERE [0] = '+CAST(@rowcount2 AS VARCHAR)+')'
EXEC SP_EXECUTESQL @qry

SELECT @bval = BValue, @apex = ApexValue, @horiz = HorizValue, @verti = VertValue FROM #tbl
DELETE FROM #tbl

SET @valuecomp = (SELECT MIN(Val) FROM ( SELECT @apex Val UNION ALL SELECT @horiz UNION ALL SELECT @verti) q )

SET @qry = ''
SET @qry = 'UPDATE #LDAlg SET ['+CAST(@colcount2 AS VARCHAR)+']= CASE WHEN '''+@aval+''' = '''+@bval+''' THEN '+@valuecomp+' ELSE '+CAST(@valuecomp + 1 AS VARCHAR)+' END WHERE [0] = '+CAST(@rowcount2 AS VARCHAR)
EXEC SP_EXECUTESQL @qry

SET @colcount2 = @colcount2 + 1
END
SET @rowcount2 = @rowcount2 + 1
END
--SELECT * FROM #LDAlg
SET @qry = ''
SET @qry = 'SELECT ['+CAST(@colcount AS VARCHAR)+'] AS [Levenshtein Distance] FROM #LDAlg WHERE [0] = '+CAST(@rowcount2 - 1 AS VARCHAR)
EXEC SP_EXECUTESQL @qry

DROP TABLE #LDAlg
DROP TABLE #tbl
GO