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

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

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

Ma question est, quelle est la meilleure façon de faire cette recherche? Devrais-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?

    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 qu’elle soit séparée par la limite de page)

    Sinon, je vous suggère de construire un index quelconque et de l’utiliser 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.

    Pour l’access au fichier, je vous recommande d’utiliser un fichier mappé en mémoire pour éviter la copie de données. C’est sortingvial 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 recommanderais d’utiliser l’ algorithme de recherche Boyer More .

    La recherche directement dans le fichier serait très lente. L’utilisation de la mise en mémoire tampon donnera de bien meilleures performances. Mais notez que votre tampon doit évidemment être plus grand que ce que vous recherchez ( SearchLength ) et que vous devez l’actualiser lorsque vous SearchLength avant sa fin.

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

    Cependant, il est généralement plus efficace d’essayer d’indexer le fichier de manière à 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.