Gibt es eine SQL Server-Implementierung des Longest Common Substring-Problems?

Gibt es eine SQL Server-Implementierung des Longest Common Substring-Problems ? Eine Lösung, die alle Zeilen einer Spalte in SQL Server überprüft? Ich habe Lösungen gesehen, die zwei Zeichenfolgen als Eingabe verwenden, aber keine SQL Server-Lösung, die alle Zeilen einer Spalte in einer Tabelle betrachtet.

Ich habe ein paar Dinge ausprobiert, aber um ehrlich zu sein, denke ich, dass mir im Moment eine Lösung über den Kopf geht. Vorschläge sind daher willkommen.

Hier gibt es kein Problem der "realen Welt". Ich betrachte nur Programmierprobleme und wie sie mit SQL Server gelöst werden könnten.

Das kann gemacht werden ziemlich leichtals SQLCLR User-Defined Aggregate (UDA). Ein Aggregat wird über eine Reihe von Zeilen ausgeführt, sodass Sie über alle Zeilen oder nur eine Teilmenge hinweg arbeiten können, basierend auf einer WHEREBedingung und optional GROUP BY(wenn Sie über mehrere Sätze von Zeilen arbeiten möchten).

ABER, ob Sie dies tun sollten oder nicht, hängt davon ab, was Sie mit dem Ergebnis vorhaben. Wenn dies ein einmaliges Projekt ist, um Nachforschungen anzustellen, die nicht wiederholt werden, ist es wahrscheinlich am besten, einfach eine kleine Konsolen-App zu erstellen, um die Zeilen einzulesen und entsprechend zu verarbeiten.

Wenn Sie jedoch den zurückgegebenen Wert in einem datenbankzentrierten Prozess verwenden müssen, sollte SQLCLR in Ordnung sein (vorausgesetzt, Sie befolgen die beiden unter "Die folgenden Tricks können verwendet werden, um die Speichernutzung einer Implementierung zu reduzieren"). im Pseudocode- Abschnitt. Sie müssen nur einen "kreativen" Weg finden, um mit der Situation umzugehen, dass mehrere Ergebnisse für den längsten gemeinsamen Teilstring erzielt werden (dh wenn zwei oder mehr gemeinsame Teilstrings für den "ersten Platz" gelten) das Beispiel von der Wikipedia-Seite (die 2 Übereinstimmungen für die 2 Zeichenfolgen zeigt):

ABAB
BABA

Gibt beide zurück:

• BAB
• ABA

Möglicherweise wird ein XML-Dokument mit Übereinstimmungen zurückgegeben, da dieses analysierbar ist und eine beliebige Zeichenfolge enthalten kann (wenn es ordnungsgemäß maskiert ist).

UPDATE (aktualisiert und erneut aktualisiert)

Den .NET C # -Quellcode hierfür finden Sie auf Pastebin.com unter:

SQLCLR UDA für den längsten gemeinsamen Teilstring - Quellcode

Und für alle, die mit dieser UDA spielen möchten, ohne sie zu kompilieren, finden Sie auf Pastebin.com ein Installations-T-SQL-Skript (keine externe DLL) unter:

SQLCLR UDA für den längsten gemeinsamen Teilstring - Installer

Der UDA sollte ziemlich speichereffizient sein, da er nur Teilzeichenfolgen speichert, die mit der aktuellen Zeichenfolge und allen zuvor angetroffenen Zeichenfolgen übereinstimmen. Wenn eine neue Zeile die UDA aufruft, werden alle Teilzeichenfolgen, die nicht in der neuen Zeichenfolge gefunden werden, aus der Auflistung entfernt.

Es ist auch insofern CPU-effizient, als wenn zu irgendeinem Zeitpunkt die Anzahl der "gemeinsamen" Teilzeichenfolgen auf Null geht, ein Flag gesetzt wird, das angibt, dass überhaupt keine Teilzeichenfolgen möglich sind, und alle zukünftigen Ausführungen kurz gekündigt werden, um sie beim Aufruf einfach zu beenden. Dies geschieht sofort, wenn eine leere Zeichenfolge gefunden wird. In jedem dieser Fälle wird ein leeres XML-Dokument (dh nur das Stammelement) zurückgegeben. Die Bedeutung des leeren Dokuments entspricht einer leeren Zeichenfolge, da die Eingabezeichenfolgen nur gemeinsam haben, dass sie keine NULLZeichenfolgen sind.

NULLwird in meiner Interpretation ignoriert und zeigt keine möglichen Übereinstimmungen an, wie dies bei einer leeren Zeichenfolge der Fall ist.

A NULLwird in den folgenden zwei Fällen zurückgegeben:

• Alle Eingänge sind NULL
• Es war nur eine einzige Nicht- NULLZeile in der Menge und daher gab es keine andere Zeichenfolge, mit der verglichen werden konnte, daher nichts, was als "häufig" angesehen werden könnte.

Ich habe einen zweiten Eingabeparameter hinzugefügt, der steuert, ob die Rückgabe nur die längste gemeinsame Teilzeichenfolge oder alle gemeinsamen Teilzeichenfolgen ist. Bei der Rückgabe von all wird jedem "Element" ein Attribut hinzugefügt, um anzugeben, ob es sich um eine der "längsten" Teilzeichenfolgen handelt oder nicht:

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

Kehrt zurück:

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

Und

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

Kehrt zurück:

<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>

Außerdem werden bei den Vergleichen jetzt Groß- und Kleinschreibung berücksichtigt, um der typischen Sortierung zu entsprechen.

Im Folgenden finden Sie 16 weitere Testfälle, die nur die Funktionalität und nicht die Leistung überprüfen. Ich werde später weitere Tests veröffentlichen, die über viele Zeilen mit viel längeren Zeichenfolgen ausgeführt werden. Ich habe vorerst absichtlich auf das Kombinieren von Charakteren und Zusatzcharakteren verzichtet, da diese etwas komplizierter sind.

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>
*/

Letztes Update (hoffentlich)

Ich habe ein paar geringfügige Änderungen am Testcode vorgenommen, der in der Antwort von @ MisterMagoo enthalten ist , damit: a) Bindungen für die "längste" gemeinsame Teilzeichenfolge zurückgegeben werden und b) das letzte Zeichen in jeder Zeichenfolge als Teil der Suche enthalten ist. Ich habe auch geringfügig geändert, wie die anfänglichen Testzeilen gesammelt werden, sodass etwas mehr als 1 Million Zeilen vorhanden sind, und die Tests erneut ausgeführt. Das Ergebnis war, dass die T-SQL-Version 1 Minute und 13 Sekunden dauerte, während die SQLCLR-UDA nur 12 Sekunden dauerte (und sogar die Option hat, alle gängigen Teilzeichenfolgen zurückzugeben, nicht nur die längsten).

Ich habe dann die Testdaten so geändert, dass sie einen weiteren gemeinsamen Teilstring mit der gleichen Länge wie der aktuelle Gewinner (7 Zeichen), einen kürzeren, aber immer noch gemeinsamen Teilstring mit 4 Zeichen und 3 zufälligen Zeichen enthalten. Dies erhöhte die maximale Größe der Testzeichenfolge von 32 Zeichen auf 46 Zeichen. Beim erneuten Ausführen des Tests (gleicher Code) musste die T-SQL-Version nach 23 Minuten beendet werden und hatte nur die ersten drei Längen getestet: 27, 26 und 25. Die SQLCLR-UDA kehrte in etwa 1 Minute und 10 Sekunden zurück.

Ist es Zeit zu feiern? Hat SQLCLR den Tag gerettet? Warten Sie mal..

Aus einer Ahnung heraus entschied ich mich, ob die Optimierung, die ich der SQLCLR-Version hinzugefügt habe, dem T-SQL helfen würde, nämlich:

• Schnappen Sie sich die kürzesten zwei Saiten (die kürzeste hätte die geringste Anzahl möglicher Teilzeichenfolgen und wäre sowieso die längste mögliche Übereinstimmung).

• Extrahieren Sie alle möglichen gemeinsamen Teilzeichenfolgen aus den beiden kurzen Zeichenfolgen (alle Teilzeichenfolgen, die über alle Zeilen hinweg "gemeinsam" sind, müssen sich in der Menge befinden, die nur aus diesen beiden Zeichenfolgen abgeleitet ist, und es können keine neuen Teilzeichenfolgen aus anderen Zeilen eingeführt werden, wie dies nicht der Fall wäre "verbreitet").

• Beginnen Sie mit dem längsten gemeinsamen Teilstring und prüfen Sie, ob er in allen Zeilen gefunden wird. Ich habe verwendet, IF (NOT EXISTS (WHERE CHARINDEX(substring, test_row) > 0))weil die EXISTSKlausel in der ersten Zeile beendet wird, die eine 0 zurückgibt (was bedeutet, dass Teilzeichenfolge nicht vorhanden ist) und daher nicht alle Zeilen testen muss. Dieser Teil wird mit einem CURSOR(shh, sag es niemandem) abgeschlossen, da es ermöglicht, am Anfang der Liste zu beginnen und einfach jede neue Zeile auszuwählen, ohne die Liste jedes Mal neu scannen zu müssen, um den nächsten Eintrag zu finden.

• Sobald der erste Teilstring gefunden wurde, speichern Sie seine Länge in einer Variablen und speichern Sie den Teilstring selbst in einer Tabellenvariablen.

• Testen Sie weiter, jedoch nur für Zeichenfolgen, die dieselbe Länge wie der erste häufig gefundene Teilstring haben. Sobald die Länge des nächsten zu suchenden Teilstrings geringer ist als die Länge des ersten zu übereinstimmenden Teilstrings, verlassen Sie die Schleife und bereinigen Sie den Cursor.

All dieses Cursor-Zeug muss es schmerzhaft langsam machen, oder? Wenn man bedenkt, dass die Fertigstellung der vorherigen T-SQL-Version mehrere Stunden gedauert hätte und die SQLCLR-UDA 1 Minute und 10 Sekunden gedauert hätte, könnte man vermuten, dass diese aktualisierte Version dauern würde. Was? Ein paar Minuten? 10 Minuten? Mehr? Nur "Cursor" zu erwähnen, ist doch ein automatischer 5-Minuten-Treffer, oder? Die tatsächliche Zeit für die geänderte Version:

22 Sekunden !!!

Dies liegt natürlich hauptsächlich daran, dass sich die Teilzeichenfolgen auf der längeren Seite befinden (im Vergleich zur Größe der Zeichenfolgen), sodass die Schleife früher beendet werden konnte, als wenn die längste gemeinsame Teilzeichenfolge nur 3 oder 4 Zeichen lang war (dh hatte) weniger zu testen, aber das ist immer noch ein gültiger Fall und betrügt nicht). Ein Vorteil der Arbeit in T-SQL besteht auch darin, dass Sie den gesamten Satz anhand eines einzelnen Werts testen können, während SQLCLR nur die aktuelle Zeile enthält und nicht den gesamten Satz sehen kann. Daher kann der SQLCLR beim Auffinden des längsten gemeinsamen Teilstrings keinen Kurzschluss verursachen (weil es nicht weiß, was "allgemein" ist, bis es über alle Zeilen ausgeführt wurde).

Eine letzte Änderung bestand darin, der neuen T-SQL-Version zu ermöglichen, alle "allgemeinen" Teilzeichenfolgen zurückzugeben, nicht nur die längsten, und gleichzeitig anzugeben, welche in einer zweiten Spalte des Datentyps die längsten waren BIT. Bei der Rückgabe aller Teilzeichenfolgen, die die Funktionalität der SQLCLR-UDA spiegeln (selbst wenn die UDA nur die längsten gemeinsamen Teilzeichenfolgen zurückgibt, wird immer noch die vollständige Liste aller gemeinsamen Teilzeichenfolgen gespeichert, da sie wiederum nicht kurzschließen kann) Die T-SQL-Version kehrt in 2 Minuten und 41 Sekunden zurück.

Es gibt also Bedingungen, unter denen T-SQL selbst bei 1,2 Millionen Zeilen schneller sein kann. Die Leistung ist jedoch für die SQLCLR-Version weitaus stabiler und definitiv schneller, wenn Sie alle gängigen Teilzeichenfolgen verwenden möchten.

Das Testskript, das alle drei Tests zusammen mit ihren Ergebnissen enthält, finden Sie auf Pastebin unter:

SQLCLR UDA für die längste gemeinsame Teilzeichenfolge - Prüfung

PS Obwohl der Test über 1,2 Millionen Zeilen durchgeführt wurde, war die längste getestete Zeichenfolge 46 Zeichen. Ich bin mir nicht sicher, wie sich die Leistung beider Ansätze auf die Leistung beider Ansätze auswirken würde. Dieser Test muss warten, bis es Zeit dafür gibt ;-).

Solomon hat wahrscheinlich Recht, aber bis eine CLR-Lösung angezeigt wird, ist hier eine T-SQL-Version zum Spielen.

/* Create some test data : on SQL 2016 this creates about 470K rows to test (with duplicates) */

 if object_id('tempdb..#Strings') is not null  drop table #Strings

   select a.Name as String, len(a.Name)+1 as StringLength
   into #Strings
   from sys.all_columns a, sys.all_columns b
   where a.Name like '%refer%';

 set nocount on;

 /* Any nulls mean there is not a "longest common string" */
 if exists(select 1 from #Strings where String is null)
 begin
   return;
 end;

/* We need to know number of rows in the sample and the length of the shortest string
   as the longest common substring cannot be longer than the shortest string in the set */

 declare @totalrows int;
 declare @minlen tinyint;
 declare @result varchar(50);

 select @minlen = min(StringLength-1), @totalrows = count(distinct String) from #Strings;

 raiserror(N'Maximum Possible Length: %d Total Distinct Rows: %d',0,0,@minlen,@totalrows) with nowait;

/* Check backwards from the longest possible string to the shortest and break when we find a match */
/* You might want to check the air conditioner is switched on here */

 while @minlen>1 and @result is null
 begin
   raiserror(N'Processing strings of length: %d',0,0,@minlen) with nowait;

   /* this method is "brute force" 
      1. find all substrings for each input string
      2. pick the first substring that appears in every input string
         we find this by grouping, counting and comparing to the number of input strings
   */
   select top(1) @result=match
   from (
     select String, substring(String, T.N, @minlen) match
     from #Strings
     cross apply ( select StringLength - @minlen ) a(L)
     cross apply (
       select top(a.L) V.N
       from (
         values(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34),(35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50)
         ) V(N)
       ) T(N)
     ) matches(String, match)
   group by match
   having count(distinct String) = @totalrows;
--   order by match;

   /* Decrement so next time we check for a shorter match */
   set @minlen = @minlen -1;
 end

/* display the result */
select 'Longest Common Substring: '+isnull(@result,'*** no match found ***');

AKTUALISIERT am 20171127 um 23:58 Uhr CST, UM UNIGRAMME ZU BEHANDELN

Ich weiß, dass ich hier etwas spät dran bin (um mehr als ein Jahr), aber meine neueste Funktion für die längste gemeinsame Teilzeichenfolge von t-sql ist mehrere tausend Mal schneller als alles, was ich irgendwo gesehen habe, einschließlich der oben genannten CLR (ich habe sie gerade getestet) ).

Es ist eine Semi-Brute-Force-Technik, auf die ich gekommen bin:

1. Löst die kürzere der beiden Zeichenfolgen auf und durchsucht die längere Teilzeichenfolge nach einer Übereinstimmung.

2. Akzeptiert einen dritten Parameter namens "Fenster" (es ist eher ein NTile-Parameter, aber ich verwende den Begriff "Fenster", weil nur wenige Leute Ntile verstehen.) Dies ist die geheime Sauce, die diesen bösen Hund so schnell macht

3. Die Routine verwendet dann eine reine Brute Force, um festzustellen, ob die Teilzeichenfolgen mit einer Größe von 20 oder weniger in der kurzen Zeichenfolge auch in der längeren Zeichenfolge vorhanden sind. Verwenden einer Tally-Tabelle - Der Brute-Force-Ansatz für Teilzeichenfolgen mit einer Größe von 20 oder weniger erfolgt sofort (0 ms).

4. Danach durchsucht es die längere Zeichenfolge nach Teilzeichenfolgen, die in der kürzeren Zeichenfolge vorhanden sind, deren Größe durch @window gleichmäßig teilbar ist. Wenn beispielsweise @window = 100 ist, wird nach übereinstimmenden Teilzeichenfolgen mit einer Länge von 100, 200 ... bis zur Länge der längeren Zeichenfolge gesucht (z. B. wenn die längere Zeichenfolge 515 Zeichen lang ist, wird nach Übereinstimmungen gesucht Teilzeichenfolgen mit einer Länge von 100, 200, 300, 400 und 500 Zeichen.

5. Sobald wir herausgefunden haben, in welchem ​​"Fenster" die längste Teilzeichenfolge lebt, verwende ich eine Zähltabelle und einen Trick "Lücken und Inseln auf Zeichenfolgen", den ich von Chris Morris ( hier besprochen ) gelernt habe , um jede Zeichenfolge auf übereinstimmende Teilzeichenfolgen zu vergleichen.

6. TOP 1 mit Bindungen wird verwendet, um den längsten Teilstring zu identifizieren.

Die Funktionen):

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;
GO

CREATE FUNCTION dbo.lcssWindowAB(@s1 varchar(8000), @s2 varchar(8000), @window int)
RETURNS TABLE WITH SCHEMABINDING AS RETURN
/*****************************************************************************************
Purpose
 Calculates the longest common substring between two varchar(n) strings up to 8000 
 characters each.

Developer Notes:
 1. Optimal performance gains will be seen on longer strings. All Longest Common Substring
    functions I have seen in SQL Server begin to choke at 500-1000. Set based Brute force 
    solutions that use a tally table are very fast for up to 1000 characters but begin to 
    slow dramatically after. 

    With N as the length of a string, The number of substrings is: N(N+1)/2
    For 1,000 character string: 1000(1000+1)/2 = 500,500   substrings
    For 2,000 characters:       2000(2000+1)/2 = 2,001,000 substrings

 2. Requires a materialized tally table beginning with 1 containing at least 8000 numbers;
    as written, this function will slow to a crawl using a cte tally table. This is due to
    the WHERE x.n BETWEEN 2 AND 10 clause. A CTE tally table will struggle with this but a
    correctly indexed materialized tally table will not. 

    For optimal performance your tally table should have a unique nonclustered index.
    THE DDL TO BUILD THE REQUIRED TALLY TABLE IS BELOW.

 3. Performance optimizations:

   3.1. The first major optimization is that the *shorter* of the two strings is broken up 
        into substrings which are then searched for in the larger string using CHARINDEX. 
        This reduces the number of substrings generated by:
          abs(len(@s1)-len(@s2)) * (abs(len(@s1)-len(@s2)) + 1) / 2  

        For example, if one is 20 characters longer than the other, 210 fewer substrings 
        will be evaluated; for 100 it's 5,050 fewer substrings, etc. 

   3.2. The second optimization is a technique I developed that I call "windowing". I use
        a @window parameter to break up the search specific windows for the presense of a
        matching substring. 1-10 legnth substrings in the smaller string are searched for 
        in the longer string. After that, only tokens with sizes evenly divisible by the
        @window parameter are evaluated. For example, say the short string length is 100
        and I set @window 20. All tokens sized 1-10 are searched for, the 20-grams, then
        40, 60... 100. This reduces the number of substrings from 5,050 to somewhere 
        beween 480 & 500 (depending on the size of the longest common substring.)

 4. The window parameter is for optimization only! It does not affect the final result set
    in any way. I strongly suggest that testing the function using different window sizes
    for different scenarios; the optimal size will vary. I have seen queries execute 3-10 
    faster when changing the window size. Start with 100, then try windows sizes of 
    20, 200, 300, 1000... 

 5. This function does not see a performance gain when run in parallel; 
    use option (maxdop 1) unless you're testing shows performance gains when running under 
    a parallel execution plan. 

Required Tally Table DDL (this will build exactly 8000 rows):
------------------------------------------------------------------------------------------
  -- (1) Create tally table
  IF OBJECT_ID('dbo.tally') IS NOT NULL DROP TABLE dbo.tally;
  CREATE TABLE dbo.tally (N int not null);

  -- (2) Add numbers to the tally table
  WITH DummyRows(V) AS ( 
    SELECT 1 FROM (VALUES -- 100 Dummy Rows
     ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),
     ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($)) 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;

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

  ALTER TABLE dbo.tally ADD CONSTRAINT uq_nc_tally UNIQUE NONCLUSTERED(N);
  GO
------------------------------------------------------------------------------------------
Usage Examples:
  SELECT * FROM dbo.lcssWindowAB('abcxxx', 'yyyabczzz', 10);

  SELECT * FROM dbo.lcssWindowAB('123xxx', '!!123!!xxx!!', 10);

History:
 20171126 - Initial Development - Developed by Alan Burstein  
 20171127 - updated to return unigrams when longest common substring is 1;
            updated to use a materialized tally table; -- Alan Burstein
*****************************************************************************************/
SELECT TOP (1) WITH TIES itemIndex, itemLen = itemLen+addThis, item
FROM dbo.getshortstring8k(@s1, @s2) xs
CROSS APPLY
(
  SELECT
    itemIndex = MIN(position) over (partition by grouper order by (select $)),
    itemLen   = itemLen,
    addThis   = position-MIN(position) over (partition by grouper order by (select $)),
    item      = SUBSTRING
                (
                 xs.s1, 
                 MIN(position) over (partition by grouper order by (select $)),
                 itemLen+position-MIN(position) over (partition by grouper order by (select $))
                )
  FROM 
  (
    SELECT position - ROW_NUMBER() OVER (ORDER BY position), position, itemLen
    FROM
    (
      SELECT TOP (1) WITH TIES t.N, x.N -- Get the "longest" (including ties)
      FROM dbo.tally t                  -- all positions within the shorter string (s.s1)
      CROSS JOIN dbo.tally x            -- all sizes of substrings within the shorter string
      WHERE (t.N <= LEN(xs.s1) AND x.N <= LEN(xs.s1) AND LEN(xs.s1) - t.N + 1 - x.N >= 0)
      AND   (x.N BETWEEN 2 AND 10 OR x.N % @window = 0)      -- only 2-20 & @window-sized tokens
      AND   CHARINDEX(SUBSTRING(xs.s1, t.N, x.N), xs.s2) > 0 -- only tokens matched in both strings
      ORDER BY -x.N
    ) longSubstrings (position, itemLen)
    UNION ALL
    SELECT -position-1, position, 1
    FROM
    (
      SELECT t.N, 1             -- unigrams only
      FROM dbo.tally t          -- all positions within the shorter string (s.s1)
      WHERE (t.N <= LEN(xs.s1)) -- all valid unigrams
      AND   CHARINDEX(SUBSTRING(xs.s1, t.N, 1), xs.s2) > 0 -- only unigrams matched in both strings
    ) unigrams (position, itemLen)
  ) addGrouper (grouper, position, itemLen)
) lcssWindow (itemIndex, itemLen, addthis, item)
WHERE @window >= 10 AND @window%10 = 0 -- must be greater than 10 and divisible by 10
AND   CHARINDEX(item, xs.s2) > 0
ORDER BY -itemLen, -addThis;
GO

Hier ist ein Beispiel dafür, wie die Funktion die längste gemeinsame Teilzeichenfolge zwischen zwei Zeichenfolgen mit einer Länge von etwa 7700 Zeichen berechnet. Es gibt die richtige Antwort in 16 Millisekunden zurück.

set statistics time on;

declare
  @s1 varchar(8000) = replicate('x',50)+replicate('Wow!',1900)+'!'+'junk,junk,junk...',
  @s2 varchar(8000) = replicate('z',95)+replicate('Wow!',1900)+'!'+'zzzzzzzzzzz......',
  @window int       = 100;

select len(@s1), len(@s2);

select * from dbo.lcssWindowAB(@s1, @s2, 100);
set statistics time off;

Dies ist Teil eines Artikels, an dem ich arbeite. Da kommt noch mehr!