Alla ricerca di parole simili

Sto provando a scrivere un modulo di controllo ortografico.Alla ricerca di parole simili

Carica un testo, crea un dizionario da 16 file MB e quindi verifica se la parola rilevata è simile alla parola nel dizionario (simile = varia fino a due caratteri), in caso affermativo lo modifica nel modulo dal dizionario.

In questo momento sto utilizzando un algoritmo Levenshtein distanza e l'elaborazione di un 50 parole set prende 3 min ...

Sono abbastanza sicuro che ci deve essere una soluzione più veloce. Profiler mi ha detto che la mia app spende oltre l'80% del tempo nella funzione Levenshtein Distance.

Esistono soluzioni/algoritmi migliori?

Ecco l'implementato della versione dell'algoritmo che uso:

def levenshteinDistance(s1, s2): 
    l_s1 = len(s1) 
    l_s2 = len(s2) 
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)] 
    for i in xrange(1, l_s1 + 1): 
     for j in xrange(1, l_s2 + 1): 
      d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1])) 
    return d[l_s1][l_s2]

fonte

2012-04-08 Michal

I suoni sono come "Correzione automatica" piuttosto che il controllo ortografico, poiché i correttori ortografici di solito creano opzioni e consentono agli utenti di scegliere tra di loro. La correzione automatica è ovviamente impossibile da fare, un fatto ormai quasi universalmente riconosciuto, anche negli spot televisivi. :-) –

Se si presuppone che la prima lettera della parola sia sempre corretta, è sufficiente controllare il dizionario per le parole che iniziano con quella lettera. Ridurrà il tuo tempo più o meno un fattore o 26 – Doboy

Non so molto su Python, ma la tua funzione di distanza usa la soluzione di programmazione dinamica standard. Ecco la mia versione in C++: http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings forse puoi notare qualche differenza. –

Ho usato il correttore ortografico di Norvig, citato nei commenti ed è impressionante.

Tuttavia, per quanto riguarda il problema, è stato scritto un Algoritmo di modifica della distanza di programmazione dinamica. Il tuo algoritmo si qualifica come un algoritmo di dati parallelo. Su una memoria condivisa, su una singola macchina, se si dispone di multi-core, è possibile sfruttarli. Sai qualcosa chiamato mappa-ridurre? Per favore non pensare distribuito e tutto bene ora, basta considerare un singolo computer quad core e una memoria condivisa. Come passo 1 è possibile partizionare il dizionario e allocare una porzione a ciascun thread che eseguirà la modifica della distanza su una porzione di dizionario (simile a un passo della mappa). Più tardi tutte le discussioni ti restituiranno tutte le parole a una distanza di modifica di 2 (simile a ridurre il passo). In questo modo il tuo programma trarrà vantaggio dall'architettura multi-core.

Un'altra cosa che potrei pensare è nel codice Python scrivere l'algoritmo di modifica della cpu in C i.e scrivendo un'estensione python.

fonte

2012-04-08 20:15:40 Yavar

Sfortunatamente non mi è permesso usare più core, ma la soluzione di Norvig ha fatto il trucco. – Michal

Forse il problema è a un livello più alto. Quando un profiler ti dice che un sacco di tempo è trascorso in una funzione, potrebbe essere che lo chiami troppo spesso. Stai forse confrontando ogni parola del testo con ogni parola del dizionario? Provalo al contrario: per le parole nel testo, genera direttamente parole di distanza < = 2 e controlla se sono nel dizionario.

fonte

2012-04-08 21:06:40

Hai ragione che a volte il problema riguarda troppe chiamate, ma non è il mio caso. Posso usare solo parole da un dizionario, ecco perché non ho bisogno di generare nuove parole, ma posso usare parole del dizionario che sono di distanza <= 2 dalla mia parola incontrata. Ma hai indicato alcune cose buone per altri casi. – Michal

Alla ricerca di parole simili

risposta

Problemi correlati