SQL中两个字符串的公共子串

Question

我需要在 SQL 中找到两个字符串的公共子字符串（不带空格）。

询问：

select *
from tbl as a, tbl as b
where a.str <> b.str

样本数据：

str1      | str2      | max substring without spaces
----------+-----------+-----------------------------
aabcdfbas | rikcdfva  | cdf
aaab akuc | aaabir a  | aaab
ab akuc   | ab atr    | ab

Answer 1

我不同意那些说 SQL 不是完成这项工作的工具的人的观点。在有人能向我展示比我用任何编程语言的解决方案更快的方法之前，我会断言 SQL（以基于集合的、无副作用编写、仅使用不可变变量）是这项工作的唯一工具（当处理varchar(8000)-或 nvarchar(4000))。以下解决方案适用于 varchar(8000)。

1. 正确索引的计数（数字）表。

-- (1) build and populate a persisted (numbers) tally 
IF OBJECT_ID('dbo.tally') IS NOT NULL DROP TABLE dbo.tally;
CREATE TABLE dbo.tally (n int not null);

WITH DummyRows(V) AS(SELECT 1 FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) t(N))
INSERT dbo.tally
SELECT TOP (8000) ROW_NUMBER() OVER (ORDER BY (SELECT 1))
FROM DummyRows a CROSS JOIN DummyRows b CROSS JOIN DummyRows c CROSS JOIN DummyRows d;

-- (2) Add Required constraints (and indexes) for performance
ALTER TABLE dbo.tally 
ADD CONSTRAINT pk_tally PRIMARY KEY CLUSTERED(N) WITH FILLFACTOR = 100;

ALTER TABLE dbo.tally 
ADD CONSTRAINT uq_tally UNIQUE NONCLUSTERED(N);

请注意，统计表功能的执行效果不佳。

2. 使用我们的计数表返回一个字符串的所有可能的子字符串

以“abcd”为例，让我们获取它的所有子字符串。请注意我的评论。

DECLARE @s1 varchar(8000) = 'abcd';

SELECT
  position  = t.N,
  tokenSize = x.N,
  string    = substring(@s1, t.N, x.N)  
FROM       dbo.tally t -- token position
CROSS JOIN dbo.tally x -- token length
WHERE t.N <=  len(@s1) -- all positions
AND   x.N <=  len(@s1) -- all lengths
AND   len(@s1) - t.N - (x.N-1) >= 0 -- filter unessesary rows [e.g.substring('abcd',3,2)]

这返回

position    tokenSize   string
----------- ----------- -------
1           1           a
2           1           b
3           1           c
4           1           d
1           2           ab
2           2           bc
3           2           cd
1           3           abc
2           3           bcd
1           4           abcd

3. dbo.getshortstring8K

这个功能是做什么用的？第一个重大优化。我们将把两个字符串中较短的一个分解成每个可能的子字符串，然后看看它是否存在于较长的字符串中。如果有两个字符串（S1 和 S2），并且 S1 比 S2 长，我们知道 S1 中比 S2 长的子串都不会是 S2 的子串。这就是 dbo.getshortstring 的目的：确保我们不执行任何不必要的子字符串比较。稍后这会变得更有意义。

这非常重要，因为可以使用三角形数字函数来计算字符串中子字符串的数量。以N为字符串的长度（字符数），子字符串的数量可以计算为N*(N+1)/2。例如“abc”有6个子串：3*(3+1)/2 = 6; a、b、c、ab、bc、abc。如果我们将“abc”与“abcdefgh”进行比较，则不需要检查“abcd”是否是“abc”的子字符串。

将“abcdefgh”（长度=8）分解为所有可能的子字符串需要 8*(8+1)/2 = 36 次操作（ “abc”需要6 次操作）。

IF OBJECT_ID('dbo.getshortstring8k') IS NOT NULL DROP FUNCTION dbo.getshortstring8k;
GO
CREATE FUNCTION dbo.getshortstring8k(@s1 varchar(8000), @s2 varchar(8000))
RETURNS TABLE WITH SCHEMABINDING AS RETURN 
SELECT s1 = CASE WHEN LEN(@s1) < LEN(@s2) THEN @s1 ELSE @s2 END,
       s2 = CASE WHEN LEN(@s1) < LEN(@s2) THEN @s2 ELSE @s1 END;

4. 查找较长字符串中存在的较短字符串的所有子环：

DECLARE @s1 varchar(8000) = 'bcdabc', @s2 varchar(8000) = 'abcd';

SELECT
  s.s1, -- test to make sure s.s1 is the shorter of the two strings
  position  = t.N,
  tokenSize = x.N,
  string    = substring(s.s1, t.N, x.N)
FROM dbo.getshortstring8k(@s1, @s2) s --<< get the shorter string
CROSS JOIN dbo.tally t  
CROSS JOIN dbo.tally x
WHERE t.N between 1 and len(s.s1)
AND   x.N between 1 and len(s.s1)
AND   len(s.s1) - t.N - (x.N-1) >= 0
AND   charindex(substring(s.s1, t.N, x.N), s.s2) > 0;

5. 仅检索最长的公共子串

这是简单的部分。我们只需添加TOP (1) WITH TIES到我们的SELECT声明中就可以了。这里，最长公共子串是“bc”和“xx”

DECLARE @s1 varchar(8000) = 'xxabcxx', @s2 varchar(8000) = 'bcdxx';

SELECT TOP (1) WITH TIES 
  position  = t.N,
  tokenSize = x.N,
  string    = substring(s.s1, t.N, x.N)
FROM dbo.getshortstring8k(@s1, @s2) s
CROSS JOIN dbo.tally t  
CROSS JOIN dbo.tally x
WHERE t.N between 1 and len(s.s1)
AND   x.N between 1 and len(s.s1)
AND   len(s.s1) - t.N - (x.N-1) >= 0
AND   charindex(substring(s.s1, t.N, x.N), s.s2) > 0
ORDER BY x.N DESC;

6. 将此逻辑应用到您的表中

使用 APPLY，我们将变量 @s1 和 @s2 替换为 t.str1 和 t.str2。我添加了一个过滤器来排除包含空格的匹配项（请参阅我的评论）...然后我们就出发了：

-- easily consumbable sample data
DECLARE @yourtable TABLE (str1 varchar(8000), str2 varchar(8000));
INSERT @yourtable 
VALUES ('aabcdfbas','rikcdfva'),('aaab akuc','aaabir a'),('ab akuc','ab atr');

SELECT str1, str2,  [max substring without spaces] = string
FROM @yourtable t
CROSS APPLY 
(
    SELECT TOP (1) WITH TIES 
      position  = t.N,
      tokenSize = x.N,
      string    = substring(s.s1, t.N, x.N)
    FROM dbo.getshortstring8k(t.str1, t.str2) s -- @s1 & @s2 replaced with str1 & str2 
    CROSS JOIN dbo.tally t  
    CROSS JOIN dbo.tally x
    WHERE t.N between 1 and len(s.s1)
    AND   x.N between 1 and len(s.s1)
    AND   len(s.s1) - t.N - (x.N-1) >= 0
    AND   charindex(substring(s.s1, t.N, x.N), s.s2) > 0
    AND   charindex(' ',substring(s.s1, t.N, x.N)) = 0 -- exclude substrings with spaces
    ORDER BY x.N DESC
) lcss;

结果：

str1        str2      max substring without spaces
----------- --------- ------------------------------
aabcdfbas   rikcdfva  cdf
aaab akuc   aaabir a  aaab
ab akuc     ab atr    ab

以及执行计划：

...没有排序或不必要的操作。只是速度。对于较长的字符串（例如 50 个字符以上），我有一种更快的技术，您可以在此处阅读。