是否存在最长公共子串问题的 SQL Server 实现？

Question

是否存在最长公共子串问题的 SQL Server 实现？在 SQL Server 中检查列的所有行的解决方案？我见过将两个字符串作为输入的解决方案，但没有查看表中列的所有行的 SQL Server 解决方案。

我确实尝试了一些东西，但老实说，我认为目前有一个解决方案超出了我的脑海，因此欢迎提出任何建议。

这里没有“现实世界”问题，我只是在研究编程问题以及如何使用 SQL Server 解决这些问题。

Answer 1

这可以做到 比较容易作为 SQLCLR 用户定义聚合 (UDA)。聚合对一组行进行操作，因此您可以根据WHERE条件和可选GROUP BY（如果想要对单独的行集进行操作）对所有行或仅对一个子集进行操作。

但是，您是否应该这样做取决于您计划对结果做什么。如果这是一个一次性的项目来做一些不会重复的研究，那么最好只制作一个小的控制台应用程序来读取行并进行相应的处理。

但是，如果您确实需要在以数据库为中心的进程中使用返回值，那么 SQLCLR 应该没问题（假设您遵循“以下技巧可用于减少实现的内存使用量”中提到的两个建议）在伪代码部分。您只需要找到一种“创造性”的方式来处理被认为是最长公共子串的多个结果的情况（即，如果 2 个或更多公共子串并列“第一名”）。使用来自维基百科页面的示例（显示 2 个字符串的 2 个匹配项）：

ABAB
BABA

返回两个：

• BAB
• ABA

也许返回匹配的 XML 文档，因为它是可解析的并且可以包含任何字符串（当正确转义时）。

更新（更新，再次更新）

.NET C# 源代码可以在 Pastebin.com 上找到：

最长公共子串的 SQLCLR UDA - 源代码

对于想要在不编译的情况下使用此 UDA 的任何人，可以在 Pastebin.com 上找到安装 T-SQL 脚本（无外部 DLL）：

最长公共子串的 SQLCLR UDA - 安装程序

UDA 应该相当节省内存，因为它只存储与当前字符串和所有以前遇到的字符串匹配的子字符串。当新行调用 UDA 时，新字符串中未找到的任何子字符串都将从集合中删除。

这也是 CPU 高效的，如果在任何时候“公共”子串的数量变为零，它会设置一个标志，指示甚至没有子串是可能的，并且短循环所有未来的执行在被调用时简单地退出。如果遇到空字符串，这会立即发生。在任何这些情况下，都会返回一个空的 XML 文档（即仅根元素）。空文档的含义等同于空字符串，因为输入字符串唯一的共同点是它们都是非NULL字符串。

NULL，在我的解释中，被忽略，并不像空字符串那样表示没有可能的匹配项。

NULL在以下两种情况下返回A ：

• 所有输入都是 NULL
• 只有一个非NULL行在集合中，因此没有其他字符串可以比较，因此没有什么可以被认为是“公共的”。

我添加了第二个输入参数，用于控制返回值是最长公共子串还是所有公共子串。在返回 all 的情况下，每个“item”都会添加一个属性来指示它是否是“最长”子字符串之一：

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test1a]
FROM   (VALUES (N'ABAB'), (N'BABA')) tab(col);

返回：

<Items Merged="False">
  <Item>ABA</Item>
  <Item>BAB</Item>
</Items>

和

SELECT dbo.LongestCommonSubstring(tab.col, 1) AS [Test1b]
FROM   (VALUES (N'ABAB'), (N'BABA')) tab(col);

返回：

<Items Merged="False">
  <Item IsLongest="True">ABA</Item>
  <Item IsLongest="True">BAB</Item>
  <Item IsLongest="False">AB</Item>
  <Item IsLongest="False">BA</Item>
  <Item IsLongest="False">A</Item>
  <Item IsLongest="False">B</Item>
</Items>

此外，比较现在不区分大小写以匹配典型的校对规则。

以下是另外 16 个仅检查功能而非性能的测试用例。稍后我将发布其他测试，这些测试对多行更长的字符串进行操作。我现在故意省略了组合字符和补充字符，因为它们有点复杂。

SELECT dbo.LongestCommonSubstring(tab.col, 1) AS [Test2]
FROM   (VALUES (N'ABAB'), (N'BABA'), (N'2BAB5')) tab(col);
-- <Items><Item>BAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test3]
FROM   (VALUES (N'ABAB'), (N'BABA'), (NULL), (N'2BAB5')) tab(col);
-- <Items><Item>BAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test4]
FROM   (VALUES (NULL), (NULL), (NULL)) tab(col);
-- NULL

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test5]
FROM   (VALUES (N'ABAB'), (N'BABA'), (N''), (N'2BAB5')) tab(col);
-- <Items />

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test6]
FROM   (VALUES (N'ABAB'), (N'BABA'), (N'L'), (N'2BAB5')) tab(col);
-- <Items />

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test7]
FROM   (VALUES (N'ABAB')) tab(col);
-- NULL

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test8a-DuplicatesAcross2Rows]
FROM   (VALUES (N'ABAB'), (N'ABAB')) tab(col);
-- <Items><Item>ABAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test8b-DuplicatesAcross3Rows]
FROM   (VALUES (N'ABAB'), (N'ABAB'), (N'ABAB')) tab(col);
-- <Items><Item>ABAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test8c-DuplicatesAcross4Rows]
FROM   (VALUES (N'ABAB'), (N'ABAB'), (N'ABAB'), (N'ABAB')) tab(col);
-- <Items Merged="False"><Item>ABAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test9-DuplicatesWithinOneString]
FROM   (VALUES (N'ABAB'), (N'zABABh2348923ABABf')) tab(col);
-- <Items Merged="False"><Item>ABAB</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test10-XmlEncodableCharacters]
FROM   (VALUES (N'ABA&B'), (N'zABA&Bh2348923ABA&Bf')) tab(col);
-- <Items Merged="False"><Item>ABA&amp;B</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test11a-FinalMatchesShorterThanInitialSet]
FROM   (VALUES (N'ABCDq1234g'), (N'1234qABCDg'), (N'uiyuiuy1234qBCDg'), (N'512tttrtrtBCDdfdfgdg')) tab(col);
-- <Items Merged="False"><Item>BCD</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test11b-FinalMatchesShorterThanInitialSet]
FROM   (VALUES (N'BCDq1234g'), (N'1234qABCDg'), (N'uiyuiuy1234qBCDg'), (N'512tttrtrtBCDdfdfgdg')) tab(col);
-- <Items Merged="False"><Item>BCD</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test11c-FinalMatchesShorterThanInitialSet]
FROM   (VALUES (N'ABCDq1234g'), (N'1234qABCDg'), (N'uiyuiuy1234qBCDg'), (N'5123tttrtrtBCDdfdfgdg')) tab(col);
-- <Items Merged="False"><Item>BCD</Item><Item>123</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test11d-FinalMatchesShorterThanInitialSet]
FROM   (VALUES (N'BCDq1234g'), (N'1234qABCDg'), (N'uiyuiuy1234qBCDg'), (N'5123tttrtrtBCDdfdfgdg')) tab(col);
-- <Items Merged="False"><Item>BCD</Item><Item>123</Item></Items>

SELECT dbo.LongestCommonSubstring(tab.col, 0) AS [Test11e-FinalMatchesShorterThanInitialSet]
FROM   (VALUES (N'BCDq1234g'), (N'1234qABCDg'), (N'uiyuiuy1234qBCDg'), (N'123tttrtrtBCDdfdfgdg')) tab(col);
-- <Items Merged="False"><Item>BCD</Item><Item>123</Item></Items>


SELECT dbo.LongestCommonSubstring(tab.col, 1) AS [Test12-CaseInSensivity]
FROM   (VALUES (N'AbAB'), (N'BAbA')) tab(col);
/*
<Items Merged="False">
  <Item IsLongest="True">AbA</Item>
  <Item IsLongest="True">bAB</Item>
  <Item IsLongest="False">Ab</Item>
  <Item IsLongest="False">bA</Item>
  <Item IsLongest="False">A</Item>
  <Item IsLongest="False">b</Item>
</Items>
*/

最终更新（希望如此）

我对@MisterMagoo 的回答中提供的测试代码进行了一些小的更改，以便：a) 返回“最长”公共子字符串的关系，以及 b) 将每个字符串中的最后一个字符作为搜索的一部分。我还稍微改变了初始测试行的收集方式，以便有超过 100 万行，然后重新运行测试。结果是，T-SQL 版本用了 1 分 13 秒，而 SQLCLR UDA 只用了 12 秒（甚至可以选择返回所有常见的子字符串，而不仅仅是最长的）。

然后我修改了测试数据以包含另一个与当前获胜者长度相同的公共子字符串（7 个字符）、一个较短但仍然是 4 个字符的公共子字符串和 3 个随机字符。这将最大测试字符串大小从 32 个字符增加到 46 个字符。再次运行测试（相同代码），T-SQL 版本必须在 23 分钟时被终止，并且只测试了前 3 个长度：27、26 和 25。SQLCLR UDA 在大约 1 分 10 秒后返回。

是时候庆祝了吗？SQLCLR 拯救了这一天吗？坚持，稍等..

凭直觉，我决定看看我在 SQLCLR 版本中添加的优化是否对 T-SQL 有帮助，即：

• 获取最短的两个字符串（最短的将具有最少数量的可能子字符串，并且无论如何都是可能的最长匹配项）。

• 从两个短字符串中提取所有可能的公共子字符串（所有行中“公共”的任何子字符串必须在仅从这两个字符串派生的集合中，并且不能引入来自其他行的新子字符串，因为它们不会“常见的”）。

• 从最长的公共子串开始，测试是否在所有行中都找到它。我使用IF (NOT EXISTS (WHERE CHARINDEX(substring, test_row) > 0))是因为该EXISTS子句将在返回 0（意味着子字符串不存在）的第一行退出，因此不需要测试所有行。这部分是用CURSOR(shh，不要告诉任何人)来完成的，因为它允许从列表的顶部开始，只需选择每个新行，而无需每次重新扫描列表以找到下一个条目。

• 找到第一个子字符串后，将其长度保存在变量中，并将子字符串本身保存到表变量中。

• 继续测试，但仅限于与找到的第一个公共子字符串长度相同的字符串。只要要搜索的下一个子字符串的长度小于要匹配的第一个子字符串的长度，就退出循环并清除光标。

所有这些游标的东西都必须让它变得非常缓慢，对吧？好吧，请记住，之前的 T-SQL 版本需要几个小时才能完成，而 SQLCLR UDA 需要 1 分 10 秒，您可能会猜到这个更新版本需要什么？几分钟？10分钟？更多的？毕竟光是说“光标”就是自动打5分钟吧？修改版本的实际时间：

22秒！！！

当然，这主要是由于子字符串在较长的一侧（与字符串的大小相比），因此循环能够比最长公共子字符串只有 3 或 4 个字符长（即它有测试较少，但这仍然是一个有效的案例并且不是作弊）。此外，在 T-SQL 中工作的一个好处是您可以针对单个值测试整个集合，而 SQLCLR 只有当前行而无法看到整个集合，因此 SQLCLR 无法在找到最长公共子串时短路（因为它首先不知道什么是“公共”，直到它在所有行中执行）。

最后的更改是允许新的 T-SQL 版本返回所有“公共”子字符串，而不仅仅是最长的子字符串，同时在 datatype 的第二列中指示哪些是最长的BIT。当返回所有子串时，镜像 SQLCLR UDA 的功能（即使 UDA 只返回最长的公共子串，它仍然存储了所有公共子串的完整列表，因为它再次没有短路的能力）， T-SQL 版本在 2 分 41 秒后返回。

因此，存在条件是 T-SQL 可以更快，即使是 120 万行。但是 SQLCLR 版本的性能要稳定得多，并且当您需要所有公共子字符串时肯定会更快。

包含所有 3 个测试及其结果的测试脚本可以在 Pastebin 上找到：

最长公共子串的 SQLCLR UDA - 测试

PS 尽管测试超过 120 万行，但测试的最长字符串是 46 个字符。我不确定在更长的字符串上操作会如何影响这两种方法的性能。该测试将不得不等到有时间进行;-)。