Il modo più efficace per trovare corrispondenze parziali di stringhe in file di grandi dimensioni (python)

Question

Ho scaricato il file dei titoli degli articoli di Wikipedia che contiene il nome di ogni articolo di Wikipedia. Devo cercare tutti i titoli degli articoli che potrebbero essere una possibile corrispondenza. Per esempio, potrei avere la parola "hockey", ma l'articolo di Wikipedia per l'hockey che vorrei fosse "Ice_hockey". Dovrebbe essere una ricerca senza distinzione tra maiuscole e minuscole.

Sto usando Python e c'è un modo più efficiente di eseguire una ricerca riga per riga? Effettuerò questa ricerca idealmente come 500 o 1000 volte al minuto. Se linea per linea è la mia unica opzione, ci sono alcune ottimizzazioni che posso fare all'interno di questo?

Penso che ci siano diversi milioni di righe nel file.

Qualche idea?

Grazie.

Answer 1

La risposta di Greg è buona se si desidera abbinare le singole parole. Se vuoi abbinare le sottostringhe avrai bisogno di qualcosa di un po 'più complicato, come un albero di suffisso (http://en.wikipedia.org/wiki/Suffix_tree). Una volta costruito, un albero di suffisso può rispondere in modo efficiente alle sottostringhe arbitrarie, così nel tuo esempio potrebbe corrispondere a "Ice_Hockey" quando qualcuno cerca "hock".

Answer 2

Se si dispone di un set di dati fisso e di query variabili, la tecnica usuale consiste nel riorganizzare il set di dati in qualcosa che può essere ricercato più facilmente. A livello astratto, è possibile suddividere ogni titolo dell'articolo in singole parole minuscole e aggiungerle a una struttura di dati del dizionario Python. Quindi, ogni volta che ottieni una query, converti la query in minuscolo e cerca nel dizionario. Se ciascun valore di voce del dizionario è un elenco di titoli, è possibile trovare facilmente tutti i titoli che corrispondono a una determinata parola di query.

Questo funziona per parole semplici, ma è necessario considerare se si desidera eseguire corrispondenze su parole simili, come trovare "fumo" quando la query è "fumo".

Answer 3

Suggerirei di inserire i dati in un database SQLite e utilizzare l'operatore "Mi piace" SQL per le ricerche.