Una ricerca che perdona i refusi: come funziona davvero la tolleranza agli errori di battitura

Il problema, detto con precisione

Un cliente che cerca "borza" intende quasi certamente "borsa". Una casella di ricerca che restituisce zero risultati su quella query non sta essendo rigorosa per un buon motivo: sta fallendo esattamente il compito per cui esiste, trovare ciò che la persona intendeva, non solo ciò che ha scritto. La tolleranza ai refusi è il nome generico dei meccanismi che chiudono quella distanza. Sembra una funzione sola. In realtà sono almeno due meccanismi diversi, con costi diversi e modi diversi di rompersi, e confonderli è dove la maggior parte delle implementazioni ingenue va storto.

Il mattone di base: la distanza di edit

Quasi ogni meccanismo di tolleranza ai refusi, qualunque sia il motore, si basa sulla stessa idea di fondo: la distanza di edit tra due stringhe, più comunemente la distanza di Levenshtein, che conta il numero minimo di inserimenti, cancellazioni o sostituzioni di un singolo carattere necessari per trasformare una stringa nell'altra. "Borza" è a una sostituzione di distanza da "borsa". "Brosa" invece di "borsa", con due lettere vicine scambiate di posto, è a una trasposizione: due edit secondo la definizione classica di Levenshtein, uno solo nella variante Damerau-Levenshtein, che conta lo scambio come un unico edit. Il numero da solo non decide niente; conta cosa il sistema ne fa.

Il dettaglio da non sbagliare fin da subito: una distanza di uno o due edit è generosa per una parola lunga e pericolosa per una corta. Due edit su una parola di dieci lettere la cambiano appena. Due edit su una parola di tre lettere possono trasformarla in una parola completamente diversa: "sale" e "sole" sono a un edit di distanza, ma lo sono anche "sale" e "vale", e "sale" e "sala". Un sistema di tolleranza ai refusi che applica la stessa soglia di distanza indipendentemente dalla lunghezza della parola finirà per "correggere" allegramente parole corte e distinte l'una nell'altra. La correzione onesta è una soglia proporzionata alla lunghezza: nessuna correzione sulle parole molto corte, un edit permesso da poche lettere in su, due edit solo quando la parola è abbastanza lunga da restare comunque riconoscibile dopo due modifiche.

Due meccanismi diversi, spesso confusi per una sola funzione

"Tolleranza ai refusi" di solito significa una di due cose davvero diverse, e quale delle due un sistema offre cambia cosa può e non può fare.

1. Corrispondenza fuzzy al momento della ricerca

Elasticsearch, OpenSearch e motori simili possono eseguire una query fuzzy (o il parametro di fuzziness su una query match) che confronta il termine cercato con i termini indicizzati usando la distanza di edit direttamente al momento della ricerca, senza dover sapere in anticipo quali errori di battitura esistano. Funziona perché il motore tiene già un indice invertito di ogni termine presente nel catalogo; una query fuzzy è, a grandi linee, "trova i termini indicizzati entro N edit da questo, e ordina i risultati per quanto sono vicini". Non richiede nessun passaggio di manutenzione separato e degrada con eleganza: una query leggermente sbagliata comunque mette in cima i termini indicizzati più vicini. Il costo reale si vede su un campo con moltissimi valori distinti o un vocabolario molto grande, dove calcolare la distanza di edit contro un grande insieme di termini candidati pesa più di una ricerca esatta per termine, ed è per questo che la corrispondenza fuzzy si applica di solito in modo selettivo (il campo di testo libero principale, non ogni campo) invece che ovunque per impostazione predefinita.

2. Correzione a dizionario, applicata solo quando serve

Un sistema senza un motore di ricerca che valuta corrispondenze fuzzy in modo nativo, per esempio una ricerca appoggiata solo su SQL, deve costruirsi il meccanismo da solo: un dizionario di termini noti, costruito dai nomi di prodotto e di marchio del catalogo stesso, contro cui confrontare un termine di ricerca che non ha trovato niente per individuare la parola vera più vicina. Il dizionario stesso viene spesso indicizzato per trigrammi di caratteri (frammenti di tre lettere) invece che confrontato lettera per lettera con ogni parola, sia perché un indice per trigrammi restringe l'elenco dei candidati plausibilmente vicini prima di calcolare la distanza di edit esatta su un insieme molto più piccolo, sia perché non richiede nessun motore esterno.

Il dettaglio che rende questo approccio economico nella pratica, invece che una trappola di prestazioni, è quando scatta la ricerca nel dizionario. Se ogni ricerca pagasse il costo di una consultazione del dizionario, la tolleranza ai refusi rallenterebbe ogni interrogazione, comprese quelle scritte correttamente che avevano già trovato risultati. La consultazione ha senso solo dopo che la ricerca esatta è già tornata vuota: una query corretta non la tocca mai, e solo il caso a zero risultati paga il costo aggiuntivo. Misurato su un catalogo reale, una query scritta correttamente e una scritta male che fa scattare il dizionario impiegavano lo stesso tempo, piccolo, in entrambi i casi (tra 0,16 e 0,19 secondi su quell'allestimento specifico): il percorso del dizionario aggiunge costo solo alle ricerche che altrimenti non avrebbero trovato niente.

Il dizionario richiede anche una manutenzione che una query fuzzy non richiede: deve imparare le parole nuove man mano che il catalogo cresce e dimenticare le parole appartenute a prodotti che non esistono più, altrimenti invecchia lentamente e inizia a suggerire correzioni verso prodotti fuori catalogo. Un dizionario ricostruito con una certa periodicità (per esempio ogni settimana, più un aggiornamento leggero la prima volta che una ricerca a zero risultati incontra una parola che ancora non conosce) lo mantiene allineato al catalogo senza doverlo ricostruire a ogni singola richiesta.

Dove la versione facile si rompe

• Una soglia di distanza fissa su parole di ogni lunghezza, come sopra: una correzione generosa su parole corte le trasforma l'una nell'altra.
• Correggere una query che ha già trovato risultati. Se una ricerca che ha già trovato prodotti viene comunque "corretta" verso un termine diverso e più popolare, il cliente può essere spostato lontano da quello che ha davvero scritto verso quello che il motore considera vicino e popolare. La correzione appartiene al caso genuino di zero risultati, non a una riscrittura costante e silenziosa di ogni query.
• Una correzione che scatta quando non dovrebbe. Su una pagina di ricerca a faccette, una selezione di filtri può legittimamente produrre zero risultati (un cliente ha scelto una combinazione di taglia e colore che nessuno ha in magazzino). Non è un problema di ortografia, e un livello di tolleranza ai refusi che non sa distinguere i due casi proverà a "correggere" un termine di ricerca scritto perfettamente perché sono i filtri, non la parola, ad aver svuotato la pagina.
• Fidarsi della corrispondenza fuzzy anche per la correttezza delle faccette. Far sì che una query con un refuso trovi comunque prodotti è un problema diverso dal contare correttamente quanti prodotti corrispondono a ogni valore di filtro. Un motore tollerante ai refusi che trova risultati per un termine scritto male calcolerà con sicurezza i conteggi delle faccette anche su quella corrispondenza approssimata; se qualcosa a valle (un elenco di "ricerche più frequenti" nel suggerimento automatico, per esempio) assume che "ha trovato almeno un prodotto" significhi "era un termine reale, scritto correttamente", finirà per pubblicare a ogni visitatore i refusi che i clienti stessi hanno digitato. Che un motore sia bravo nel suo lavoro è proprio ciò che rende facile commettere questo errore altrove nello stesso sistema.
• Silenzio invece di trasparenza. Una ricerca che sostituisce in silenzio un termine diverso da quello digitato, senza nessuna indicazione che sia avvenuta una sostituzione, lascia il cliente a chiedersi perché i risultati non corrispondono del tutto a quello che ha cercato. Una riga visibile e onesta, "Nessun risultato per X. Risultati mostrati per Y", costa una frase ed evita del tutto quella confusione.

Una checklist breve

• Proporzionate la distanza di edit permessa alla lunghezza della parola; non applicate la stessa soglia a una parola di tre lettere e a una di dodici.
• Correggete solo dopo una ricerca genuinamente a zero risultati, mai come riscrittura silenziosa di una query che ha già trovato qualcosa.
• Distinguete "la parola era scritta male" da "i filtri hanno svuotato la pagina": richiedono trattamenti diversi, e confonderli produce un tentativo di correzione dove non serviva.
• Se mantenete un vostro dizionario invece di affidarvi alla corrispondenza fuzzy nativa di un motore, tenetelo aggiornato: ricostruitelo con una certa periodicità e fatelo imparare dal catalogo mentre cambia, o inizierà a suggerire parole che non esistono più.
• Dite al cliente quando è avvenuta una sostituzione. Non lasciate che una corrispondenza fuzzy "riuscita" nasconda il fatto che quello che ha scritto e quello che ha ottenuto non sono la stessa parola.

In sintesi

La tolleranza ai refusi non è un interruttore acceso o spento: è una scelta tra due meccanismi diversi, la corrispondenza fuzzy nativa del motore al momento della ricerca, oppure un dizionario mantenuto e consultato solo su una ricerca genuinamente a zero risultati, ognuno con il proprio costo e il proprio modo di sbagliare in silenzio. I due errori da tenere d'occhio sono correggere parole che non erano affatto sbagliate, e fidarsi di una corrispondenza fuzzy per rispondere a domande per cui non è stata costruita, come un conteggio esatto di faccette. Gestiamo questo dentro cll_essearch, il nostro modulo di ricerca e navigazione a faccette per PrestaShop, sia con la corrispondenza fuzzy nativa di Elasticsearch sia con un nostro dizionario a trigrammi per i negozi che usano il motore nativo del database, se volete vedere questa distinzione applicata a un negozio vero.

Ricerca Elasticsearch & Navigazione a FaccetteRicerca velocissima e tollerante ai refusi con navigazione a faccette con pannello filtri modale, con motore…99,99 €Vedi il prodotto