Free Press

Il Fuzzy Matching ti permette di identificare le corrispondenze non esatte del tuo oggetto. È la pietra angolare di molte strutture dei motori di ricerca e uno dei motivi principali per cui è possibile ottenere risultati di ricerca pertinenti anche se si ha un errore di battitura nella query o un diverso tempo verbale.

Come ci si potrebbe aspettare, ci sono molti algoritmi che possono essere usati per la ricerca fuzzy sul testo, ma praticamente tutti i framework dei motori di ricerca (incluso bleve) usano principalmente la Levenshtein Distance per l’abbinamento fuzzy delle stringhe:

Levenshtein Distance

Conosciuta anche come Edit Distance, è il numero di trasformazioni (cancellazioni, inserzioni o sostituzioni) necessarie per trasformare una stringa sorgente in quella di destinazione. Per esempio, se il termine di destinazione è “book” e la fonte è “back”, sarà necessario cambiare la prima “o” in “a” e la seconda “o” in “c”, che ci darà una distanza di Levenshtein di 2.Edit Distance è molto facile da implementare, ed è una sfida popolare durante le interviste sul codice (È possibile trovare implementazioni di Levenshtein in JavaScript, Kotlin, Java, e molti altri qui).

Inoltre, alcuni framework supportano anche la distanza Damerau-Levenshtein:

Damerau-Levenshtein distance

È un’estensione della Levenshtein Distance, che permette un’operazione extra: Trasposizione di due caratteri adiacenti:

Ex: TSAR a STAR

Damerau-Levenshtein distance = 1 (Cambiare le posizioni S e T costa solo un’operazione)

Levenshtein distance = 2 (Sostituire S con T e T con S)

Fuzzy matching e rilevanza

Fuzzy matching ha un grande effetto collaterale; incasina la rilevanza. Anche se Damerau-Levenshtein è un algoritmo che considera la maggior parte degli errori di ortografia dell’utente comune, può anche includere un numero significativo di falsi positivi, soprattutto quando stiamo usando una lingua con una media di sole 5 lettere per parola, come l’inglese. Questo è il motivo per cui la maggior parte dei framework dei motori di ricerca preferisce attenersi alla distanza di Levenshtein. Vediamo un esempio reale:

Primo, useremo questo set di dati del catalogo dei film. Lo consiglio vivamente se volete giocare con la ricerca full-text. Quindi, cerchiamo i film con “libro” nel titolo. Un semplice codice sarebbe come il seguente:

Il codice sopra riportato porterà i seguenti risultati:

Di default, i risultati sono case-insensitive, ma si può facilmente cambiare questo comportamento creando nuovi indici con diversi analizzatori.

Ora, aggiungiamo una capacità di fuzzy matching alla nostra query impostando fuzziness a 1 (Levenshtein distance 1), il che significa che “libro” e “look” avranno la stessa rilevanza.

Ed ecco il risultato della ricerca fuzzy:

Ora, il film chiamato “Hook” è il primissimo risultato della ricerca, che potrebbe non essere esattamente quello che l’utente si aspetta in una ricerca per “Book”.

Come minimizzare i falsi positivi durante le ricerche fuzzy

In un mondo ideale, gli utenti non farebbero mai errori di battitura mentre cercano qualcosa. Tuttavia, questo non è il mondo in cui viviamo, e se volete che i vostri utenti abbiano un’esperienza piacevole, dovete gestire almeno una distanza di modifica di 1. Pertanto, la vera domanda è: come possiamo fare un fuzzy string matching minimizzando la perdita di rilevanza? Una corrispondenza con una distanza di modifica più bassa di solito ottiene un punteggio più alto. Questa caratteristica ci permette di combinare le due query con diversi livelli di fuzziness in una sola:

Ecco il risultato della query fuzzy di cui sopra:

Come potete vedere, questo risultato è molto più vicino a quello che l’utente potrebbe aspettarsi. Notate che ora stiamo usando una classe chiamata DisjunctionQuery, le disgiunzioni sono un equivalente dell’operatore “OR” in SQL.

Che altro potremmo migliorare per ridurre l’effetto collaterale negativo di un algoritmo di corrispondenza fuzzy? Rianalizziamo il nostro problema per capire se ha bisogno di ulteriori miglioramenti:

Sappiamo già che le ricerche fuzzy possono produrre alcuni risultati inaspettati (ad esempio Book -> Look, Hook). Tuttavia, una ricerca per singolo termine è di solito una query terribile, poiché ci dà a malapena un indizio di ciò che esattamente l’utente sta cercando di realizzare.

Anche Google, che ha probabilmente uno degli algoritmi di ricerca fuzzy più sviluppati in uso, non sa esattamente cosa sto cercando quando cerco “tavolo”:

Quindi, qual è la lunghezza media delle parole chiave in una query di ricerca? Per rispondere a questa domanda, mostrerò un grafico tratto dalla presentazione di Rand Fishkin del 2016. (È uno dei guru più famosi del mondo SEO)

Secondo il grafico sopra, ~80% delle query di ricerca hanno 2 o più parole chiave, quindi proviamo a cercare il film “Black Book” usando la sfocatura 1:

Risultato:

Non male. Abbiamo ottenuto il film che stavamo cercando come primo risultato. Tuttavia, una query di disgiunzione porterebbe ancora un migliore insieme di risultati.

Ma ancora, sembra che abbiamo una nuova bella proprietà qui; l’effetto collaterale del fuzziness matching diminuisce leggermente all’aumentare del numero di parole chiave. Una ricerca per “Black Book” con fuzziness 1 può ancora portare risultati come back look o lack cook (alcune combinazioni con edit distance 1), ma è improbabile che questi siano veri titoli di film.

Una ricerca di “book eli” con fuzziness 2 lo porterebbe ancora come terzo risultato:

Tuttavia, poiché la parola inglese media è lunga 5 lettere, NON raccomanderei di usare una distanza di modifica maggiore di 2 a meno che l’utente non stia cercando parole lunghe che sono facili da scrivere male, come “Schwarzenegger” per esempio (almeno per i non tedeschi o non austriaci).

Conclusione

In questo articolo, abbiamo discusso il fuzziness matching e come superare il suo principale effetto collaterale senza rovinare la sua rilevanza. Attenzione, l’abbinamento fuzzy è solo una delle tante caratteristiche di cui dovreste approfittare per implementare una ricerca pertinente e user-friendly. Ne discuteremo alcune durante questa serie: N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.

Guardate anche la Parte 1 e la Parte 2 di questa serie.

Nel frattempo, se avete domande, twittatemi a @deniswsrosa.