Levenshtein distance en T-SQL

Question

Je suis intéressé par l’algorithme dans le calcul T-SQL de la distance de Levenshtein.

Answer 1

Arnold Fribble propose celui-ci:

 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
 

Answer 2

IIRC, avec SQL Server 2005 et versions ultérieures, vous pouvez écrire des procédures stockées en toute .NET langue: à l'Aide de CLR Intégration dans SQL Server 2005. Avec qu'il ne devrait pas être trop difficile d'écrire une procédure pour le calcul de la distance de Levenstein.

Un simple Bonjour tout le Monde! extrait de l'aide:

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

Puis dans votre SQL Server, exécutez la commande suivante:

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

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

Et maintenant, vous pouvez tester l'exécuter:

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

Espérons que cette aide.

Answer 3

Vous pouvez utiliser l'algorithme de distance Levenshtein pour comparer des chaînes

Vous trouverez ici un exemple T-SQL à l' adresse http://www.kodyaz.com/articles/fuzzy-string-matching-using-levenshtein-distance-sql-server.aspx

L'algorithme renvoie simplement le nombre de stpe pour changer une chaîne en une autre en remplaçant un caractère différent à une étape.

Answer 4

Pensez à utiliser la procédure stockée CLR si celles-ci sont disponibles. Si non, voir ceci et cela .