Accelerare levenshtein/similar_text in PHP

Question

Attualmente sto usando similar_text per confrontare una stringa con un elenco di ~ 50.000 che funziona anche se a causa del numero di confronti è molto lento. Ci vogliono circa 11 minuti per confrontare ~ 500 stringhe uniche.

Prima di eseguirlo, controllo i database per vedere se è stato elaborato in passato, quindi ogni volta dopo la prima esecuzione è vicino all'istante.

Sono sicuro che usare levenshtein sarebbe leggermente più veloce e la funzione LevenshteinDistance che qualcuno ha pubblicato nel manuale sembra interessante. Mi manca qualcosa che potrebbe renderlo significativamente più veloce?

Answer 1

Alla fine, sia levenshtein sia similar_text erano entrambi troppo lenti con il numero di stringhe che doveva attraversare, anche con molti controlli e usandoli solo uno di loro come ultima risorsa.

Come esperimento, ho portato un po 'del codice in C# per vedere quanto sarebbe stato più veloce su un codice interperato. Ha funzionato in circa 3 minuti con lo stesso set di dati.

Successivamente ho aggiunto un campo aggiuntivo alla tabella e ho utilizzato l'estensione PECL a doppio metaphone per generare le chiavi per ogni riga. I risultati sono stati buoni anche se, dal momento che alcuni numeri inclusi hanno causato duplicati. Immagino che avrei potuto eseguire ognuno di loro attraverso le funzioni di cui sopra ma ho deciso di non farlo.

Alla fine ho optato per l'approccio più semplice, il testo completo di MySQL che ha funzionato molto bene. Occasionalmente ci sono errori anche se sono facili da individuare e correggere. Inoltre funziona molto velocemente, in circa 3-4 secondi.

Answer 2

Forse si potrebbero "cortocircuitare" alcuni controlli confrontando prima la stringa per una corrispondenza esatta (e prima confrontando se la lunghezza è identica), e se si salta la più costosa chiamata similar_text.

Come ha osservato @jason, un algoritmo O (N^3) non sarà mai una buona scelta.

Answer 3

Quando si utilizza levenshtein automa (automa che corrisponde a una stringa con la distanza k) si può fare un controllo per la corrispondenza in O(n), dove n è la lunghezza della stringa che si sta verificando. La costruzione dell'automa richiederà O(kn), dove k è la distanza massima e la lunghezza della stringa di base è n.