T-SQL中的Levenshtein距离
我对T-SQL计算Levenshtein距离的算法感兴趣。
回答 4
Stack Overflow用户
发布于 2009-02-18 11:48:27
在SQL Server2005和更高版本中，您可以用任何.NET语言编写存储过程：Using CLR Integration in SQL Server 2005。这样一来，编写一个计算Levenstein distance的过程应该不难。
一个简单的Hello，World！摘自帮助：
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!";
}
}然后在SQL Server中运行以下命令：
CREATE ASSEMBLY helloworld from 'c:\helloworld.dll' WITH PERMISSION_SET = SAFE
CREATE PROCEDURE hello
@i nchar(25) OUTPUT
AS
EXTERNAL NAME helloworld.HelloWorldProc.HelloWorld现在你可以测试运行它了：
DECLARE @J nchar(25)
EXEC hello @J out
PRINT @J希望这能有所帮助。
Stack Overflow用户
发布于 2011-07-11 14:50:39
您可以使用Levenshtein距离算法来比较字符串
在这里，您可以在http://www.kodyaz.com/articles/fuzzy-string-matching-using-levenshtein-distance-sql-server.aspx找到一个T-SQL示例
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( Joseph Gama开发的函数)
用法：
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')该算法只返回stpe计数，通过在一步中替换不同的字符来将一个字符串更改为另一个字符串
Stack Overflow用户
发布于 2018-01-05 23:43:08
在TSQL中，比较两个项的最好、最快的方法是使用SELECT语句连接索引列上的表。因此，如果您想从RDBMS引擎的优势中获益，这就是我建议实现编辑距离的方式。TSQL循环也可以工作，但对于大容量比较，Levenstein距离计算在其他语言中比在TSQL中更快。
我已经在几个系统中实现了编辑距离，使用了一系列专门针对临时表的连接。它需要一些繁重的预处理步骤-准备临时表-但它在处理大量比较时非常有效。
简而言之:预处理包括创建、填充和索引临时表。第一个包含引用ids、一个字母列和一个charindex列。这个表是通过运行一系列insert查询(使用SELECT SUBSTRING)将每个单词拆分成字母来填充的(使用SELECT SUBSTRING)，以创建与源列表中的单词具有字母一样多的行(我知道，这是很多的行，但SQL server可以处理数十亿行)。然后创建具有2个字母列的第二个表，以及具有3个字母列的另一个表，依此类推。最终结果是一系列表，其中包含每个单词的引用in和子字符串，以及它们在单词中位置的引用。
一旦完成，整个游戏就是复制这些表，并通过计算匹配数量的select查询将它们连接到一个组中。这为每对可能的单词创建了一系列度量，然后将这些度量重新聚合为每对单词的单个Levenstein距离。
从技术上讲，这与Levenstein距离(或其变体)的大多数其他实现非常不同，因此您需要深入了解Levenstein距离是如何工作的，以及为什么它是这样设计的。也要研究替代方法，因为使用这种方法，您最终会得到一系列底层指标，这些指标可以帮助同时计算编辑距离的许多变体，从而为您提供有趣的机器学习潜在改进。
本页前面的答案已经提到的另一点是:尝试尽可能多地进行预处理，以消除不需要距离测量的对。例如，应该排除没有单个字母的一对两个单词，因为编辑距离可以从字符串的长度获得。或者不测量同一单词的两个副本之间的距离，因为它本质上是0。或者在进行测量之前删除重复项，如果您的单词列表来自长文本，则相同的单词可能会多次出现，因此只测量一次距离将节省处理时间，等等。
https://stackoverflow.com/questions/560709
复制相似问题
腾讯云开发者
