Distância de Levenshtein em T-SQL

Estou interessado no algoritmo em T-SQL calculando a distância de Levenshtein.

Implementei a função de edição de distância padrão Levenshtein em TSQL com várias otimizações que aumentam a velocidade em relação às outras versões que conheço. Nos casos em que as duas strings têm caracteres em comum no início (prefixo compartilhado), caracteres em comum no final (sufixo compartilhado) e quando as strings são grandes e uma distância máxima de edição é fornecida, a melhoria na velocidade é significativa. Por exemplo, quando as entradas são duas strings de 4.000 caracteres muito semelhantes e uma distância máxima de edição de 2 é especificada, isso é quase três ordens de magnitude mais rápido que oedit_distance_withinna resposta aceita, retornando a resposta em 0,073 segundos (73 milissegundos) vs 55 segundos. Também é eficiente em termos de memória, usando espaço igual à maior das duas strings de entrada mais algum espaço constante. Ele usa uma única "matriz" nvarchar que representa uma coluna e faz todos os cálculos no local, além de algumas variáveis ​​int auxiliares.

Otimizações:

• pula o processamento de prefixo e / ou sufixo compartilhado
• retorno antecipado se a string maior começar ou terminar com string menor inteira
• retorno antecipado se a diferença nos tamanhos garantir que a distância máxima seja excedida
• usa apenas uma única matriz que representa uma coluna na matriz (implementada como nvarchar)
• quando uma distância máxima é fornecida, a complexidade do tempo vai de (len1 * len2) a (min (len1, len2)) ou seja, linear
• quando uma distância máxima é fornecida, retorno antecipado assim que o limite da distância máxima é conhecido como não alcançável

Aqui está o código (atualizado em 20/01/2014 para agilizar um pouco mais):

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

Conforme mencionado nos comentários desta função, a diferenciação de maiúsculas e minúsculas das comparações de caracteres seguirá o agrupamento em vigor. Por padrão, o agrupamento do SQL Server é aquele que resultará em comparações que não diferenciam maiúsculas de minúsculas. Uma maneira de modificar essa função para sempre fazer distinção entre maiúsculas e minúsculas seria adicionar um agrupamento específico aos dois lugares onde as strings são comparadas. No entanto, eu não testei isso completamente, especialmente para efeitos colaterais quando o banco de dados está usando um agrupamento não padrão. É assim que as duas linhas seriam alteradas para forçar comparações que diferenciam maiúsculas de minúsculas:

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

e

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

Arnold Fribble tinha duas propostas em sqlteam.com/forums

• um de junho de 2005 e
• outro atualizado de maio de 2006

Este é o mais jovem de 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, com SQL Server 2005 e posterior, você pode escrever procedimentos armazenados em qualquer linguagem .NET: Usando a integração CLR no SQL Server 2005 . Com isso, não deve ser difícil escrever um procedimento para calcular a distância de Levenstein .

Um simples Hello, World! extraído da ajuda:

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!";
    }
}

Em seguida, no seu SQL Server, execute o seguinte:

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

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

E agora você pode testá-lo:

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

Espero que isto ajude.

Você pode usar o Algoritmo de distância de Levenshtein para comparar strings

Aqui você pode encontrar um exemplo de T-SQL em 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

(Função desenvolvida por Joseph Gama)

Uso:

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')

O algoritmo simplesmente retorna a contagem de stpe para transformar uma string em outra, substituindo um caractere diferente em uma etapa

Eu também estava procurando um exemplo de código para o algoritmo de Levenshtein e fiquei feliz em encontrá-lo aqui. Claro que eu queria entender como o algoritmo está funcionando e estava brincando um pouco com um dos exemplos acima que estava brincando um pouco que foi postado por Veve . Para entender melhor o código criei um EXCEL com o Matrix.

distância para FUZZY em comparação com FUZY

As imagens dizem mais de 1000 palavras.

Com este EXCEL, descobri que havia potencial para otimização de desempenho adicional. Todos os valores na área vermelha superior direita não precisam ser calculados. O valor de cada célula vermelha resulta no valor da célula esquerda mais 1. Isso porque, a segunda string será sempre mais longa naquela área do que a primeira, o que aumenta a distância no valor de 1 para cada caractere.

Você pode refletir isso usando a declaração IF @j <= @i e aumentando o valor de @i Antes desta declaração.

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;

Em TSQL, a maneira melhor e mais rápida de comparar dois itens são as instruções SELECT que unem tabelas em colunas indexadas. Portanto, é assim que sugiro implementar a distância de edição se você quiser se beneficiar das vantagens de um motor RDBMS. Os Loops TSQL também funcionarão, mas os cálculos de distâncias de Levenstein serão mais rápidos em outras línguas do que em TSQL para comparações de grandes volumes.

Implementei a distância de edição em vários sistemas usando séries de Joins contra tabelas temporárias projetadas apenas para esse fim. Requer algumas etapas pesadas de pré-processamento - a preparação das tabelas temporárias - mas funciona muito bem com um grande número de comparações.

Em poucas palavras: o pré-processamento consiste em criar, preencher e indexar tabelas temporárias. O primeiro contém ids de referência, uma coluna de uma letra e uma coluna charindex. Esta tabela é preenchida executando uma série de consultas de inserção que dividem cada palavra em letras (usando SELECT SUBSTRING) para criar tantas linhas quanto a palavra na lista de origem tem letras (eu sei, são muitas linhas, mas o servidor SQL pode lidar com bilhões de linhas). Em seguida, faça uma segunda tabela com uma coluna de 2 letras, outra tabela com uma coluna de 3 letras, etc. O resultado final é uma série de tabelas que contêm ids de referência e substrings de cada uma das palavras, bem como a referência de sua posição na palavra.

Feito isso, todo o jogo consiste em duplicar essas tabelas e juntá-las às suas duplicatas em uma consulta de seleção GROUP BY que conta o número de partidas. Isso cria uma série de medidas para cada par de palavras possível, que são então agregadas em uma única distância de Levenstein por par de palavras.

Tecnicamente, isso é muito diferente da maioria das outras implementações da distância de Levenstein (ou suas variantes), portanto, você precisa entender profundamente como a distância de Levenstein funciona e por que foi projetada como está. Investigue as alternativas também porque, com esse método, você acaba com uma série de métricas subjacentes que podem ajudar a calcular muitas variantes da distância de edição ao mesmo tempo, fornecendo a você melhorias potenciais interessantes de aprendizado de máquina.

Outro ponto já citado nas respostas anteriores desta página: tente pré-processar o máximo possível para eliminar os pares que não requerem medição de distância. Por exemplo, um par de duas palavras que não têm uma única letra em comum deve ser excluído, porque a distância de edição pode ser obtida a partir do comprimento das strings. Ou não meça a distância entre duas cópias da mesma palavra, uma vez que é 0 por natureza. Ou remova duplicatas antes de fazer a medição, se sua lista de palavras vier de um texto longo, é provável que as mesmas palavras apareçam mais de uma vez, portanto, medir a distância apenas uma vez economizará tempo de processamento, etc.