Levenshtein Abstand in T-SQL
https://stackoverflow.com/questions/560709
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich interessiere mich für Algorithmus in T-SQL Berechnung Levenshtein-Distanz.
Lösung 2
Arnold Fribble hatte zwei Vorschläge auf sqlteam.com/forums
Dies ist der jüngere von 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
Andere Tipps
implementiert ich die Standard Levenshtein Editierdistanz Funktion in TSQL mit mehreren Optimierungen, die die Geschwindigkeit über die anderen Versionen verbessert von Ich bin mir bewusst. In Fällen, in denen die beiden Strings Zeichen gemeinsam an ihrem Anfang (gemeinsam Präfix), Zeichen gemeinsam an ihrem Ende (gemeinsam Suffix) haben, und wenn die Saiten sind groß und eine max Editierdistanz vorgesehen ist, ist die Verbesserung der Geschwindigkeit signifikant. Zum Beispiel, wenn die Eingänge sind zwei sehr ähnlich 4000 Zeichenkette und ein max bearbeiten Abstand von 2 angegeben ist, ist dies fast drei Größenordnung schneller als die edit_distance_within Funktion in der akzeptierten Antwort, Rückkehr die Antwort in 0,073 Sekunden (73 Millisekunden vs) 55 Sekunden. Es ist auch eine effiziente Speicher, Raum mit gleich dem größeren der beiden Eingangs Saiten und einen konstanten Raum. Es verwendet einen einzigen nvarchar „Array“ repräsentiert eine Spalte, und führt alle Berechnungen an Ort und Stelle, dass, sowie einige Helfer int Variablen.
Optimierungen:
- springt die Verarbeitung von gemeinsamem Präfix und / oder Suffix
- frühe Rückkehr, wenn größere Zeichenfolge beginnt oder endet mit gesamter kleineren Zeichenfolge
- frühe Rückkehr, wenn Differenz in den Größen garantiert max Abstand überschritten wird
- verwendet nur eine einzige Anordnung mit einer Spalte in der Matrix, die (implementiert als nvarchar)
- , wenn ein Abstand max gegeben ist, geht von Zeitkomplexität (len1 * len2) bis (min (len1, len2)), das heißt linear
- , wenn ein max Abstand gegeben ist, kehrt früh sobald max Abstand ist bekannt, gebunden nicht erreichbar sein
Die Optimierungen werden in etwas ausführlicher beschrieben in mein Blog-Post auf Levenshtein in TSQL und einen Link dort auf eine andere Stelle mit einem ähnlichen Damerau-Levenshtein Umsetzung. Aber hier ist der Code (2014.01.20 aktualisiert es zu beschleunigen ein bisschen mehr):
-- =============================================
-- 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
Wie in den Kommentaren dieser Funktion erwähnt, wird die Groß- und Kleinschreibung der Zeichen Vergleiche der Sortierung folgen, die in Kraft ist. Standardmäßig Sortierungs SQL Server ist eine, die in Groß- und Kleinschreibung Vergleichen führen. Eine Möglichkeit, diese Funktion zu ändern, immer seine Groß- und Kleinschreibung wäre eine spezifische Zusammenstellung an die beiden Orte hinzufügen, wo Strings verglichen werden. Allerdings habe ich nicht gründlich getestet dies, vor allem für Nebenwirkungen, wenn die Datenbank einer Nicht-Standardsortierung verwendet. Diese sind, wie die beiden Linien geändert würden, um Groß- und Kleinschreibung Vergleiche zu erzwingen:
-- 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)
und
SELECT @distance =
CASE WHEN (@sChar = SUBSTRING(@t, @j, 1) COLLATE SQL_Latin1_General_Cp1_CS_AS) THEN @diag --match, no change
IIRC, mit SQL Server 2005 und später können Sie gespeicherte Prozeduren in jeder .NET-Sprache schreiben: mit der CLR-Integration in SQL Server 2005 . Damit sollte es ein Verfahren zu schreiben für die Berechnung der Levenstein Entfernung nicht schwer sein.
Ein einfaches Hallo, Welt! extrahiert aus der Hilfe:
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!";
}
}
Dann in der SQL-Server den folgenden:
CREATE ASSEMBLY helloworld from 'c:\helloworld.dll' WITH PERMISSION_SET = SAFE
CREATE PROCEDURE hello
@i nchar(25) OUTPUT
AS
EXTERNAL NAME helloworld.HelloWorldProc.HelloWorld
Und jetzt können Sie es ausführen Test:
DECLARE @J nchar(25)
EXEC hello @J out
PRINT @J
Hope, das hilft.
Sie können Levenshtein Entfernung Algorithmus verwenden Strings für den Vergleich
Hier können Sie ein T-SQL-Beispiel finden Sie bei 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
(Funktion entwickelt von Joseph Gama)
Verbrauch:
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')
Der Algorithmus gibt einfach die stpe Zählung eine Saite in andere zu ändern, indem Sie einen anderen Charakter in einem Schritt zu ersetzen
Ich war auf der Suche nach einem Codebeispiel für den Levenshtein-Algorithmus, auch, und war froh, dass es hier zu finden. Natürlich wollte ich verstehen, wie der Algorithmus funktioniert, und ich wurde um ein wenig spielen mit einer der oben genannten Beispiele, die ich um ein wenig spielte, die von Veve . Um habe ich eine EXCEL mit der Matrix zu einem besseren Verständnis des Codes zu erhalten.
Entfernung für FUZZY verglichen mit Fuzy
Bilder sagen mehr als 1000 Worte.
Mit diesem EXCEL fand ich, dass es für zusätzliches Leistungsoptimierungspotenzial war. Alle Werte in dem rechten oberen roten Bereich müssen nicht berechnet werden. Der Wert jeder roten Blutkörperchen ergibt den Wert der linken Zelle plus 1. Dies liegt daran, wird die zweite Saite länger immer in diesem Bereich als das erste, was für jedes Zeichen den Abstand um den Wert 1 erhöht.
Sie können reflektieren, dass durch die Anweisung mit IF @j <= @i und den Wert von @i Vor dieser Aussage.
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;
In TSQL die beste und schnellste Weg, um zwei Produkte zum Vergleich sind SELECT-Anweisungen, die Tabellen auf indizierte Spalten verbinden. Daher ist dies, wie ich vorschlagen, den Bearbeitungs Abstand zu implementieren, wenn Sie von den Vorteilen eines RDBMS-Engine profitieren wollen. TSQL Loops wird auch funktionieren, aber Berechnungen Levenstein Entfernung werden schneller in anderen Sprachen als in TSQL für große Volumenvergleiche.
Ich habe die Bearbeitung Entfernung in mehreren Systemen implementiert Reihe von Joins gegen temporäre Tabellen entwickelt zu diesem Zweck nur. Es erfordert einige schwere Vorverarbeitungsschritte - die Herstellung der temporären Tabellen - aber es funktioniert sehr gut mit einer großen Anzahl von Vergleichen.
In wenigen Worten: die Vorverarbeitung der Erstellung besteht, bevölkern und Indizierung Temptabellen. Der erste enthält Referenz-IDs, eine Ein-Buchstaben-Säule und eine charindex Spalte. Diese Tabelle, indem Sie eine Reihe von Insert-Abfragen bevölkert wird, die jedes Wort in Buchstaben (mit SELECT SUBSTRING) aufgeteilt, wie viele Zeilen, wie Wort in der Quellenliste zu erstellen Buchstaben haben (ich weiß, das ist eine Menge von Zeilen, aber SQL Server kann Milliarden behandeln die Zeilen). Dann wird eine zweite Tabelle mit einer 2-Buchstaben-Spalt bilden, eine anderen Tabelle mit einer 3-Buchstaben-Säule usw. Die Endergebnisse ist eine Reihe von Tabellen, die Referenz-IDs und Unterketten jedes der Worte enthalten, sowie eine der Referenz ihrer Position im Wort.
Sobald dies geschehen ist, ist das ganze Spiel über diese Tabellen duplizieren und sie gegen ihre zweifacher Ausfertigung in einer GROUP BY-Auswahlabfrage Verbindung, die die Anzahl der Spiele zählt. Dies schafft eine Reihe von Maßnahmen für jedes mögliche Paar von Worten, die dann in einen einzigen Levenstein Abstand wieder aggregiert pro Paar von Worten.
Technisch ist dies ganz anders als die meisten anderen Implementierungen der Levenstein Abstand (oder seine Varianten) so müssen Sie tief verstehen, wie die Entfernung Werke Levenstein und warum es entworfen wurde, wie es ist. Untersuchen Sie die Alternativen als auch, weil mit dieser Methode, die Sie mit einer Reihe von zugrunde liegenden Kennzahlen am Ende, die viele Varianten des Bearbeitung Abstandes zur gleichen Zeit berechnen können helfen, Sie mit interessantem Maschinenlernpotenzial Verbesserungen bieten.
Ein weiterer Punkt bereits von früheren Antworten auf dieser Seite erwähnt: versuchen, so viel zu Pre-Prozess wie möglich die Paare zu eliminieren, die Entfernungsmessung nicht benötigen. Zum Beispiel kann ein Paar von zwei Worten, die nicht ein einziger Buchstabe gemeinsam haben ausgeschlossen werden soll, weil die Bearbeitung Abstand von der Länge der Saiten erhalten werden kann. Oder nicht misst den Abstand zwischen zwei Kopien des gleichen Wortes, da es 0 von Natur aus ist. Oder Duplikate zu entfernen, bevor die Messung zu tun, wenn Ihre Liste von Worten aus einem langen Text kommt, ist es wahrscheinlich, dass die gleichen Worte mehr als einmal erscheinen, so die Entfernungsmessung nur einmal werden die Verarbeitungszeit sparen, etc.
