Hai sicuramente visto le ricerche di testo fuzzy ovunque. Ad esempio si digita "stck" ma in realtà si intende "stack"! Vi siete mai chiesti come funziona questa roba?
Ci sono un sacco di algoritmi per fare la corrispondenza del testo fuzzy, ognuno con i suoi pro e contro. I più famosi sono edit distance e qgram. Voglio concentrarmi su qgram oggi e implementare un campione.
In pratica i qgram sono l'algoritmo di corrispondenza stringa fuzzy più adatto per i database relazionali. È piuttosto semplice "q" in qgram verrà sostituito con un numero come 2-gram o 3-gram o anche 4-gram.
2 grammi significa che ogni parola è suddivisa in un gruppo di due caratteri grammi. "Stack" sarà suddiviso in un insieme di {"st", "ta", "ac", "ck"} o "database" sarà suddiviso in {"da", "in", "ta", "ba ", "come", "se"}.
Una volta che le parole sono suddivise in 2 grammi, possiamo cercare nel database un insieme di valori anziché una stringa. Ad esempio, se l'utente ha digitato "stck", qualsiasi ricerca per "stck" non corrisponde a "stack" perché manca "a", ma il set di 2 grammi "" st "," tc "," ck "} ha 2 righe in comune con il set di stack da 2 grammi! Bingo abbiamo trovato una partita molto simile. Non ha nulla in comune con il set di database da 2 grammi e solo 1 in comune con il set da 2 grammi di "stat", quindi possiamo facilmente suggerire all'utente che intendeva scrivere: primo "stack" o secondo "stella ".
Ora implementarlo utilizzando Sql Server: presuppone un set di dati di parole ipotetiche. È necessario avere una relazione molti a molti tra 2 grammi e parole.
CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))
La tabella dei grammi deve essere raggruppata nel primo twog, quindi nella parola ID per le prestazioni. Quando si interroga una parola (ad esempio una pila), si inseriscono i grammi in una tabella temporanea. Per prima cosa creiamo alcuni milioni di record fittizi.
--make millions of 2grams
DECLARE @i int =0
WHILE (@i<5000000)
BEGIN
-- a random 2gram
declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
INS... INTO Grams (twog, wordId) VALUES (@rnum1 + @rnum2, CAST(RAND()*100000 AS int))
END
Ora consente di interrogare la parola "stack", che sarà rotto per: { 'st', 'ta', 'AC', 'ck'} due grammi.
DECLARE @word TABLE(twog char(2)) -- 'stack'
INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')
select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
GROUP BY wordId
È necessario assicurarsi che SQL Server utilizza un mazzo di indice cluster cerca (o loockups) per l'esecuzione di questa query.Dovrebbe essere la scelta naturale ma a volte le statistiche potrebbero essere danneggiate o non aggiornate e SqlServer potrebbe decidere che una scansione completa è più economica. Questo di solito accade se non conosce la cardinalità della tabella di sinistra, ad esempio SqlServer può presumere che la tabella @word sia enorme e che milioni di loockup siano più costosi di una scansione dell'indice completa.