Odległość Levenshteina w T-SQL

Interesuje mnie algorytm w T-SQL obliczający odległość Levenshteina.

Zaimplementowałem standardową funkcję odległości edycji Levenshteina w TSQL z kilkoma optymalizacjami, które poprawiają prędkość w stosunku do innych znanych mi wersji. W przypadkach, gdy dwa łańcuchy mają wspólne znaki na początku (wspólny prefiks), znaki wspólne na końcu (wspólny sufiks), a także gdy łańcuchy są duże i podana jest maksymalna odległość edycji, poprawa szybkości jest znacząca. Na przykład, gdy wejściowe są dwa bardzo podobne ciągi znaków po 4000 znaków i określono maksymalną odległość edycji wynoszącą 2, jest to prawie trzy rzędy wielkości szybsze niżedit_distance_withinfunkcja w zaakceptowanej odpowiedzi, zwracając odpowiedź w 0,073 sekundy (73 milisekundy) vs 55 sekund. Jest również wydajny pod względem pamięci, wykorzystując przestrzeń równą większemu z dwóch ciągów wejściowych plus pewną stałą przestrzeń. Używa pojedynczej "tablicy" nvarchar reprezentującej kolumnę i wykonuje wszystkie obliczenia na miejscu, plus kilka pomocniczych zmiennych int.

Optymalizacje:

• pomija przetwarzanie współużytkowanego prefiksu i / lub sufiksu
• wczesny powrót, jeśli większy ciąg zaczyna się lub kończy całym mniejszym ciągiem
• wczesny zwrot, jeśli różnica w rozmiarach gwarantuje przekroczenie maksymalnej odległości
• używa tylko jednej tablicy reprezentującej kolumnę w macierzy (zaimplementowana jako nvarchar)
• gdy podana jest odległość maksymalna, złożoność czasowa zmienia się od (len1 * len2) do (min (len1, len2)), tj. liniowa
• gdy podana jest maksymalna odległość, wczesny powrót, gdy tylko wiadomo, że maksymalna odległość jest niemożliwa do osiągnięcia

Oto kod (zaktualizowany 1/20/2014, aby nieco przyspieszyć):

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

Jak wspomniano w komentarzach do tej funkcji, uwzględnianie wielkości liter przy porównywaniu znaków będzie następować po zastosowanym sortowaniu. Domyślnie sortowanie w SQL Server to takie, które spowoduje porównania bez rozróżniania wielkości liter. Jednym ze sposobów zmodyfikowania tej funkcji, aby zawsze uwzględniała wielkość liter, byłoby dodanie określonego sortowania do dwóch miejsc, w których porównywane są ciągi. Jednak nie przetestowałem tego dokładnie, zwłaszcza pod kątem skutków ubocznych, gdy baza danych używa sortowania innego niż domyślne. Oto, jak te dwie linie zostałyby zmienione, aby wymusić porównania z uwzględnieniem wielkości liter:

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

i

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

Arnold Fribble miał dwie propozycje na sqlteam.com/forums

• jeden z czerwca 2005 i
• kolejny zaktualizowany z maja 2006

Oto młodszy z 2006 roku:

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, z SQL Server 2005 i nowszymi wersjami, można pisać procedury składowane w dowolnym języku .NET: Korzystanie z integracji CLR w SQL Server 2005 . Dzięki temu nie powinno być trudno napisać procedurę obliczania odległości Levensteina .

Prosty Hello, World! wyciągnięte z pomocy:

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

Następnie na serwerze SQL uruchom następujące czynności:

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

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

A teraz możesz go przetestować:

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

Mam nadzieję że to pomoże.

Możesz użyć algorytmu odległości Levenshteina do porównywania ciągów

Tutaj można znaleźć przykład T-SQL pod adresem 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

(Funkcja opracowana przez Josepha Gamę)

Stosowanie :

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

Algorytm po prostu zwraca liczbę stpe, aby zmienić jeden ciąg na inny, zastępując inny znak w jednym kroku

Szukałem też przykładu kodu dla algorytmu Levenshteina i z przyjemnością go tutaj znalazłem. Oczywiście chciałem zrozumieć, jak działa algorytm i bawiłem się trochę jednym z powyższych przykładów, trochę pobawiłem się, który został opublikowany przez Veve . Aby lepiej zrozumieć kod, stworzyłem EXCEL z Matrixem.

odległość dla FUZZY w porównaniu z FUZY

Obrazy mówią więcej niż 1000 słów.

Dzięki temu EXCELowi odkryłem, że istnieje potencjał do dodatkowej optymalizacji wydajności. Wszystkie wartości w prawym górnym, czerwonym obszarze nie muszą być obliczane. Wartość każdej czerwonej komórki daje wartość lewej komórki plus 1. Dzieje się tak, ponieważ drugi ciąg będzie zawsze dłuższy w tym obszarze niż pierwszy, co zwiększa odległość o 1 dla każdego znaku.

Można to odzwierciedlić, używając instrukcji IF @j <= @i i zwiększając wartość @i Przed tą instrukcją.

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;

W języku TSQL najlepszym i najszybszym sposobem porównania dwóch elementów są instrukcje SELECT, które łączą tabele na indeksowanych kolumnach. Dlatego w ten sposób proponuję zaimplementować odległość edycji, jeśli chcesz skorzystać z zalet silnika RDBMS. Pętle TSQL również będą działać, ale obliczenia odległości Levensteina będą szybsze w innych językach niż w TSQL dla porównań dużych wolumenów.

Zaimplementowałem odległość edycji w kilku systemach, używając serii Łączeń dla tabel tymczasowych przeznaczonych tylko do tego celu. Wymaga kilku ciężkich etapów wstępnego przetwarzania - przygotowania tymczasowych tabel - ale działa bardzo dobrze przy dużej liczbie porównań.

W kilku słowach: wstępne przetwarzanie polega na tworzeniu, wypełnianiu i indeksowaniu tabel tymczasowych. Pierwsza zawiera identyfikatory referencji, jednoliterową kolumnę i kolumnę charindex. Ta tabela jest zapełniana przez uruchomienie serii zapytań wstawiających, które dzielą każde słowo na litery (używając SELECT SUBSTRING), aby utworzyć tyle wierszy, ile słowo na liście źródłowej ma litery (wiem, to dużo wierszy, ale serwer SQL może obsłużyć miliardy rzędów). Następnie utwórz drugą tabelę z 2-literową kolumną, kolejną tabelą z 3-literową kolumną itd. Końcowe wyniki to seria tabel, które zawierają identyfikatory referencyjne i podciągi każdego słowa, a także odniesienie do ich pozycji w świecie.

Gdy to zrobisz, cała gra polega na powieleniu tych tabel i połączeniu ich z ich duplikatami w zapytaniu wybierającym GROUP BY, które zlicza liczbę dopasowań. Tworzy to serię miar dla każdej możliwej pary słów, które są następnie ponownie agregowane w jedną odległość Levensteina na parę słów.

Technicznie różni się to bardzo od większości innych implementacji odległości Levensteina (lub jej wariantów), więc musisz dogłębnie zrozumieć, jak działa odległość Levensteina i dlaczego została zaprojektowana tak, jak jest. Zbadaj również alternatywy, ponieważ dzięki tej metodzie otrzymasz szereg podstawowych wskaźników, które mogą pomóc w obliczeniu wielu wariantów odległości edycji w tym samym czasie, zapewniając interesujące potencjalne ulepszenia uczenia maszynowego.

Kolejna kwestia wspomniana już we wcześniejszych odpowiedziach na tej stronie: postaraj się jak najwięcej wstępnie przetworzyć, aby wyeliminować pary, które nie wymagają pomiaru odległości. Na przykład para dwóch słów, które nie mają ani jednej wspólnej litery, powinna zostać wykluczona, ponieważ odległość edycji można obliczyć na podstawie długości ciągów. Lub nie mierz odległości między dwiema kopiami tego samego słowa, ponieważ z natury jest ono równe 0. Lub usuń duplikaty przed wykonaniem pomiaru, jeśli lista słów pochodzi z długiego tekstu, prawdopodobnie te same słowa pojawią się więcej niż raz, więc pomiar odległości tylko raz pozwoli zaoszczędzić czas przetwarzania itp.