[tsql] T-SQL의 Levenshtein 거리

내가 알고있는 다른 버전에 비해 속도를 향상시키는 몇 가지 최적화를 통해 TSQL에서 표준 Levenshtein 편집 거리 기능을 구현했습니다. 두 문자열의 시작 부분에 공통 문자 (공유 접두사), 끝 부분에 공통 문자 (공유 접미사), 문자열이 크고 최대 편집 거리가 제공되는 경우 속도 향상이 현저합니다. 예를 들어 입력이 두 개의 매우 유사한 4000 문자열이고 최대 편집 거리가 2로 지정된 경우 이는 거의 3 배 더 빠릅니다.edit_distance_within허용 된 답변에서 함수를 사용하여 0.073 초 (73 밀리 초) 대 55 초 내에 답변을 반환합니다. 또한 두 개의 입력 문자열 중 더 큰 공간에 일정한 공간을 더한 것과 동일한 공간을 사용하여 메모리 효율적입니다. 열을 나타내는 단일 nvarchar “배열”을 사용하고 그 안에서 모든 계산과 일부 도우미 int 변수를 제자리에서 수행합니다.

최적화 :

• 공유 접두사 및 / 또는 접미사 처리를 건너 뜁니다.
• 큰 문자열이 전체 작은 문자열로 시작하거나 끝나는 경우 조기 반환
• 크기 차이가 최대 거리 초과를 보장하는 경우 조기 반환
• 행렬의 열을 나타내는 단일 배열 만 사용합니다 (nvarchar로 구현 됨).
• 최대 거리가 주어지면 시간 복잡도는 (len1 * len2)에서 (min (len1, len2))로 이동합니다. 즉, 선형
• 최대 거리가 주어지면 최대 거리 한계를 달성 할 수 없다고 알려진 즉시 조기 복귀

다음은 코드입니다 (2014 년 1 월 20 일 업데이트 됨).

-- =============================================
-- 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).
-- 
-- 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

이 함수의 주석에서 언급했듯이 문자 비교의 대소 문자 구분은 유효한 데이터 정렬을 따릅니다. 기본적으로 SQL Server의 데이터 정렬은 대 / 소문자를 구분하지 않는 비교를 수행하는 데이터 정렬입니다. 이 함수를 항상 대소 문자를 구분하도록 수정하는 한 가지 방법은 문자열이 비교되는 두 위치에 특정 데이터 정렬을 추가하는 것입니다. 그러나, 특히 데이터베이스가 기본이 아닌 데이터 정렬을 사용하는 경우 부작용에 대해 철저하게 테스트하지 않았습니다. 다음은 대소 문자 구분 비교를 강제하기 위해 두 줄을 변경하는 방법입니다.

    -- prefix common to both strings can be ignored
    WHILE (@start < @sLen AND SUBSTRING(@s, @start, 1) = SUBSTRING(@t, @start, 1) COLLATE SQL_Latin1_General_Cp1_CS_AS)

과

            SELECT @distance =
                CASE WHEN (@sChar = SUBSTRING(@t, @j, 1) COLLATE SQL_Latin1_General_Cp1_CS_AS) THEN @diag                    --match, no change