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

Меня интересует алгоритм в T-SQL, вычисляющий расстояние Левенштейна.

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

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

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

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

 -- ============================================= -- Computes and returns the Levenshtein edit distance between two strings, ie 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 

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

  • один с июня 2005 года и
  • другой обновленный с мая 2006 года

Это младший из 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 

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 

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

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

Здесь вы можете найти пример 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, @[email protected], 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, @[email protected]+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') 

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

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

расстояние для 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; 

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

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

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

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

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

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

  • Использование курсора с динамическим SQL в хранимой процедуре
  • Isoweek в SQL Server 2005
  • Разделение TSQL на ноль встречается, несмотря на отсутствие столбцов, содержащих 0
  • Каков хороший способ обрезать все символы пробелов из строки в T-SQL без UDF и без CLR?
  • Выполнение хранимой процедуры SQL и обработка результатов
  • Как сделать SQL как% в Linq?
  • Использование псевдонимов в разделе «Где» или «Альтернативный вариант»?
  • Как проверить, существует ли столбец в таблице SQL Server?
  • T-SQL CASE: как указать WHEN NULL
  • Функция PadLeft в T-SQL
  • Создание таблицы HTML с SQL FOR XML
  • Давайте будем гением компьютера.