Se necesita una manera eficiente de búsqueda del siguiente requisito specfic

Question

Tengo que buscar un nombre de archivo dado (por no decir palabra clave) en un directorio que contiene los archivos. Si sólo había pocas palabras clave para buscar, podría haber usado de búsqueda normal (como la creación de una matriz de nombres de archivos que residen en el directorio especificado y luego buscar el nombre de cada archivo con la palabra clave dada). Desde que necesita para buscar gran número de palabras clave de forma dinámica, no es eficiente para buscar usando regular. Tenía par de ideas:

1.Using hash (pero no está claro cómo diseñarlo)

Filtros 2.Using Bloom para la búsqueda (por favor, Google, si u no sabe sobre él, su trabajo es muy interesante!): Problema en el uso de filtros Bloom es "Los falsos positivos son posibles, pero no son falsos negativos". Podría pasar por alto algunos resultados ....

Answer 1

Antes de buscar, crear un trie de todas las coincidencias positivas.

Crear el trie se llevará a O (n), donde n es el número de palabras.

Para buscar, tratar de igualar la palabra contra el trie. Look-ups se realizan en O (m) donde m es el longitud de la palabra a buscar arriba.

tiempo de ejecución total:. O (n + nm) => O (nm) para encontrar todas las palabras