Avait besoin d'un moyen efficace pour la recherche de l'exigence specfic suivante

Question

Je dois rechercher un nom de fichier donné (sans dire les mots-clés) dans un fichier contenant le répertoire. S'il n'y avait que quelques mots-clés à rechercher, je aurais pu utiliser la recherche régulière (comme la création d'un tableau de noms de fichiers résidant dans le répertoire spécifié puis recherchez chaque nom de fichier avec le mot-clé donné). Depuis que je dois chercher très grand nombre de mots-clés dynamiquement, ce ne est pas efficace de recherche à l'aide régulière. J'ai eu quelques idées:

hashing 1.En (mais pas clairement comment concevoir)

Filtres 2.Grâce Bloom pour la recherche (google s'il vous plaît, si u ne sais pas à ce sujet, son travail est très intéressant!): Problème dans l'utilisation de filtres bloom est « faux positifs sont possibles, mais faux négatifs ne sont pas ». Je pourrais manquer des résultats ....

Answer 1

Avant de rechercher, créer un de Trie tous les matchs positifs.

Création du Trie prendra O (n) où n est le nombre de mots.

Pour rechercher, essayer de faire correspondre le mot contre la Trie. Look-ups se font en O (m) où m est le longueur du mot consultation.

Durée d'exécution totale:. O (n + nm) => O (nm) pour trouver tous les mots