Distancia de Levenshtein en T-SQL

Implementé la función estándar Levenshtein edit distance en TSQL con varias optimizaciones que mejoran la velocidad sobre las otras versiones que conozco. En los casos en que las dos cadenas tienen caracteres en común al principio (prefijo compartido), caracteres en común al final (sufijo compartido), y cuando las cadenas son grandes y se proporciona una distancia máxima de edición, la mejora en la velocidad es significativa. Por ejemplo, cuando las entradas son dos cadenas de caracteres de 4000 muy similares, y un máximo editar distancia de 2 se especifica, esto es casi tres órdenes de magnitud más rápido que la función edit_distance_within en la respuesta aceptada, devolviendo la respuesta en 0.073 segundos (73 milisegundos) vs 55 segundos. También es eficiente en memoria, usando espacio igual a la mayor de las dos cadenas de entrada más un poco de espacio constante. Utiliza un único "array" nvarchar que representa una columna, y hace todos los cálculos en su lugar, además de algunas variables int de ayuda.

Optimizaciones:

• salta procesamiento de prefijo y/o sufijo compartido
• retorno anticipado si la cadena más grande comienza o termina con una cadena entera más pequeña
• retorno anticipado si la diferencia de tamaños garantiza que se excederá la distancia máxima
• utiliza solo una única matriz que representa una columna en la matriz (implementada como nvarchar)
• cuando se da una distancia máxima, la complejidad del tiempo va de (len1*len2) a(min (len1,len2)), es decir, lineal
• cuando se da una distancia máxima, el retorno temprano tan pronto como la distancia máxima se sabe que la encuadernación no es alcanzable

Las optimizaciones se describen con un poco más de detalle en mi entrada de blog sobre Levenshtein en TSQL y un enlace a otro post con una implementación similar de Damerau-Levenshtein. Pero aquí está el código (actualizado el 20/1/2014 para acelerarlo un poco más):

-- =============================================
-- 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, con SQL Server 2005 y posteriores puede escribir procedimientos almacenados en cualquier lenguaje.NET: Utilizando la integración CLR en SQL Server 2005. Con eso no debería ser difícil escribir un procedimiento para calcular distancia de Levenstein .

Un simple Hola, Mundo! extraído de la ayuda:

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

Luego en su SQL Server ejecute lo siguiente:

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

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

Y ahora puedes probar ejecutarlo:

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

Espero que esto ayude.

Puede usar el algoritmo de distancia de Levenshtein para comparar cadenas

Aquí puede encontrar un ejemplo de T-SQL en 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

(Función desarrollada 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')

El algoritmo simplemente devuelve el recuento de stpe para cambiar una cadena por otra reemplazando un carácter diferente en un paso

También estaba buscando un ejemplo de código para el algoritmo de Levenshtein, y me alegró encontrarlo aquí. Por supuesto, quería entender cómo funciona el algoritmo y estaba jugando un poco con uno de los ejemplos anteriores que estaba jugando un poco que fue publicado por Veve. Con el fin de obtener una mejor comprensión del código he creado un EXCEL con la Matriz.

Distancia para FUZZY en comparación con FUZY

Las imágenes dicen más de 1000 palabras.

Con este EXCEL encontré que había potencial para la optimización del rendimiento adicional. No es necesario calcular todos los valores en el área roja superior derecha. El valor de cada celda roja resulta en el valor de la celda izquierda más 1. Esto se debe a que, la segunda cadena siempre será más larga en esa área que la primera, lo que aumenta la distancia por el valor de 1 para cada carácter.

Puede reflejar esto usando la instrucción IF @j y aumentando la valor de @i Antes de esta declaración.

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;

En TSQL la mejor y más rápida manera de comparar dos elementos son las sentencias SELECT que unen tablas en columnas indexadas. Por lo tanto, así es como sugiero implementar la distancia de edición si desea beneficiarse de las ventajas de un motor RDBMS. Los bucles TSQL también funcionarán, pero los cálculos de distancia de Levenstein serán más rápidos en otros lenguajes que en TSQL para comparaciones de grandes volúmenes.

He implementado la distancia de edición en varios sistemas utilizando series de Joins contra temporales mesas diseñadas únicamente para ese fin. Requiere algunos pasos de preprocesamiento pesados - la preparación de las tablas temporales-pero funciona muy bien con un gran número de comparaciones.

En pocas palabras: el preprocesamiento consiste en crear, rellenar e indexar tablas temporales. El primero contiene identificadores de referencia, una columna de una letra y una columna charindex. Esta tabla se rellena ejecutando una serie de consultas de inserción que dividen cada palabra en letras (utilizando SELECCIONAR SUBCADENA) para crear tantas filas como word en la lista fuente tenga letras (lo sé, eso es un montón de filas, pero SQL server puede manejar miles de millones de filas). Luego haga una segunda tabla con una columna de 2 letras, otra tabla con una columna de 3 letras, etc. El resultado final es una serie de tablas que contienen identificadores de referencia y subcadenas de cada una de las palabras, así como la referencia de su posición en la palabra.

Una vez hecho esto, todo el juego se trata de duplicar estas mesas y unirlas contra sus duplicar en un GRUPO POR seleccionar consulta que cuenta el número de coincidencias. Esto crea una serie de medidas para cada posible par de palabras, que luego se re-agregan en una sola distancia de Levenstein por par de palabras.

Técnicamente esto es muy diferente a la mayoría de las otras implementaciones de la distancia de Levenstein (o sus variantes), por lo que debe comprender profundamente cómo funciona la distancia de Levenstein y por qué fue diseñada tal como es. Investigar las alternativas también porque con ese método termina con una serie de métricas subyacentes que pueden ayudar a calcular muchas variantes de la distancia de edición al mismo tiempo, proporcionándole interesantes mejoras potenciales de aprendizaje automático.

Otro punto ya mencionado por las respuestas anteriores en esta página: trate de preprocesar tanto como sea posible para eliminar los pares que no requieren medición de distancia. Por ejemplo, un par de dos palabras que no tienen una sola letra en común debe excluirse, porque la distancia de edición se puede obtener a partir de la longitud de las cadenas. O no medir la distancia entre dos copias de la misma palabra, ya que es 0 por naturaleza. O elimine duplicados antes de hacer la medición, si su lista de palabras proviene de un texto largo, es probable que las mismas palabras aparezcan más de una vez, por lo que medir la distancia solo una vez ahorrará tiempo de procesamiento, etc.