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:
Ausweis | Daten |
---|---|
1 | der schnelle braune Fuchs springt über den faulen Hund |
2 | die schnelle braune katze springt über den faulen frosch |
3 | der faule schnelle braune frosch springt über die katze |
4 | lorem ipsum dolor sit amet |
Und ich suche nach “der schnelle braune Ochse springt über einen faulen Hund”, ich möchte Ergebnisse, die ungefähr so aussehen:
Ausweis | Punktzahl |
---|---|
1 | 95 |
2 | 80 |
3 | 40 |
4 | 0 |
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 LIKE
oder CONTAINS
anscheinend 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)