Saltar al contenido

Distancia de Levenshtein en T-SQL

Luego de investigar con especialistas en este tema, programadores de diversas áreas y profesores dimos con la solución a la pregunta y la dejamos plasmada en esta publicación.

Implementé la función de distancia de edición estándar de Levenshtein en TSQL con varias optimizaciones que mejoran la velocidad con respecto a las otras versiones que conozco. En los casos en que las dos cadenas tienen caracteres en común al principio (compartidos prefix), 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 4000 caracteres muy similares y se especifica una distancia máxima de edición de 2, esto es casi tres órdenes de magnitud más rápido que el edit_distance_within funcionan en la respuesta aceptada, devolviendo la respuesta en 0.073 segundos (73 milisegundos) vs 55 segundos. También es eficiente en la memoria, utilizando un espacio igual a la mayor de las dos cadenas de entrada más algo de espacio constante. Utiliza un solo nvarchar “array”que representa una columna, y hace todos los cálculos en el lugar en eso, más algunas variables int auxiliares.

Optimizaciones:

  • omite el procesamiento de compartido prefix y / o sufijo
  • devolución anticipada si es más grande string comienza o termina con todo más pequeño string
  • devolución anticipada si la diferencia de tamaños garantiza que se superará la distancia máxima
  • usa solo una array representando una columna en la matriz (implementado 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, retorno temprano tan pronto como se sepa que el límite de la distancia máxima no es alcanzable

Aquí está el código (actualizado el 20/01/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).
-- 
-- 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

Como se menciona en los comentarios de esta función, la distinción entre mayúsculas y minúsculas de las comparaciones de caracteres seguirá la intercalación que esté en efecto. De forma predeterminada, la intercalación de SQL Server es una que dará como resultado comparaciones que no distinguen entre mayúsculas y minúsculas. Una forma de modificar esta función para que siempre distinga entre mayúsculas y minúsculas sería agregar una intercalación específica a los dos lugares donde se comparan las cadenas. Sin embargo, no lo he probado a fondo, especialmente para los efectos secundarios cuando la base de datos utiliza una intercalación no predeterminada. Así es como se cambiarían las dos líneas para forzar comparaciones sensibles a mayúsculas y 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) 

y

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

Arnold Fribble tenía dos propuestas en sqlteam.com/forums

  • uno de junio de 2005 y
  • otro actualizado de mayo de 2006

Este es el más joven 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, con SQL Server 2005 y versiones 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 la distancia de Levenstein.

Un simple Hello, World! 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.

Sección de Reseñas y Valoraciones

Si te animas, puedes dejar un post acerca de qué te ha parecido esta reseña.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)


Tags :

Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *