Quelle est la meilleure façon de faire une recherche dans un fichier volumineux?

Question

Je souhaite appliquer une recherche KMP (ou similaire) à un fichier volumineux (> 4 Go).

Je m'attends à ce que cela me pose cependant des problèmes. Je ne peux pas tout copier en mémoire car il n'y a pas assez d'espace disponible ici.

Ma question est la suivante: quelle est la meilleure façon de faire cette recherche? Dois-je simplement créer un FICHIER * et effectuer la recherche directement dans le fichier, dois-je copier des blocs (disons 4k) dans la mémoire et les rechercher, ou quelque chose de plus?

Answer 1

Si vous utilisez une plate-forme qui la prend en charge, vous pouvez utiliser mmap (). La pagination du fichier est également une possibilité, mais n'oubliez pas de garder la mémoire tampon la plus grande possible pour réduire le surcoût d'IO et de faire attention aux limites de deux pages (supposons qu'une chaîne corresponde, mais est scindée par la limite de la page)

Sinon, je vous suggère de créer un index quelconque et d'utiliser l'index pour restreindre la recherche. La recherche KMP n'est pas particulièrement efficace. Cela dépend bien sûr de la nature de votre fichier, de la manière dont il est créé, etc.

Answer 2

Pour l'accès aux fichiers, je vous recommande d'utiliser un fichier mappé en mémoire pour éviter la copie de données. C'est trivial sur les machines Unix. Vous devrez peut-être diviser le mappage de fichiers en blocs plus petits s'il ne peut pas être alloué en un seul bloc. Je peux fournir du code si cela vous intéresse.

Pour la recherche, je vous recommande d'utiliser Boyer un algorithme de recherche plus complet .

Answer 3

La recherche directe dans le fichier serait très lente, l’utilisation de la mise en mémoire tampon donnerait de bien meilleures performances. Mais notez que votre tampon doit être plus grand que ce que vous recherchez ( SearchLength ), bien sûr, et vous devez l'actualiser lorsque SearchLength octets avant sa fin. / p>

Answer 4

La meilleure approche consiste à le lire par blocs et à le rechercher. Vous devez définir la taille de bloc comme un paramètre afin de pouvoir expérimenter ce qui offre les meilleures performances.

Cependant, il est généralement plus efficace d’essayer d’indexer le fichier de façon à ne pas avoir à effectuer de recherche linéaire dans l’ensemble du fichier. Par exemple, KMP est un algorithme de recherche de chaîne. Cherchez-vous simplement l'occurrence d'un mot? Ensuite, vous pouvez simplement créer une table de hachage (sur disque) des mots et leur emplacement dans le fichier pour une recherche très efficace.