Меня интересует алгоритм в T-SQL, вычисляющий расстояние Левенштейна.
Расстояние Левенштейна в T-SQL
Ответ 1
У Арнольда Фрибла было два предложения по 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
Ответ 2
Я реализовал стандартную функцию расстояния редактирования Левенштейна в 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 "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
Ответ 3
IIRC, с SQL Server 2005 и более поздними версиями вы можете писать хранимые процедуры на любом языке .NET: Использование интеграции CLR в SQL Server 2005. При этом нетрудно написать процедуру вычисления Levenstein distance.
Простой 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
Надеюсь, что это поможет.
Ответ 4
Вы можете использовать алгоритм расстояния Левенштейна для сравнения строк
Здесь вы можете найти пример 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')
Алгоритм просто возвращает значение stpe, чтобы изменить одну строку на другую, заменив другой символ на один шаг
Ответ 5
Я искал пример кода для алгоритма Левенштейна и был рад найти его здесь. Конечно, я хотел понять, как работает алгоритм, и я немного поиграл с одним из вышеприведенных примеров, которые я играл немного, который был отправлен 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;
Ответ 6
В TSQL лучшим и быстрым способом сравнения двух элементов являются инструкции SELECT, которые объединяют таблицы в индексированных столбцах. Поэтому я предлагаю реализовать расстояние редактирования, если вы хотите воспользоваться преимуществами RDBMS-движка. Также будут работать циклы TSQL, но расчет расстояний Levenstein будет быстрее на других языках, чем в TSQL для сравнения больших объемов.
Я реализовал расстояние редактирования в нескольких системах, используя серию Joins для временных таблиц, предназначенных только для этой цели. Для этого требуются некоторые тяжелые стадии предварительной обработки - подготовка временных таблиц, но она очень хорошо работает с большим количеством сравнений.
В нескольких словах: предварительная обработка состоит из создания, заполнения и индексирования временных таблиц. Первый содержит ссылочные идентификаторы, столбцы с одной буквой и столбец charindex. Эта таблица заполняется запуском серии запросов вставки, которые разбивают каждое слово на буквы (используя SELECT SUBSTRING), чтобы создать столько строк, сколько слова в исходном списке имеют буквы (я знаю, что много строк, но SQL-сервер может обрабатывать миллиарды строк). Затем создайте вторую таблицу с 2-буквенным столбцом, другую таблицу с 3-буквенным столбцом и т.д. Конечные результаты представляют собой серию таблиц, которые содержат ссылочные идентификаторы и подстроки каждого слова, а также ссылку на их позицию в слове.
Как только это будет сделано, вся игра состоит в дублировании этих таблиц и объединении их с их дубликатом в запросе GROUP BY select, который подсчитывает количество совпадений. Это создает ряд мер для каждой возможной пары слов, которые затем повторно агрегируются в одно расстояние Левенштейна на пару слов.
Технически это очень отличается от большинства других реализаций расстояния Левенштейна (или его вариантов), поэтому вам нужно глубоко понять, как работает расстояние Левенштейна и почему оно было спроектировано так, как оно есть. Изучите альтернативы, а потому, что с помощью этого метода вы получите ряд базовых показателей, которые могут помочь одновременно рассчитать множество вариантов расстояния редактирования, что даст вам интересные улучшения в обучении машинного обучения.
Еще один момент, который уже упоминался в предыдущих ответах на этой странице: попробуйте предварительно обработать как можно больше, чтобы устранить пары, которые не требуют измерения расстояния. Например, пара двух слов, которые не имеют единой буквы, должна быть исключена, поскольку расстояние редактирования может быть получено из длины строк. Или не измеряйте расстояние между двумя копиями одного и того же слова, так как оно 0 по своей природе. Или удалите дубликаты перед выполнением измерения, если ваш список слов поступает из длинного текста, вполне вероятно, что одни и те же слова появятся более одного раза, поэтому измерение расстояния только один раз позволит сэкономить время обработки и т.д.
Ответ 7
Позвольте мне предисловие, сказав, что я знаю, что это ужасно. Тем не менее, я использую HIVE QL, но не знаю достаточно Java для udf... Поэтому я создал монстра andy-shtein... Это определенно не очень, но в крайнем случае, я думаю, это звучит. Как вы думаете?
DECLARE @A VARCHAR(20),@B VARCHAR(20)
SET @A = 'AAIRAA'
SET @B = 'ALASKA AIR'
SELECT
CASE WHEN RUNME = 0 THEN 0 ELSE
(SUM(CASE WHEN A13 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12+A13
WHEN A12 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11+A12
WHEN A11 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+A11
WHEN A10 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9+A10
WHEN A9 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8+A9
WHEN A8 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7+A8
WHEN A7 IS NOT NULL THEN A1+A2+A3+A4+A5+A6+A7
WHEN A6 IS NOT NULL THEN A1+A2+A3+A4+A5+A6
WHEN A5 IS NOT NULL THEN A1+A2+A3+A4+A5
WHEN A4 IS NOT NULL THEN A1+A2+A3+A4
WHEN A3 IS NOT NULL THEN A1+A2+A3
WHEN A2 IS NOT NULL THEN A1+A2
WHEN A1 IS NOT NULL THEN A1
ELSE 0 END)*1.0)/
((13-SUM(CASE WHEN A13 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A12 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A11 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A10 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A9 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A8 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A7 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A6 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A5 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A4 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A3 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A2 IS NULL THEN 1 ELSE 0 END +
CASE WHEN A1 IS NULL THEN 1 ELSE 0 END))*1.0)
END AS MATCHY
FROM (
SELECT
CASE WHEN LEN(@A) < 6 THEN 0
WHEN LEN(@B) < 6 THEN 0
ELSE 1 END AS RUNME,
CASE WHEN SUBSTRING(@A, 1, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 1, 3), '%') THEN 1 ELSE 0 END AS A1,
CASE WHEN SUBSTRING(@A, 2, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 2, 3), '%') THEN 1 ELSE 0 END AS A2,
CASE WHEN SUBSTRING(@A, 3, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 3, 3), '%') THEN 1 ELSE 0 END AS A3,
CASE WHEN SUBSTRING(@A, 4, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 4, 3), '%') THEN 1 ELSE 0 END AS A4,
CASE WHEN SUBSTRING(@A, 5, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 5, 3), '%') THEN 1 ELSE 0 END AS A5,
CASE WHEN SUBSTRING(@A, 6, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 6, 3), '%') THEN 1 ELSE 0 END AS A6,
CASE WHEN SUBSTRING(@A, 7, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 7, 3), '%') THEN 1 ELSE 0 END AS A7,
CASE WHEN SUBSTRING(@A, 8, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 8, 3), '%') THEN 1 ELSE 0 END AS A8,
CASE WHEN SUBSTRING(@A, 9, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 9, 3), '%') THEN 1 ELSE 0 END AS A9,
CASE WHEN SUBSTRING(@A, 10, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 10, 3), '%') THEN 1 ELSE 0 END AS A10,
CASE WHEN SUBSTRING(@A, 11, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 11, 3), '%') THEN 1 ELSE 0 END AS A11,
CASE WHEN SUBSTRING(@A, 12, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 12, 3), '%') THEN 1 ELSE 0 END AS A12,
CASE WHEN SUBSTRING(@A, 13, 3) ='' THEN NULL
WHEN @B LIKE CONCAT('%', SUBSTRING(@A, 13, 3), '%') THEN 1 ELSE 0 END AS A13
)SUB
GROUP BY RUNME