[FIXED] Fuzzy-Phrase-Ähnlichkeit in SQL Server

Ausgabe

Wie soll ich mit SQL Server eine Fuzzy-Ranked-Suche über alle Zeilen in einer großen Tabelle nach Ähnlichkeiten mit einem langen Ausdruck in einer Spalte durchführen?

Mit anderen Worten, wenn meine Daten so aussehen:

Und ich suche nach “der schnelle braune Ochse springt über einen faulen Hund”, ich möchte Ergebnisse, die ungefähr so ​​aussehen:

Tatsächliche Daten hätten mehr Zeilen und längere Phrasen.

Offensichtlich möchte ich keine exakte Zeichenfolgenübereinstimmung, daher würde die Verwendung von LIKEoder CONTAINSanscheinend nicht funktionieren.

Die Wortreihenfolge ist wichtig, daher würde es auch nicht funktionieren, jedes Wort einzeln zu suchen.

Volltextindizes und Sound-ähnliche Indizes scheinen nur für die Ähnlichkeit von Teilzeichenfolgen nützlich zu sein, daher habe ich keine Möglichkeit gesehen, dies auf die Phrasenähnlichkeit anzuwenden. Wie könnten Sie dies beispielsweise so abfragen, dass ein ähnlicher Satz mit fehlenden oder hinzugefügten Wörtern eine anständige Punktzahl erhält?

Ich habe mit Edit Distance (Lavenshtein, Jaro-Winkler usw.) getestet, aber es ist viel zu langsam über einen großen Satz langer Saiten. Eine Abfrage dauert mehrere Minuten. Es hört sich so an, als ob es nur für kleinere Daten verwendet werden sollte, daher denke ich, dass hier ein anderer Ansatz erforderlich ist.

Ich habe gesehen, dass TFIDF und Cosinus-Ähnlichkeit erwähnt wurden, aber ich bin mir nicht sicher, ob das hier richtig ist oder wie es auf SQL Server implementiert werden könnte.

Außerdem ist die CLR-Unterstützung eingeschränkt, da wir SQL Server unter Linux verwenden. Es sieht so aus, als wäre es erlaubt, solange es keine unsicheren oder externen Berechtigungen erfordert.

Lösung

Eine relativ schnelle Methode zum schnellen Finden der am besten passenden Zeichenfolge unter Verwendung von Fuzzy-Matching-Logik kann auf dem Zählen übereinstimmender 3-Gramm in den Zeichenfolgen basieren.

Es kann vorgefertigte SQL-Funktionen und indizierte Tabellen verwenden, die die Suche beschleunigen sollten. Insbesondere muss es nicht den Abstand von der Suchzeichenfolge zu jeder Zeichenfolge im Datensatz prüfen.

Erstellen Sie der Einfachheit halber zunächst eine Tabellenfunktion, die Zeichenfolgen in Token mit drei Buchstaben aufteilt.

drop function dbo.get_triplets;
go
CREATE FUNCTION dbo.get_triplets
(   
    @data varchar(1000)
)
RETURNS TABLE AS RETURN 
(
    WITH Nums AS
    (
      SELECT n = ROW_NUMBER() OVER (ORDER BY [object_id])  FROM sys.all_objects 
    )
    select triplet,count(*) c, len(@data)-2 triplet_count
    from (
        select SUBSTRING(@data,n,3) triplet
        from (select top (len(@data)-2) n from nums) n
    ) triplets
    group by triplet
)
GO

Erstellen Sie ein Zeichenfolgen-Dataset

drop table if exists #data;
select * into #data
from (
values
(1, 'the quick brown fox jumps over the lazy dog'),
(2, 'the quick brown cat jumps over the lazy frog'),
(3, 'the lazy quick brown frog jumps over the cat'),
(4, 'lorem ipsum dolor sit amet')
) a(id,data);

Erstellen Sie eine indizierte Tabelle mit 3-Buchstaben-Token

drop table if exists #triplets;
select id,triplet,c,triplet_count data_triplet_count 
into #triplets
from #data d
cross apply dbo.get_triplets(d.data);

CREATE unique CLUSTERED INDEX IX_triplet_index ON #triplets(triplet,id); 

Dann würde ich eine effiziente Fuzzy-Suche nach einer Übereinstimmung mit einer bestimmten Zeichenfolge mit einer ähnlichen Abfrage erwarten

declare @string_to_search varchar(1000) = 'the quick brown ox jumps over a lazy dog';

select  matched.*,d.data,
cast(
cast(matched_triplets as float)
/
cast(case when data_triplet_count>string_triplet_count 
          then data_triplet_count 
          else string_triplet_count
          end as float) 
as decimal(4,3)) score 
from (
    select id,sum(case when a.c<b.c then a.c else b.c end) matched_triplets,
    max(a.data_triplet_count) data_triplet_count,
    max(b.triplet_count) string_triplet_count
    from #triplets a
    join dbo.get_triplets(@string_to_search) b
    on a.triplet = b.triplet
    group by id
) matched
join #data d
on d.id = matched.id;

Beantwortet von – Igor N.

Antwort geprüft von – Robin (FixError Admin)