Necessario un modo efficiente per la ricerca per il seguente requisito specfic

Question

Devo cercare un determinato nome di file (per non dire di parola chiave) in una directory contenente i file. Se ci fossero solo poche parole chiave da ricercare, avrei potuto usare ricerca normale (come la creazione di una serie di nomi di file che risiedono nella directory specificata e quindi cercare ogni nome di file con la parola data). Dal momento che ho bisogno di cercare molto elevato numero di parole chiave in modo dinamico, non è efficiente per la ricerca utilizzando normale. Ho avuto paio di idee:

1.Utilizzando hashing (ma non è chiaro come disegnarlo)

Filtri 2.Tramite Bloom per la ricerca (si prega di google, se u non sa a questo proposito, il suo funzionamento è molto interessante!): Problema nell'uso di filtri di fioritura è "falsi positivi sono possibili, ma i falsi negativi non sono". Potrei perdere qualche risultato ....

Answer 1

Prima di cercare, creare un trie di tutte le partite positive.

Creazione del trie prenderà O (n), dove n è il numero di parole.

Per effettuare la ricerca, cercare di abbinare la parola contro il trie. Look-up sono fatti in O (m) dove m è la lunghezza della parola di look-up.

Tempo totale:. O (n + nm) => O (nm) per trovare tutte le parole