Precisava de uma maneira eficiente para a busca do seguinte requisito específico

Question

Eu tenho que procurar um determinado nome do arquivo (vamos dizer palavra-chave) em um diretório que contém arquivos. Se houvesse apenas algumas palavras-chave a ser pesquisado, eu poderia ter usado pesquisa regular (como a criação de uma matriz de nomes de arquivos que residem no diretório especificado e, em seguida, procurar o nome de cada arquivo com a palavra-chave dada). Desde que eu preciso procurar muito grande número de palavras-chave dinamicamente, não é eficiente para pesquisar usando regular. Eu tinha algumas idéias:

1.Using hashing (mas não está claro como a projetá-lo)

2.Using Bloom Filtros para a busca (por favor, google, se u não sei sobre isso, o seu trabalho é muito interessante!): Problema no uso de filtros Bloom é "Falsos positivos são possíveis, mas falsos negativos não são". Eu poderia perder alguns resultados ....

Answer 1

Antes de pesquisa, criar uma trie de todas as partidas positivos.

Criar a trie vai demorar O (n), onde n é o número de palavras.

Para pesquisar, tentar igualar a palavra contra o trie. Look-ups são feitos em O (m) onde m é a comprimento da palavra para look-up.

total de tempo de execução:. O (n + nm) => S (nm) para encontrar todas as palavras