Jarak Levenshtein di T-SQL

Saya tertarik dengan algoritma dalam T-SQL yang menghitung jarak Levenshtein.

Saya menerapkan fungsi jarak edit Levenshtein standar di TSQL dengan beberapa pengoptimalan yang meningkatkan kecepatan dibandingkan versi lain yang saya ketahui. Dalam kasus di mana dua string memiliki karakter yang sama di awal (awalan bersama), karakter yang sama di akhir (sufiks bersama), dan saat string besar dan jarak edit maksimal disediakan, peningkatan kecepatan menjadi signifikan. Misalnya, ketika input adalah dua string 4000 karakter yang sangat mirip, dan jarak edit maksimal 2 ditentukan, ini hampir tiga kali lipat lebih cepat daripadaedit_distance_withinberfungsi dalam jawaban yang diterima, mengembalikan jawaban dalam 0,073 detik (73 milidetik) vs 55 detik. Ini juga hemat memori, menggunakan ruang yang sama dengan yang lebih besar dari dua string input ditambah beberapa ruang konstan. Ia menggunakan "array" nvarchar tunggal yang mewakili kolom, dan melakukan semua perhitungan di tempat itu, ditambah beberapa variabel int pembantu.

Optimasi:

• melewatkan pemrosesan prefiks dan / atau sufiks bersama
• pengembalian awal jika string yang lebih besar dimulai atau diakhiri dengan seluruh string yang lebih kecil
• pengembalian awal jika perbedaan ukuran menjamin jarak maksimal akan terlampaui
• hanya menggunakan satu array yang mewakili kolom dalam matriks (diimplementasikan sebagai nvarchar)
• ketika jarak maksimum diberikan, kompleksitas waktu berubah dari (len1 * len2) menjadi (min (len1, len2)) yaitu linier
• ketika jarak maksimum diberikan, pengembalian awal segera setelah batas jarak maksimum diketahui tidak dapat dicapai

Berikut adalah kodenya (diperbarui 1/20/2014 untuk lebih mempercepatnya):

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

Seperti yang disebutkan di komentar fungsi ini, sensitivitas huruf besar-kecil dari perbandingan karakter akan mengikuti pemeriksaan yang berlaku. Secara default, pemeriksaan SQL Server adalah salah satu yang akan menghasilkan perbandingan tidak peka huruf besar / kecil. Salah satu cara untuk mengubah fungsi ini agar selalu peka huruf besar / kecil adalah dengan menambahkan pemeriksaan khusus ke dua tempat di mana string dibandingkan. Namun, saya belum menguji ini secara menyeluruh, terutama untuk efek samping ketika database menggunakan pemeriksaan non-default. Berikut adalah cara mengubah dua baris untuk memaksa perbandingan case-sensitive:

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

dan

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

Arnold Fribble memiliki dua proposal di sqlteam.com/forums

• satu dari Juni 2005 dan
• satu lagi diperbarui dari Mei 2006

Ini yang lebih muda dari tahun 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, dengan SQL Server 2005 dan yang lebih baru, Anda dapat menulis prosedur yang disimpan dalam bahasa .NET apa pun: Menggunakan Integrasi CLR di SQL Server 2005 . Dengan itu seharusnya tidak sulit untuk menulis prosedur untuk menghitung jarak Levenstein .

Halo, Dunia! diekstrak dari bantuan:

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

Kemudian di SQL Server Anda, jalankan perintah berikut:

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

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

Dan sekarang Anda dapat mengujinya:

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

Semoga ini membantu.

Anda dapat menggunakan Algoritma Jarak Levenshtein untuk membandingkan string

Di sini Anda dapat menemukan contoh T-SQL di 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

(Fungsi dikembangkan oleh Joseph Gama)

Penggunaan:

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

Algoritme hanya mengembalikan jumlah stpe untuk mengubah satu string menjadi string lain dengan mengganti karakter yang berbeda pada satu langkah

Saya juga mencari contoh kode untuk algoritma Levenshtein, dan dengan senang hati menemukannya di sini. Tentu saja saya ingin memahami cara kerja algoritme dan saya bermain-main sedikit dengan salah satu contoh di atas yang saya mainkan sedikit yang diposting oleh Veve . Untuk mendapatkan pemahaman yang lebih baik tentang kode, saya membuat EXCEL dengan Matrix.

jarak untuk FUZZY dibandingkan dengan FUZY

Gambar mengatakan lebih dari 1000 kata.

Dengan EXCEL ini saya menemukan bahwa ada potensi untuk pengoptimalan kinerja tambahan. Semua nilai di area merah kanan atas tidak perlu dihitung. Nilai setiap sel darah merah menghasilkan nilai sel kiri ditambah 1. Hal ini karena string kedua akan selalu lebih panjang di area tersebut daripada yang pertama, yang menambah jarak dengan nilai 1 untuk setiap karakter.

Anda dapat merefleksikannya dengan menggunakan pernyataan IF @j <= @i dan meningkatkan nilai @i Sebelum pernyataan ini.

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;

Di TSQL, cara terbaik dan tercepat untuk membandingkan dua item adalah pernyataan SELECT yang menggabungkan tabel pada kolom yang diindeks. Oleh karena itu, inilah cara saya menyarankan untuk menerapkan jarak pengeditan jika Anda ingin memanfaatkan keunggulan mesin RDBMS. TSQL Loops juga akan berfungsi, tetapi penghitungan jarak Levenstein akan lebih cepat dalam bahasa lain daripada di TSQL untuk perbandingan volume besar.

Saya telah menerapkan jarak pengeditan di beberapa sistem menggunakan serangkaian Gabungan terhadap tabel sementara yang dirancang hanya untuk tujuan itu. Ini membutuhkan beberapa langkah pra-pemrosesan yang berat - persiapan tabel sementara - tetapi ini bekerja sangat baik dengan sejumlah besar perbandingan.

Singkatnya: pra-pemrosesan terdiri dari membuat, mengisi, dan mengindeks tabel temp. Yang pertama berisi id referensi, kolom satu huruf dan kolom charindex. Tabel ini diisi dengan menjalankan serangkaian kueri sisipkan yang membagi setiap kata menjadi huruf (menggunakan SELECT SUBSTRING) untuk membuat baris sebanyak kata dalam daftar sumber memiliki huruf (saya tahu, itu banyak baris tetapi server SQL dapat menangani miliaran baris). Kemudian buat tabel kedua dengan kolom 2 huruf, tabel lain dengan kolom 3 huruf, dll. Hasil akhirnya berupa rangkaian tabel yang berisi id referensi dan substring dari masing-masing kata, serta referensi posisinya. di kata.

Setelah ini selesai, seluruh permainan adalah tentang menduplikasi tabel ini dan menggabungkannya dengan duplikatnya dalam kueri pemilihan GROUP BY yang menghitung jumlah kecocokan. Ini menciptakan serangkaian ukuran untuk setiap kemungkinan pasangan kata, yang kemudian digabungkan kembali menjadi satu jarak Levenstein per pasangan kata.

Secara teknis, ini sangat berbeda dari kebanyakan implementasi jarak Levenstein lainnya (atau variannya) sehingga Anda perlu memahami secara mendalam bagaimana jarak Levenstein bekerja dan mengapa itu dirancang sebagaimana adanya. Selidiki alternatifnya juga karena dengan metode itu Anda akan mendapatkan serangkaian metrik yang mendasari yang dapat membantu menghitung banyak varian jarak pengeditan pada saat yang sama, memberi Anda peningkatan potensial pembelajaran mesin yang menarik.

Hal lain yang sudah disebutkan oleh jawaban sebelumnya di halaman ini: coba lakukan pra proses sebanyak mungkin untuk menghilangkan pasangan yang tidak memerlukan pengukuran jarak. Misalnya sepasang dua kata yang tidak memiliki satu huruf pun yang sama harus dikecualikan, karena jarak pengeditan dapat diperoleh dari panjang string. Atau jangan mengukur jarak antara dua salinan dari kata yang sama, karena sifatnya 0. Atau hapus duplikat sebelum melakukan pengukuran, jika daftar kata Anda berasal dari teks yang panjang kemungkinan besar kata yang sama akan muncul lebih dari satu kali, jadi mengukur jarak hanya sekali akan menghemat waktu pemrosesan, dll.