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. Sono necessari circa 11 minuti per confrontare ~ 500 stringhe uniche.

Prima di eseguirlo, controllo i database per vedere se è stato elaborato in passato, quindi ogni volta che l'esecuzione iniziale è quasi istantanea.

Sono sicuro che l'utilizzo di levenshtein sarebbe leggermente più veloce e Levenshtein Funzione di distanza che qualcuno ha pubblicato nel manuale sembra interessante. Mi sto perdendo qualcosa che potrebbe renderlo significativamente più veloce?

Answer 1

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

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

Successivamente ho aggiunto un campo in più alla tabella e ho usato l'estensione PECL a doppio metafono per generare le chiavi per ogni riga. I risultati sono stati buoni anche se da alcuni numeri inclusi questo ha causato duplicati. Immagino che avrei potuto eseguire ognuna delle funzioni precedenti 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 sebbene siano facili da rilevare e correggere. Inoltre, funziona molto velocemente, in circa 3-4 secondi.

Answer 2

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

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

Answer 3

Quando si utilizza l'automa levenshtein (automa che corrisponde a una stringa con distanza k ) è possibile verificare la corrispondenza in O (n) , dove n è la lunghezza della stringa che stai controllando. La costruzione dell'automa richiederà O (kn) , dove k è la distanza massima e n la lunghezza della stringa di base.