Created
June 23, 2016 14:22
-
-
Save acazsouza/884efea3830b789cdb216d6c99fbdf5e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| -- ============================================= | |
| -- Computes and returns the Levenshtein edit distance between two strings, i.e. the | |
| -- number of insertion, deletion, and sustitution edits required to transform one | |
| -- string to the other, or NULL if @max is exceeded. Comparisons use the case- | |
| -- sensitivity configured in SQL Server (case-insensitive by default). | |
| -- http://blog.softwx.net/2014/12/optimizing-levenshtein-algorithm-in-tsql.html | |
| -- | |
| -- Based on Sten Hjelmqvist's "Fast, memory efficient" algorithm, described | |
| -- at http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm, | |
| -- with some additional optimizations. | |
| -- ============================================= | |
| CREATE FUNCTION [dbo].[Levenshtein]( | |
| @s nvarchar(4000) | |
| , @t nvarchar(4000) | |
| , @max int | |
| ) | |
| RETURNS int | |
| WITH SCHEMABINDING | |
| AS | |
| BEGIN | |
| DECLARE @distance int = 0 -- return variable | |
| , @v0 nvarchar(4000)-- running scratchpad for storing computed distances | |
| , @start int = 1 -- index (1 based) of first non-matching character between the two string | |
| , @i int, @j int -- loop counters: i for s string and j for t string | |
| , @diag int -- distance in cell diagonally above and left if we were using an m by n matrix | |
| , @left int -- distance in cell to the left if we were using an m by n matrix | |
| , @sChar nchar -- character at index i from s string | |
| , @thisJ int -- temporary storage of @j to allow SELECT combining | |
| , @jOffset int -- offset used to calculate starting value for j loop | |
| , @jEnd int -- ending value for j loop (stopping point for processing a column) | |
| -- get input string lengths including any trailing spaces (which SQL Server would otherwise ignore) | |
| , @sLen int = datalength(@s) / datalength(left(left(@s, 1) + '.', 1)) -- length of smaller string | |
| , @tLen int = datalength(@t) / datalength(left(left(@t, 1) + '.', 1)) -- length of larger string | |
| , @lenDiff int -- difference in length between the two strings | |
| -- if strings of different lengths, ensure shorter string is in s. This can result in a little | |
| -- faster speed by spending more time spinning just the inner loop during the main processing. | |
| IF (@sLen > @tLen) BEGIN | |
| SELECT @v0 = @s, @i = @sLen -- temporarily use v0 for swap | |
| SELECT @s = @t, @sLen = @tLen | |
| SELECT @t = @v0, @tLen = @i | |
| END | |
| SELECT @max = ISNULL(@max, @tLen) | |
| , @lenDiff = @tLen - @sLen | |
| IF @lenDiff > @max RETURN NULL | |
| -- suffix common to both strings can be ignored | |
| WHILE(@sLen > 0 AND SUBSTRING(@s, @sLen, 1) = SUBSTRING(@t, @tLen, 1)) | |
| SELECT @sLen = @sLen - 1, @tLen = @tLen - 1 | |
| IF (@sLen = 0) RETURN @tLen | |
| -- prefix common to both strings can be ignored | |
| WHILE (@start < @sLen AND SUBSTRING(@s, @start, 1) = SUBSTRING(@t, @start, 1)) | |
| SELECT @start = @start + 1 | |
| IF (@start > 1) BEGIN | |
| SELECT @sLen = @sLen - (@start - 1) | |
| , @tLen = @tLen - (@start - 1) | |
| -- if all of shorter string matches prefix and/or suffix of longer string, then | |
| -- edit distance is just the delete of additional characters present in longer string | |
| IF (@sLen <= 0) RETURN @tLen | |
| SELECT @s = SUBSTRING(@s, @start, @sLen) | |
| , @t = SUBSTRING(@t, @start, @tLen) | |
| END | |
| -- initialize v0 array of distances | |
| SELECT @v0 = '', @j = 1 | |
| WHILE (@j <= @tLen) BEGIN | |
| SELECT @v0 = @v0 + NCHAR(CASE WHEN @j > @max THEN @max ELSE @j END) | |
| SELECT @j = @j + 1 | |
| END | |
| SELECT @jOffset = @max - @lenDiff | |
| , @i = 1 | |
| WHILE (@i <= @sLen) BEGIN | |
| SELECT @distance = @i | |
| , @diag = @i - 1 | |
| , @sChar = SUBSTRING(@s, @i, 1) | |
| -- no need to look beyond window of upper left diagonal (@i) + @max cells | |
| -- and the lower right diagonal (@i - @lenDiff) - @max cells | |
| , @j = CASE WHEN @i <= @jOffset THEN 1 ELSE @i - @jOffset END | |
| , @jEnd = CASE WHEN @i + @max >= @tLen THEN @tLen ELSE @i + @max END | |
| WHILE (@j <= @jEnd) BEGIN | |
| -- at this point, @distance holds the previous value (the cell above if we were using an m by n matrix) | |
| SELECT @left = UNICODE(SUBSTRING(@v0, @j, 1)) | |
| , @thisJ = @j | |
| SELECT @distance = | |
| CASE WHEN (@sChar = SUBSTRING(@t, @j, 1)) THEN @diag --match, no change | |
| ELSE 1 + CASE WHEN @diag < @left AND @diag < @distance THEN @diag --substitution | |
| WHEN @left < @distance THEN @left -- insertion | |
| ELSE @distance -- deletion | |
| END END | |
| SELECT @v0 = STUFF(@v0, @thisJ, 1, NCHAR(@distance)) | |
| , @diag = @left | |
| , @j = case when (@distance > @max) AND (@thisJ = @i + @lenDiff) then @jEnd + 2 else @thisJ + 1 end | |
| END | |
| SELECT @i = CASE WHEN @j > @jEnd + 1 THEN @sLen + 1 ELSE @i + 1 END | |
| END | |
| RETURN CASE WHEN @distance <= @max THEN @distance ELSE NULL END | |
| END |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment