Me interesa el algoritmo en T-SQL calculando la distancia de Levenshtein.Distancia de Levenshtein en T-SQL
Respuesta
Arnold Fribble proposes éste:
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 más tarde se puede escribir procedimientos en cualquier lenguaje .NET almacenado: Using CLR Integration in SQL Server 2005. Con eso no debería ser difícil escribir un procedimiento para calcular .
Un simple ¡Hola, mundo! extraídos 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 el 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 puede probar ejecutarlo:
DECLARE @J nchar(25)
EXEC hello @J out
PRINT @J
Espero que esto ayude.
Puede utilizar Levenshtein Distancia Algoritmo para cuerdas que comparan
Aquí se 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, @[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
(Función desarrollado por José 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 retorna ns el conteo stpe para cambiar una cadena a otra reemplazando un carácter diferente en un paso
Desafortunadamente, esto no cubre el caso en que una cadena está en blanco – Codeman
Implementé la función de distancia de edición estándar de Levenshtein en TSQL con varias optimizaciones que mejoran la velocidad respecto a las otras versiones que conozco. En los casos en que las dos cadenas tienen caracteres en común al inicio (prefijo compartido), caracteres en común en su extremo (sufijo compartido) y cuando las cadenas son grandes y se proporciona una distancia de edición máxima, 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 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 desde el punto de vista de la memoria, utilizando un espacio igual a la mayor de las dos cadenas de entrada más algún espacio constante. Utiliza una única "matriz" de nvarchar que representa una columna, y realiza todos los cálculos in situ, más algunas variables int de ayuda.
optimizaciones:
- saltos procesamiento de prefijo y/o sufijo común
- pronto regreso si grandes aperturas de cuerda o termina con toda la cadena más pequeña
- pronto regreso si diferencia de tamaños garantiza distancia máxima será superó
- usa solo una matriz que representa una columna en la matriz (implementado como nvarchar)
- cuando se da una distancia máxima, la complejidad del tiempo va desde (len1 * len2) to (min (len1, len2)) es decirlineal
- cuando se da una distancia max, pronto retorno tan pronto como la distancia max no se conoce obligado a ser alcanzable
Las optimizaciones se describen en un poco más de detalle en my blog post en Levenshtein en TSQL y un enlace allí a otra publicación con una implementación similar de Damerau-Levenshtein. Pero aquí está el código (actualizado el 20/01/2014 a 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
¡Una gran mejora en el rendimiento! – motoDrizzt
¿Cómo podemos usar esto para buscar las 5 cadenas más cercanas en una tabla? Quiero decir digamos que tengo una tabla de nombres de calles con 10m filas. Entro a la búsqueda de un nombre de calle pero 1 carácter está incorrectamente escrito. ¿Cómo puedo buscar las 5 mejores partidas más cercanas con el máximo rendimiento? – MonsterMMORPG
Además de la fuerza bruta (que compara todas las direcciones), no se puede. Levenshtein no es algo que pueda aprovechar fácilmente los índices. Si puede limitar los candidatos a un subconjunto más pequeño a través de algo que puede indexarse, como un código postal para la dirección, o un código fonético para los nombres, por ejemplo, entonces Levenshtein directamente así en las respuestas aquí puede aplicarse de manera factible al subconjunto. Para aplicar a un conjunto completo que sea grande, necesitaría ir a algo como Levenshtein Automata, pero implementarlo en SQL va más allá del alcance de la pregunta SO que se responde aquí. – hatchet
que estaba buscando un ejemplo de código para el algoritmo de Levenshtein, también, y estaba feliz de encontrar aquí. Por supuesto que 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. Para entender mejor el código, creé un EXCEL con Matrix.
distance for FUZZY compared with FUZY
imágenes dicen más de 1000 palabras.
Con este EXCEL, descubrí que existía la posibilidad de optimizar el rendimiento adicional. No es necesario calcular todos los valores en el área roja superior derecha. El valor de cada celda roja da como resultado el valor de la celda izquierda más 1. Esto se debe a que la segunda cuerda siempre será más larga en esa área que la primera, lo que aumenta la distancia en el valor de 1 para cada carácter.
Usted puede reflejar que mediante la instrucción SI @j < = @i y aumentar el 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;
Tal como está escrito, esto no siempre dará los resultados correctos. Por ejemplo, las entradas '('jane', 'jeanne')' devolverán una distancia de 3, cuando la distancia debería ser 2. Para corregir esto, se debe agregar un código adicional que cambie '@ s1' y' @ s2' si '@ s1' tiene una longitud más corta que' @ s2'. – hatchet
Permítanme prometer diciendo que sé que esto es terrible. Sin embargo, estoy usando HIVE QL y aún no sé suficiente de Java para un udf ... Así que creé el monstruo de andy-shtein ... Definitivamente no es bonito, pero en un apuro creo que es bueno. ¿Qué piensas?
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
Ese es uno de los códigos más impresionantemente horribles que haya visto, ¡y he visto un poco! – Kong
En TSQL la mejor y más rápida manera de comparar dos elementos son instrucciones SELECT que se unen a las tablas en columnas indizadas. Por lo tanto, así es como sugiero implementar la distancia de edición si desea beneficiarse de las ventajas de un motor RDBMS. TSQL Loops también funcionará, pero los cálculos de distancia de Levenstein serán más rápidos en otros idiomas que en TSQL para comparaciones de gran volumen.
He implementado la distancia de edición en varios sistemas utilizando serie de tablas temporales se une contra diseñados sólo para ese propósito. Requiere algunos pasos de preprocesamiento intensos, la preparación de tablas temporales, pero funciona muy bien con una gran cantidad de comparaciones.
En pocas palabras: el preprocesamiento consiste en crear, poblar e indexar tablas temporales. El primero contiene identificadores de referencia, una columna de una letra y una columna charindex. Esta tabla se completa ejecutando una serie de consultas insertadas que dividen cada palabra en letras (usando SELECT SUBSTRING) para crear tantas filas como palabras en la lista fuente tienen 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 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 una referencia de su posición en la palabra.
Una vez hecho esto, todo el juego consiste en duplicar estas tablas y unirlas a su duplicado en una consulta de selección GROUP BY que cuente el número de coincidencias. Esto crea una serie de medidas para cada par de palabras posibles, que luego se vuelven a agregar 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 Levenstein (o sus variantes) por lo que necesita entender profundamente cómo funciona la distancia Levenstein y por qué fue diseñada tal como es. También investigue las alternativas 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 mejoras potenciales potenciales de aprendizaje automático.
Otro punto ya mencionado por las respuestas anteriores en esta página: intente preprocesar tanto como sea posible para eliminar los pares que no requieren medición de distancia. Por ejemplo, se debe excluir un par de dos palabras que no tengan una sola letra en común, ya que la distancia de edición se puede obtener a partir de la longitud de las cadenas. O no mida 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 aparezcan las mismas palabras más de una vez, por lo que medir la distancia solo una vez ahorrará tiempo de procesamiento, etc.
- 1. Levenshtein Distancia en VBA
- 2. OCR: distancia Levenshtein ponderada
- 3. Levenshtein distancia simétrica?
- 4. Fast Levenshtein distancia en R?
- 5. distancia de Levenshtein en la expresión regular
- 6. Similitud de cadenas -> distancia de Levenshtein
- 7. Damerau-Levenshtein distancia (Editar distancia con transposición) c implementación
- 8. ¿Cómo se implementa la distancia de Levenshtein en Delphi?
- 9. Métodos basados en la distancia de Levenshtein Vs Soundex
- 10. Porcentaje de coincidencia de coincidencia con Levenshtein Coincidencia de distancia
- 11. Implementación de la distancia de Levenshtein para búsqueda mysql/fuzzy?
- 12. calculando distancia de Levenshtein usando listas de palabras
- 13. La forma más eficiente de calcular la distancia de Levenshtein
- 14. Levenshtein Algoritmo de distancia mejor que O (n * m)?
- 15. Concordancia exacta de la palabra de búsqueda posiblemente usando la distancia de Levenshtein
- 16. Determina de manera eficiente "cómo está ordenada" una lista, p. Ej. Distancia de Levenshtein
- 17. levenshtein alternative
- 18. Acelerando levenshtein/similar_text en PHP
- 19. Damerau-Levenshtein php
- 20. Transacciones anidadas en TSQL
- 21. ¿Simular enumeraciones en TSQL?
- 22. TSQL - Caso - ¿Valores en?
- 23. Cuerda distancia, transposiciones única
- 24. Algoritmo para medir la distancia entre las secuencias desordenadas
- 25. transacción tsql
- 26. ¿Inconsistencia de TSQL Round()?
- 27. Analizar texto (lematización, distancia de edición)
- 28. Comparar 5000 cadenas con PHP Levenshtein
- 29. TSQL - ISNULL en varias columnas
- 30. ¿Qué hace "%% DatabaseEx" en TSQL?
@Alexander, parece funcionar, pero cambiaría tus nombres de variable a algo más significativo. Además, me desharía de @d, ya sabes la longitud de las dos cadenas en tu entrada. –
@Lieven: No es mi implementación, el autor es Arnold Fribble. El parámetro @d es una diferencia máxima permitida entre las cadenas después de alcanzarlas, que se consideran demasiado diversas y la función devuelve -1. Se agrega porque el algoritmo en T-SQL funciona muy lentamente. –
Debería verificar el algoritmo del código psuedo en: http://en.wikipedia.org/wiki/Levenshtein_distance, no ha mejorado mucho. –