Расстояние Левенштейна в T-SQL

я реализовал стандартную функцию levenshtein edit distance в TSQL с несколькими оптимизациями, которые улучшают скорость по сравнению с другими версиями, о которых я знаю. В тех случаях, когда две строки имеют общие символы в начале (общий префикс), общие символы в конце (общий суффикс), а также когда строки большие и предусмотрено максимальное расстояние редактирования, улучшение скорости является значительным. Например, когда входы являются двумя очень похожими 4000 символьными строками, А максимальное расстояние редактирования 2 указано, это почти на три порядка быстрее, чем edit_distance_within функция в принятом ответе, возвращая ответ через 0,073 секунды (73 миллисекунды) против 55 секунд. Это также эффективная память, используя пространство, равное большей из двух входных строк плюс некоторое постоянное пространство. Он использует один nvarchar "массив", представляющий столбец, и делает все вычисления на месте в этом, а также некоторые вспомогательные int переменная.

оптимизация:

• пропускает обработку общего префикса и / или суффикса
• ранний возврат, если большая строка начинается или заканчивается всей меньшей строкой
• раннее возвращение, если разница в размерах гарантирует, что максимальное расстояние будет превышено
• использует только один массив, представляющий столбец в матрице (реализуется как nvarchar)
• когда задано максимальное расстояние, временная сложность переходит от (len1*len2) к (min (len1, len2)) т. е. линейный
• когда задано максимальное расстояние, раннее возвращение, как только известно, что максимальная граница расстояния не достижима

оптимизация описана чуть более подробно в мой блог о Левенштейне в TSQL и ссылка там на другой пост с аналогичной реализацией Damerau-Levenshtein. Но вот код (обновлено 1/20/2014 чтобы ускорить его немного больше):

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

IIRC, с SQL Server 2005 и более поздних версий вы можете писать хранимые процедуры на любом языке .NET:использование интеграции среды CLR в SQL Server 2005. С этим не должно быть трудно написать процедуру вычисления расстояние Левенштейна.

простой Привет, Мир! извлечено из справки:

using System;
using System.Data;
using Microsoft.SqlServer.Server;
using System.Data.SqlTypes;

public class HelloWorldProc
{
    [Microsoft.SqlServer.Server.SqlProcedure]
    public static void HelloWorld(out string text)
    {
        SqlContext.Pipe.Send("Hello world!" + Environment.NewLine);
        text = "Hello world!";
    }
}

затем в SQL Server выполните следующие действия:

CREATE ASSEMBLY helloworld from 'c:\helloworld.dll' WITH PERMISSION_SET = SAFE

CREATE PROCEDURE hello
@i nchar(25) OUTPUT
AS
EXTERNAL NAME helloworld.HelloWorldProc.HelloWorld

и теперь вы можете проверить запустить его:

DECLARE @J nchar(25)
EXEC hello @J out
PRINT @J

надеюсь, что это помогает.

Вы можете использовать алгоритм расстояния Левенштейна для сравнения строк

здесь вы можете найти пример T-SQL по адресу http://www.kodyaz.com/articles/fuzzy-string-matching-using-levenshtein-distance-sql-server.aspx

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
 DECLARE @s1_len int, @s2_len int
 DECLARE @i int, @j int, @s1_char nchar, @c int, @c_temp int
 DECLARE @cv0 varbinary(8000), @cv1 varbinary(8000)

 SELECT
  @s1_len = LEN(@s1),
  @s2_len = LEN(@s2),
  @cv1 = 0x0000,
  @j = 1, @i = 1, @c = 0

 WHILE @j <= @s2_len
  SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1

 WHILE @i <= @s1_len
 BEGIN
  SELECT
   @s1_char = SUBSTRING(@s1, @i, 1),
   @c = @i,
   @cv0 = CAST(@i AS binary(2)),
   @j = 1

  WHILE @j <= @s2_len
  BEGIN
   SET @c = @c + 1
   SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
    CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
   IF @c > @c_temp SET @c = @c_temp
   SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
   IF @c > @c_temp SET @c = @c_temp
   SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
 END

 SELECT @cv1 = @cv0, @i = @i + 1
 END

 RETURN @c
END

(функция, разработанная Джозефом Гама)

использование :

select
 dbo.edit_distance('Fuzzy String Match','fuzzy string match'),
 dbo.edit_distance('fuzzy','fuzy'),
 dbo.edit_distance('Fuzzy String Match','fuzy string match'),
 dbo.edit_distance('levenshtein distance sql','levenshtein sql server'),
 dbo.edit_distance('distance','server')

алгоритм просто возвращает счетчик stpe, чтобы изменить одну строку в другую, заменив другой символ на одном шаге

Я тоже искал пример кода для алгоритма Левенштейна и был счастлив найти его здесь. Конечно, я хотел понять, как работает алгоритм, и я немного играл с одним из приведенных выше примеров, которые я немного играл, который был опубликован Веве. Чтобы лучше понять код, я создал EXCEL с матрицей.

расстояние для нечетких по сравнению с FUZY

картинки говорят больше чем 1000 слов.

С помощью этого EXCEL я обнаружил, что существует потенциал для дополнительной оптимизации производительности. Все значения в верхней правой красной области вычислять не нужно. Значение каждой красной ячейки приводит к значению левой ячейки плюс 1. Это связано с тем, что вторая строка всегда будет длиннее в этой области, чем первая, что увеличивает расстояние на значение 1 для каждого символа.

вы можете отразить это с помощью оператора если @j и увеличение значения @i до этого заявления.

CREATE FUNCTION [dbo].[f_LevenshteinDistance](@s1 nvarchar(3999), @s2 nvarchar(3999))
    RETURNS int
    AS
    BEGIN
       DECLARE @s1_len  int;
       DECLARE @s2_len  int;
       DECLARE @i       int;
       DECLARE @j       int;
       DECLARE @s1_char nchar;
       DECLARE @c       int;
       DECLARE @c_temp  int;
       DECLARE @cv0     varbinary(8000);
       DECLARE @cv1     varbinary(8000);

       SELECT
          @s1_len = LEN(@s1),
          @s2_len = LEN(@s2),
          @cv1    = 0x0000  ,
          @j      = 1       , 
          @i      = 1       , 
          @c      = 0

       WHILE @j <= @s2_len
          SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1;

          WHILE @i <= @s1_len
             BEGIN
                SELECT
                   @s1_char = SUBSTRING(@s1, @i, 1),
                   @c       = @i                   ,
                   @cv0     = CAST(@i AS binary(2)),
                   @j       = 1;

                SET @i = @i + 1;

                WHILE @j <= @s2_len
                   BEGIN
                      SET @c = @c + 1;

                      IF @j <= @i 
                         BEGIN
                            SET @c_temp = CAST(SUBSTRING(@cv1, @j + @j - 1, 2) AS int) + CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END;
                            IF @c > @c_temp SET @c = @c_temp
                            SET @c_temp = CAST(SUBSTRING(@cv1, @j + @j + 1, 2) AS int) + 1;
                            IF @c > @c_temp SET @c = @c_temp;
                         END;
                      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1;
                   END;
                SET @cv1 = @cv0;
          END;
       RETURN @c;
    END;

в TSQL лучшим и самым быстрым способом сравнения двух элементов являются инструкции SELECT, которые объединяют таблицы в индексированных столбцах. Поэтому именно так я предлагаю реализовать расстояние редактирования, если вы хотите воспользоваться преимуществами движка RDBMS. Циклы TSQL также будут работать, но вычисления расстояния Левенштейна будут быстрее на других языках, чем в TSQL для больших сравнений объемов.

я реализовал расстояние редактирования в нескольких системах, используя серию соединений против временные таблицы, предназначенные только для этой цели. Он требует некоторых тяжелых этапов предварительной обработки-подготовки временных таблиц-но он очень хорошо работает с большим количеством сравнений.

в нескольких словах: предварительная обработка состоит из создания, заполнения и индексирования временных таблиц. Первый содержит идентификаторы ссылок, однобуквенный столбец и столбец charindex. Эта таблица заполняется путем выполнения серии запросов вставки, которые разбивают каждое слово на Буквы (с помощью SELECT Подстрока), чтобы создать столько строк, сколько слово в исходном списке имеет буквы (Я знаю, что это много строк, но SQL server может обрабатывать миллиарды строк). Затем сделайте вторую таблицу с 2-буквенным столбцом, другую таблицу с 3-буквенным столбцом и т. д. Конечные результаты-это серия таблиц, которые содержат идентификаторы ссылок и подстроки каждого слова, а также ссылку на их положение в слове.

Как только это будет сделано, вся игра заключается в дублировании этих таблиц и присоединении к ним против их дубликата в группе путем выбора запроса, который подсчитывает количество совпадений. Это создает ряд мер для каждой возможной пары слов, которые затем повторно агрегируются в одно расстояние Левенштейна на пару слов.

технически это очень отличается от большинства других реализаций расстояния Левенштейна (или его вариантов), поэтому вам нужно глубоко понять, как работает расстояние Левенштейна и почему оно было спроектировано так, как оно есть. Исследуйте альтернативы как ну, потому что с помощью этого метода вы получаете ряд базовых показателей, которые могут помочь рассчитать множество вариантов расстояния редактирования одновременно, предоставляя вам интересные улучшения потенциала машинного обучения.

еще один момент, уже упомянутый предыдущими ответами на этой странице: попробуйте предварительно обработать как можно больше, чтобы исключить пары, которые не требуют измерения расстояния. Например, пара двух слов, которые не имеют ни одной буквы В общем должны исключается, поскольку расстояние редактирования может быть получено из длины строк. Или не измерять расстояние между двумя копиями одного и того же слова, так как это 0 по природе. Или удалите дубликаты перед выполнением измерения, если ваш список слов исходит из длинного текста, вероятно, что одни и те же слова появятся более одного раза, поэтому измерение расстояния только один раз сэкономит время обработки и т. д.