Consigli su come migliorare un'implementazione di ricerca fuzzy attuale

Question

Attualmente sto lavorando per implementare una ricerca fuzzy per un servizio web terminologico e sto cercando suggerimenti su come migliorare l'implementazione corrente. È troppo codice da condividere, ma penso che una spiegazione potrebbe essere sufficiente per suggerire suggerimenti ponderati. Capisco che c'è molto da leggere ma apprezzerei qualsiasi aiuto.

In primo luogo, la terminologia è fondamentalmente solo un numero di nomi (o termini). Per ogni parola, la dividiamo in token per spazio e poi iteriamo attraverso ogni carattere per aggiungerlo al trie. Su un nodo terminale (come quando viene raggiunto il carattere y in fragola), archiviamo in un elenco un indice all'elenco dei termini principali. Quindi un nodo terminale può avere più indici (poiché il nodo terminale per fragola corrisponderà a "fragola" e "allergia a fragola").

Come per la ricerca effettiva, anche la query di ricerca viene suddivisa in token per spazio. L'algoritmo di ricerca viene eseguito per ogni token. Il primo carattere del token di ricerca deve essere una corrispondenza (quindi il traw non abbinerà mai la fragola). Dopodiché, passiamo attraverso i bambini di ciascun nodo successivo. Se c'è un bambino con un personaggio che corrisponde, continuiamo la ricerca con il prossimo carattere del token di ricerca. Se un bambino non corrisponde al carattere dato, guardiamo i bambini che usano il carattere corrente del token di ricerca (quindi non lo fanno avanzare). Questa è la parte fuzziness, quindi 'stwb' corrisponderà a 'fragola'.

Quando raggiungiamo la fine del token di ricerca, cercheremo attraverso il resto della struttura trie su quel nodo per ottenere tutte le potenziali corrispondenze (poiché gli indici all'elenco dei termini principali sono solo sui nodi terminali). Lo chiamiamo roll up. Archiviamo gli indici impostando il loro valore su un BitSet. Quindi, abbiamo semplicemente e i BitSet dai risultati di ogni risultato di token di ricerca. Quindi prendiamo, ad esempio, i primi 1000 o 5000 indici dai BitSet anded e troviamo i termini effettivi a cui corrispondono. Usiamo Levenshtein per segnare ogni termine e poi ordinare per punteggio per ottenere i nostri risultati finali.

Questo funziona abbastanza bene ed è piuttosto veloce. Ci sono oltre 390 nodi di nodi nell'albero e oltre 1,1 milioni di nomi di termini effettivi. Tuttavia, ci sono problemi con questo così com'è.

Ad esempio, la ricerca di "cat car" restituirà la cateterizzazione, quando non lo vogliamo (poiché la query di ricerca è composta da due parole, il risultato dovrebbe essere almeno due). Sarebbe abbastanza facile da controllare, ma non si cura di una situazione come la procedura di cateterizzazione, poiché si tratta di due parole. Idealmente, vorremmo che corrispondesse a qualcosa come la cateterizzazione cardiaca.

In base alla necessità di correggere ciò, abbiamo apportato alcune modifiche. Per uno, passiamo attraverso il trie in una ricerca di profondità/larghezza mista. Fondamentalmente andiamo in profondità per tutto il tempo in cui un personaggio corrisponde. Quei nodi secondari che non corrispondono vengono aggiunti a una coda di priorità. La coda di priorità è ordinata dalla distanza di modifica, che può essere calcolata durante la ricerca del trie (poiché se c'è una corrispondenza di carattere, la distanza rimane la stessa e in caso contrario aumenta di 1). In questo modo, otteniamo la distanza di modifica per ogni parola. Non usiamo più il BitSet. Invece, è una mappa dell'indice di un oggetto Terminfo. Questo oggetto memorizza l'indice della frase di interrogazione e il termine frase e il punteggio. Quindi, se la ricerca è "car cat" e un termine abbinato è "procedura di cateterizzazione", gli indici frase termine saranno 1 così come gli indici della frase di interrogazione. Per "cateterismo cardiaco" gli indici di frase termine saranno 1,2 come gli indici di frase di interrogazione. Come si può vedere, è molto semplice in seguito a guardare il conteggio degli indici frase termine e gli indici di query frase e se non sono almeno pari al conteggio ricerca di parola, si può essere scartata.

Dopo di che, si sommano le distanze di modifica delle parole, rimuovere le parole del termine che corrispondono l'indice frase termine, e contiamo le lettere rimanenti per ottenere la vera distanza di modifica.Ad esempio, se si abbinato il termine "allergia alle fragole" e la query di ricerca era "di paglia" si avrebbe un punteggio di 7 da fragole, allora devi usare l'indice frase termine di scartare le fragole dal termine, e basta contare "allergia a" (meno gli spazi) per ottenere il punteggio di 16.

Questo ci i risultati precisi ci aspettiamo ottiene. Tuttavia, è troppo lento. Dove prima potevamo ottenere 25-40 ms su una ricerca di parole, ora potrebbe essere anche mezzo secondo. È in gran parte da cose come l'istanziazione di oggetti TermInfo, usando operazioni .add(), operazioni .put() e il fatto che dobbiamo restituire un numero elevato di corrispondenze. Potremmo limitare ogni ricerca per restituire solo 1000 le partite, ma non c'è alcuna garanzia che i primi 1000 risultati per "auto" sarebbe partita qualsiasi dei primi 1000 risultati corrispondenti alla "gatto" (ricordate, ci sono più di 1.1. Milioni di termini).

Anche per una sola parola di query, come il gatto, abbiamo ancora bisogno di un gran numero di partite. Questo perché se cerchiamo "cat" la ricerca abbinerà auto e arrotolerà tutti i nodi terminali sotto di esso (che sarà molto). Tuttavia, se limitassimo il numero di risultati, darebbe troppo peso alle parole che iniziano con la query e non alla distanza di modifica. Quindi, le parole come la cateterizzazione sarebbero più probabili da includere rispetto a qualcosa come il cappotto.

Quindi, in sostanza, ci sono qualche idea su come potremmo gestire i problemi che la seconda implementazione fisso, ma senza tanto della velocità rallentano che ha introdotto? Posso includere del codice selezionato se potrebbe chiarire le cose ma non volevo pubblicare un gigantesco muro di codice.

Answer 1

Wow ... dura.

Bene perché non si implementa Lucene? È lo stato dell'arte migliore e attuale quando si tratta di problemi come il tuo afaik.

Tuttavia voglio condividere alcuni pensieri ...

La rudezza non è qualcosa di simile alla paglia * è piuttosto la digitazione errata di alcune parole. E ogni personaggio mancante/errato aggiunge 1 alla distanza.

In genere è molto, molto difficile avere corrispondenza parziale (caratteri jolly) e sfocatura allo stesso tempo!

La tokenizzazione è generalmente una buona idea.

Tutto dipende anche molto dai dati che ottieni. Ci sono errori di ortografia nei file di origine o solo nelle query di ricerca?

Ho visto alcune implementazioni piuttosto carini utilizzando alberi a intervallo multidimensionale.

Ma penso davvero che se si vuole ottenere tutto ciò di cui sopra è necessaria una combinazione molto carina di un set di grafici e un buon algoritmo di indicizzazione.

Si potrebbe ad esempio utilizzare un database semantico come sesamo e quando si importano i documenti, importare ogni token e documentare come nodo. Quindi, in base alla posizione nel documento, è possibile aggiungere una relazione ponderata.

Quindi sono necessari i token in alcune strutture in cui è possibile eseguire corrispondenze fuzzy efficienti come bk-trees. Penso che potresti indicizzare i token in un database mysql e fare funzioni di confronto bit-saggio per ottenere le differenze. C'è una funzione che restituisce tutti i bit corrispondenti, se si traducono le stringhe in ascii e si raggruppano i bit si potrebbe ottenere qualcosa abbastanza velocemente.

Tuttavia, se si abbinano i token alla stringa, è possibile costruire un'antichità di corrispondenza perfetta e interrogare il database semantico per i vicini più vicini.

È necessario suddividere le parole in parole parziali durante la tokenizzazione per ottenere corrispondenze parziali.

Tuttavia, è possibile eseguire anche le corrispondenze con caratteri jolly (prefisso, suffisso o entrambi), ma senza sfocatura.

È anche possibile indicizzare l'intera parola o diverse concatenazioni di token.

Tuttavia potrebbero esserci speciali implementazioni di bk-tree che supportano questo ma non ne ho mai visto uno.

Answer 2

ho fatto un certo numero di iterazioni di un correttore ortografico secoli fa, ed ecco una recent description del metodo di base. Fondamentalmente il dizionario delle parole corrette è in un trie, e la ricerca è un semplice branch-and-bound. Ho usato una ripetuta trie di profondità, prima delimitata da lev. distanza perché, dal momento che ogni incremento ulteriore dei risultati a distanza in modo molto più del trie che è camminata, il costo, per la piccola distanza, è sostanzialmente esponenziale in lontananza, in modo da andare ad una profondità di ricerca combinata/ampiezza non salva molto, ma lo rende molto più complicato.

(a parte: Sareste sorpresi di quanti modi i medici possono cercare di incantesimo "acido acetilsalicilico".)

Sono sorpresi dalle dimensioni del vostro trie. Un dizionario base di parole accettabili è forse qualche migliaio. Quindi ci sono prefissi e suffissi comuni. Poiché la struttura è un trie, puoi collegare insieme i sotto-tentativi e risparmiare molto spazio. Come il trie di prefissi di base può collegarsi al dizionario principale, e quindi i nodi terminali del dizionario principale può collegarsi al trie di suffissi comuni (che può effettivamente contenere cicli). In altre parole, il trie può essere generalizzato in una macchina a stati finiti. Questo ti dà molta flessibilità.

Indipendentemente da tutto ciò, si ha un problema di prestazioni. La cosa bella dei problemi di prestazioni è che, peggio, sono più facili da trovare. Sono stato un vero pidocchio su StackOverflow sottolineando questo. This link spiega come farlo, collega ad un esempio dettagliato e cerca di dissipare alcuni miti popolari. In poche parole, più tempo spendi facendo qualcosa che potresti ottimizzare, più probabilmente lo prenderai facendo se lo interrompi e dai un'occhiata. Il mio sospetto è che un sacco di tempo sta entrando in operazioni sulla struttura di dati esagerata, piuttosto che solo arrivare alla risposta. Questa è una situazione comune, ma non aggiustare nulla finché i campioni non ti indicano direttamente il problema.