J'ai un gros fichier binaire (1 MB < taille < 50 MB). J'ai besoin de rechercher une chaîne et d'extraire les quatre octets suivants (qui est la {taille, décalage} des données réelles dans un autre fichier). Quel est le moyen le plus efficace de le faire pour que la recherche soit la plus rapide?Recherche de chaînes dans de gros fichiers binaires
EDIT: Les chaînes des fichiers d'index sont triées.
Enregistrez les tuples {chaîne, taille, décalage} dans l'ordre trié (par chaîne) et utilisez une recherche binaire pour la chaîne.
Vous pouvez également stocker, au début du fichier, des décalages pour chaque première lettre de chaînes. Par exemple, si les chaînes commençant par 'a' commencent à la position 120 et celles commençant par 'b' commencent à la position 2000 dans le fichier, vous pouvez démarrer le fichier avec 120, 2000, ...
Si le codage est fixe (ASCII), il est relativement simple. Ouvrir un flux binaire, lire un octet pour un octet et correspondre au premier caractère de la chaîne cible.
Si vous avez des chaînes utilisant un autre codage (UTF-8), cela devient plus compliqué.
Y at-il une API .NET pour cela? – blitzkriegz
Rechercher le Boyer–Moore string search algorithm.
Malheureusement, il ne semble pas que Boyer-Moore vaille la peine d'être implémenté en C#. Consultez http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore. –
@Jonathan Wood: Pas si vous pouvez charger le fichier entier en mémoire et utiliser 'IndexOf'. Mais pour les données streamées, .NET ne fournit pas un moyen de recherche, et Boyer-Moore est l'algorithme recommandé à utiliser dans ce cas. – Groo
@Groo: Cela semble intéressant. Soin d'écrire un autre article pour [Black Belt Coder] (http://www.blackbeltcoder.com)? :-) –
D'abord, utilisez le mappage de la mémoire sur le fichier. Ce sera beaucoup plus efficace que de le lire dans la RAM car au lieu de deux copies (une dans votre programme et une dans le cache de fichiers), il n'y a qu'une seule copie.
Si chaque chaîne a une longueur fixe, une recherche binaire est très simple car vous pouvez traiter la mémoire comme un tableau de tableaux de caractères. Si chaque chaîne est de longueur variable mais 0 terminée, vous pouvez utiliser une variante de recherche binaire où vous passez au milieu de la liste de chaînes, recherchez le 0 suivant, puis testez la chaîne suivante après cela. Puis sautez en avant ou en arrière à 1/4 ou 3/4 de la liste de cordes et répétez.
Si chaque chaîne est de longueur variable dans le style Pascal, avec un nombre d'octets au début, c'est plus délicat. Une recherche linéaire depuis le début n'est pas trop lente, pour des recherches peu fréquentes. Si vous recherchez des correspondances exactes, n'oubliez pas que vous pouvez passer la plupart des chaînes en vérifiant que les longueurs ne correspondent pas.
Si vous devez souvent effectuer une recherche dans la liste, la construction d'un tableau de pointeurs char dans la liste des chaînes rendra la recherche binaire encore plus facile. Si ce fichier est vraiment un fichier d'index pour les recherches rapides, il l'a probablement déjà quelque part, à moins que le concepteur ait eu l'intention de construire un tableau de pointeurs char lors du chargement du fichier.
Comment faire pour mapper la mémoire en C#? – devnull
J'avais rencontré une situation similaire. Chaîne classique utilisée recherchant le caractère par caractère (en supposant ASCII). Puisque vous avez déjà un fichier d'index, je ne pense pas que vous puissiez améliorer les performances. – blitzkriegz