使用 LEVENSHTEIN 算法匹配字符串

Question

create table tbl1
(
    name varchar(50)
);

insert into tbl1 values ('Mircrosoft SQL Server'),
                        ('Office Microsoft');

create table tbl2
(
    name varchar(50)
);

insert into tbl2 values ('SQL Server Microsoft'),
                        ('Microsoft Office');

我想获取两个表列name之间匹配字符串的百分比。

我尝试使用 LEVENSHTEIN 算法。但是我想从给定数据中获得的结果在表之间是相同的，但顺序不同，所以我希望看到输出为 100% 匹配。

尝试过：LEVENSHTEIN

SELECT  [dbo].[GetPercentageOfTwoStringMatching](a.name , b.name) MatchedPercentage,a.name as tbl1_name,b.name as tbl2_name
FROM tbl1 a
CROSS JOIN tbl2 b 
WHERE [dbo].[GetPercentageOfTwoStringMatching](a.name , b.name) >= 0;

结果：

MatchedPercentage   tbl1_name               tbl2_name
-----------------------------------------------------------------
5                   Mircrosoft SQL Server   SQL Server Microsoft
10                  Office Microsoft        SQL Server Microsoft
15                  Mircrosoft SQL Server   Microsoft Office
13                  Office Microsoft        Microsoft Office

Answer 1

如评论中所述，这可以通过使用字符串拆分 table 值函数来实现。就我个人而言，我使用了一种基于非常高效的基于集合的计数 table 方法，该方法由 Jeff Moden 组合在一起，在我的答案的末尾。

使用此函数可以比较由 space 字符分隔的单个单词，并计算与两个值中的单词总数相比的匹配数。

但是请注意，此解决方案会忽略任何具有前导 space 的值。如果这会成为问题，请在运行此脚本之前清理您的数据或调整以处理它们:

declare @t1 table(v nvarchar(50));
declare @t2 table(v nvarchar(50));

insert into @t1 values('Microsoft SQL Server'),('Office Microsoft'),('Other values');    -- Add in some extra values, with the same number of words and some with the same number of characters
insert into @t2 values('SQL Server Microsoft'),('Microsoft Office'),('that matched'),('that didn''t'),('Other valuee');

with c as
(
    select t1.v as v1
            ,t2.v as v2
            ,len(t1.v) - len(replace(t1.v,' ','')) + 1 as NumWords  -- String Length - String Length without spaces = Number of words - 1
    from @t1 as t1
        cross join @t2 as t2    -- Cross join the two tables to get all comparisons
    where len(replace(t1.v,' ','')) = len(replace(t2.v,' ','')) -- Where the length without spaces is the same. Can't have the same words in a different order if the number of non space characters in the whole string is different
)
select c.v1
        ,c.v2
        ,c.NumWords
        ,sum(case when s1.item = s2.item then 1 else 0 end) as MatchedWords
from c
    cross apply dbo.fn_StringSplit4k(c.v1,' ',null) as s1
    cross apply dbo.fn_StringSplit4k(c.v2,' ',null) as s2
group by c.v1
        ,c.v2
        ,c.NumWords
having c.NumWords = sum(case when s1.item = s2.item then 1 else 0 end);

输出

+----------------------+----------------------+----------+--------------+
|          v1          |          v2          | NumWords | MatchedWords |
+----------------------+----------------------+----------+--------------+
| Microsoft SQL Server | SQL Server Microsoft |        3 |            3 |
| Office Microsoft     | Microsoft Office     |        2 |            2 |
+----------------------+----------------------+----------+--------------+

函数

create function dbo.fn_StringSplit4k
(
     @str nvarchar(4000) = ' '              -- String to split.
    ,@delimiter as nvarchar(1) = ','        -- Delimiting value to split on.
    ,@num as int = null                     -- Which value to return.
)
returns table
as
return
                    -- Start tally table with 10 rows.
    with n(n)   as (select 1 union all select 1 union all select 1 union all select 1 union all select 1 union all select 1 union all select 1 union all select 1 union all select 1 union all select 1)

                    -- Select the same number of rows as characters in @str as incremental row numbers.
                    -- Cross joins increase exponentially to a max possible 10,000 rows to cover largest @str length.
        ,t(t)   as (select top (select len(isnull(@str,'')) a) row_number() over (order by (select null)) from n n1,n n2,n n3,n n4)

                    -- Return the position of every value that follows the specified delimiter.
        ,s(s)   as (select 1 union all select t+1 from t where substring(isnull(@str,''),t,1) = @delimiter)

                    -- Return the start and length of every value, to use in the SUBSTRING function.
                    -- ISNULL/NULLIF combo handles the last value where there is no delimiter at the end of the string.
        ,l(s,l) as (select s,isnull(nullif(charindex(@delimiter,isnull(@str,''),s),0)-s,4000) from s)

    select rn
          ,item
    from(select row_number() over(order by s) as rn
                ,substring(@str,s,l) as item
        from l
        ) a
    where rn = @num
        or @num is null;

使用 LEVENSHTEIN 算法匹配字符串

Matching string with LEVENSHTEIN algorithm

sql-server

sql-server-2008-r2

输出

函数