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

Je cherche à appliquer une recherche KMP (ou similaire) à un gros fichier (> 4 Go).Quelle est la meilleure façon de faire une recherche dans un fichier volumineux?

Je m'attends à ce que cela me pose problème. Je ne peux pas tout copier en mémoire car il n'y a pas assez d'espace là-bas.

Ma question est, quelle est la meilleure façon de faire cette recherche? Devrais-je simplement créer un FICHIER * et faire la recherche directement dans le fichier, devrais-je copier des blocs (disons 4k) en mémoire et les chercher, ou quelque chose d'autre complètement?

Source

2009-07-31 samoz

Si vous utilisez une plateforme qui le prend en charge, vous pouvez utiliser mmap(). La pagination du fichier est également une possibilité, mais n'oubliez pas de conserver le tampon le plus grand possible pour réduire le temps système des E/S et de faire attention aux limites de deux pages (supposons qu'une chaîne correspond, mais est divisée Alternativement, je vous suggère de construire un index de quelque sorte, 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, comment il est créé, etc.

Source

2009-07-31 12:41:47

+1 pour l'utilisation de mmap. Il faut juste noter que vous aurez toujours besoin de mmap dans les blocs, sur les machines 32 bits, car l'espace d'adressage ne suffit pas. – tsg

Oui, mmap (au moins sur OSX, mais c'est BSD stardard) accepte size_t len et off_t offset. L'OP doit vérifier si ces types contiennent des valeurs de 64 bits, sinon il ne pourra jamais dépasser la limite de 4 Gio. –

La recherche directe 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 être plus grand que ce que vous recherchez (SearchLength), bien sûr, et vous devez rafraîchir le tampon lorsqu'il est SearchLength octets avant sa fin.

Source

2009-07-31 12:29:45 schnaader

La meilleure approche est de le lire en blocs et de le rechercher. Vous devriez faire de la taille de bloc un paramètre, de sorte que vous puissiez expérimenter avec ce qui donne les meilleures performances.

Cependant, il est généralement plus efficace d'essayer d'indexer le fichier d'une manière ou d'une autre, de sorte que vous n'avez pas besoin de faire une recherche linéaire dans tout le fichier. Par exemple, KMP est un algorithme de recherche de chaîne - recherchez-vous simplement les occurrences d'un mot? Ensuite, vous pouvez simplement créer une table de hachage (sur disque) des mots et leur emplacement dans le fichier et avoir une recherche très efficace.

Source

2009-07-31 12:30:02

Eh bien, j'essaie de faire une recherche pour toutes les occurrences d'une chaîne hexadécimale dans un fichier fourni par l'utilisateur. Puisque le fichier sera différent à chaque fois et que je cherche des valeurs hexadécimales, les tables de hachage semblent ne pas valoir le coût. – samoz

C'est vrai, c'est pourquoi j'ai dit "habituellement" :) Chaque problème de recherche est quelque peu différent. Je préconiserais simplement la pagination, mais encore une fois, toujours utiliser les paramètres afin que vous puissiez régler les paramètres de votre configuration particulière. –

Pour l'accès au fichier, je 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 scinder le mappage de fichier en blocs plus petits s'il ne peut pas être alloué dans un bloc. Je peux fournir du code si vous êtes intéressé.

Pour la recherche, je recommanderais d'utiliser le Boyer More search algorithm.

Source

2009-07-31 12:48:43 chmike

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

Répondre

Questions connexes