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

Ответы:

100

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

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

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

Вот код (обновлен 20.01.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).
-- 
-- 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
топор - сделано с SOverflow
источник
1
Как мы можем использовать это, чтобы найти 5 самых близких строк в таблице? Я имею в виду, допустим, у меня есть таблица названий улиц с 10-метровыми рядами. Я ввожу поиск по названию улицы, но неправильно написан 1 символ. Как я могу найти 5 самых близких совпадений с максимальной производительностью?
MonsterMMORPG
1
Кроме грубой силы (сравнение всех адресов), вы не можете. Левенштейн не из тех, кто может легко воспользоваться индексами. Если вы можете сузить количество кандидатов до меньшего подмножества с помощью чего-то, что можно проиндексировать, например, почтового индекса для адреса или фонетического кода для имен, тогда прямой Левенштейн, подобный тому, что в ответах здесь, может быть применен к подмножество. Чтобы применить ко всему большому набору, вам нужно будет обратиться к чему-то вроде автоматов Левенштейна, но реализация этого в SQL выходит за рамки вопроса SO, на который здесь дан ответ.
топорик - сделано с SOverflow
@MonsterMMORPG теоретически можно было бы сделать наоборот и вычислить все возможные перестановки для заданного расстояния Левенштейна. Или вы можете попробовать и посмотреть, составляют ли слова в ваших адресах список, достаточно короткий, чтобы быть полезным (возможно, игнорируя слова, которые встречаются редко).
TheConstructor
@MonsterMMORPG - уже поздно, но я подумал, что добавлю ответ получше. Если вы знаете минимальное количество разрешенных правок, вы можете использовать метод симметричного удаления, как это было сделано в проекте symspell на github. Вы можете сохранить небольшое подмножество перестановок только удалений, а затем искать любую из небольшого набора перестановок удаления в строке поиска. В возвращенном наборе (который был бы небольшим, если бы вы разрешили только 1 или 2 максимальных расстояния редактирования), вы затем выполняете полный levenshtein calc. Но это должно быть намного меньше, чем делать это на всех струнах.
топор - сделано с SOverflow
1
@DaveCousineau - как упоминалось в комментариях к функциям, при сравнении строк используется чувствительность к регистру для действующей сортировки SQL Server. По умолчанию это обычно означает нечувствительность к регистру. См. Правку только что добавленного мной сообщения. Реализация Fribble в другом ответе ведет себя аналогичным образом в отношении сопоставления.
топор - сделано с SOverflow
58

У Арнольда Фриббла было два предложения на sqlteam.com/forums

Это младший из 2006 года:

SET QUOTED_IDENTIFIER ON 
GO
SET ANSI_NULLS ON 
GO

CREATE FUNCTION edit_distance_within(@s nvarchar(4000), @t nvarchar(4000), @d int)
RETURNS int
AS
BEGIN
  DECLARE @sl int, @tl int, @i int, @j int, @sc nchar, @c int, @c1 int,
    @cv0 nvarchar(4000), @cv1 nvarchar(4000), @cmin int
  SELECT @sl = LEN(@s), @tl = LEN(@t), @cv1 = '', @j = 1, @i = 1, @c = 0
  WHILE @j <= @tl
    SELECT @cv1 = @cv1 + NCHAR(@j), @j = @j + 1
  WHILE @i <= @sl
  BEGIN
    SELECT @sc = SUBSTRING(@s, @i, 1), @c1 = @i, @c = @i, @cv0 = '', @j = 1, @cmin = 4000
    WHILE @j <= @tl
    BEGIN
      SET @c = @c + 1
      SET @c1 = @c1 - CASE WHEN @sc = SUBSTRING(@t, @j, 1) THEN 1 ELSE 0 END
      IF @c > @c1 SET @c = @c1
      SET @c1 = UNICODE(SUBSTRING(@cv1, @j, 1)) + 1
      IF @c > @c1 SET @c = @c1
      IF @c < @cmin SET @cmin = @c
      SELECT @cv0 = @cv0 + NCHAR(@c), @j = @j + 1
    END
    IF @cmin > @d BREAK
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN CASE WHEN @cmin <= @d AND @c <= @d THEN @c ELSE -1 END
END
GO
Александр Прокофьев
источник
1
@Alexander, похоже, это работает, но я бы изменил имена ваших переменных на что-то более значимое. Кроме того, я бы избавился от @d, вы знаете длину двух строк в вашем вводе.
Ливен Кеерсмэкерс
2
@Lieven: Это не моя реализация, автор - Арнольд Фриббл. Параметр @d - это максимально допустимая разница между строками, после достижения которых они считаются слишком разными, и функция возвращает -1. Это добавлено, потому что алгоритм в T-SQL работает слишком медленно.
Александр Прокофьев
Вы должны проверить псевдокод алгоритма по адресу: en.wikipedia.org/wiki/Levenshtein_distance, он не сильно улучшен.
Norman H
13

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

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

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

Надеюсь это поможет.

Леандро Лопес
источник
7

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

Здесь вы можете найти пример 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')

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

Eralper
источник
К сожалению, это не распространяется на случай, когда строка
пуста
2

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

расстояние для FUZZY по сравнению с FUZY

Изображения говорят более 1000 слов.

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

Вы можете отразить это, используя оператор IF @j <= @i и увеличивая значение @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;
Маркус Белз
источник
Как написано, это не всегда дает правильные результаты. Например, входы ('jane', 'jeanne')будут возвращать расстояние 3, когда расстояние должно быть равно 2. Для того, чтобы исправить этот дополнительный код следует добавить , что свопы , @s1и , @s2если @s1имеет более короткую длину , чем @s2.
топор - сделано с SOverflow
2

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

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

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

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

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

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

JeromeE
источник