Quel est l'algorithme de recherche de sous-chaîne le plus rapide?

OK, donc je n'ai pas l'air d'un idiot, je vais énoncer le problème / les exigences plus explicitement:

• L'aiguille (motif) et la botte de foin (texte à rechercher) sont toutes deux des chaînes de style C à terminaison nulle. Aucune information de longueur n'est fournie; si nécessaire, il doit être calculé.
• La fonction doit renvoyer un pointeur sur la première correspondance ou NULLsi aucune correspondance n'est trouvée.
• Les cas d'échec ne sont pas autorisés. Cela signifie que tout algorithme avec des exigences de stockage non constantes (ou grandes constantes) devra avoir un cas de secours en cas d'échec d'allocation (et les performances dans le traitement de secours contribuent ainsi aux performances les plus défavorables).
• L'implémentation doit être en C, bien qu'une bonne description de l'algorithme (ou un lien vers un tel algorithme) sans code convienne également.

... ainsi que ce que j'entends par «plus rapide»:

• Déterministe O(n)où n= longueur de la botte de foin. (Mais il peut être possible d'utiliser des idées d'algorithmes qui sont normalement O(nm)(par exemple, le hachage roulant) s'ils sont combinés avec un algorithme plus robuste pour donner des O(n)résultats déterministes ).
• Ne fonctionne jamais (de manière mesurable; quelques horloges pour if (!needle[1])etc. sont bien) pire que l'algorithme de force brute naïve, en particulier sur des aiguilles très courtes qui sont probablement le cas le plus courant. (Les frais généraux de prétraitement lourds inconditionnels sont mauvais, tout comme essayer d'améliorer le coefficient linéaire pour les aiguilles pathologiques au détriment des aiguilles probables.)
• Avec une aiguille et une botte de foin arbitraires, des performances comparables ou meilleures (pas moins de 50% de temps de recherche plus long) par rapport à tout autre algorithme largement implémenté.
• En dehors de ces conditions, je laisse ouverte la définition de «plus rapide». Une bonne réponse devrait expliquer pourquoi vous considérez l'approche que vous suggérez comme «la plus rapide».

Mon implémentation actuelle est à peu près 10% plus lente et 8 fois plus rapide (selon l'entrée) que l'implémentation de la glibc de Two-Way.

Mise à jour: Mon algorithme optimal actuel est le suivant:

• Pour les aiguilles de longueur 1, utilisez strchr.
• Pour les aiguilles d'une longueur de 2 à 4, utilisez des mots machine pour comparer 2 à 4 octets à la fois comme suit: préchargez l'aiguille dans un entier de 16 ou 32 bits avec décalages de bits et faites défiler l'ancien octet / les nouveaux octets à partir de la botte de foin à chaque itération . Chaque octet de la meule de foin est lu exactement une fois et subit une vérification par rapport à 0 (fin de chaîne) et une comparaison 16 ou 32 bits.
• Pour les aiguilles de longueur> 4, utilisez l'algorithme bidirectionnel avec une mauvaise table de décalage (comme Boyer-Moore) qui n'est appliquée qu'au dernier octet de la fenêtre. Pour éviter la surcharge de l'initialisation d'une table de 1 ko, ce qui serait une perte nette pour de nombreuses aiguilles de longueur moyenne, je garde un tableau de bits (32 octets) marquant les entrées de la table de décalage qui sont initialisées. Les bits non définis correspondent à des valeurs d'octets qui n'apparaissent jamais dans l'aiguille, pour lesquelles un décalage complet de la longueur de l'aiguille est possible.

Les grandes questions qui restent dans mon esprit sont:

• Existe-t-il un moyen de mieux utiliser la mauvaise table de travail? Boyer-Moore en fait le meilleur usage en balayant vers l'arrière (de droite à gauche), mais bidirectionnel nécessite un balayage de gauche à droite.
• Les deux seuls algorithmes candidats viables que j'ai trouvés pour le cas général (pas de mémoire insuffisante ou de conditions de performances quadratiques) sont la correspondance bidirectionnelle et de chaîne sur les alphabets ordonnés . Mais existe-t-il des cas facilement détectables où différents algorithmes seraient optimaux? Il est certain que beaucoup d' algorithmes spatiaux O(m)(où mest la longueur de l'aiguille) pourraient être utilisés pour m<100environ. Il serait également possible d'utiliser des algorithmes qui sont quadratiques dans le pire des cas s'il existe un test facile pour les aiguilles qui ne nécessitent que du temps linéaire.

Points bonus pour:

• Pouvez-vous améliorer les performances en supposant que l'aiguille et la botte de foin sont toutes deux bien formées en UTF-8? (Avec des caractères de longueurs d'octets variables, la bonne forme impose certaines exigences d'alignement des chaînes entre l'aiguille et la botte de foin et permet des décalages automatiques de 2 à 4 octets lorsqu'un octet de tête incompatible est rencontré. Mais ces contraintes vous achètent-elles beaucoup / rien au-delà de ce les calculs de suffixes maximaux, les bons décalages de suffixes, etc. vous donnent déjà divers algorithmes?)

Remarque: je connais bien la plupart des algorithmes, mais pas leur performance dans la pratique. Voici une bonne référence pour que les gens ne continuent pas à me donner des références sur les algorithmes sous forme de commentaires / réponses: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Construisez une bibliothèque de test d'aiguilles et de meules de foin probables. Profil des tests sur plusieurs algorithmes de recherche, y compris la force brute. Choisissez celui qui fonctionne le mieux avec vos données.

Boyer-Moore utilise une mauvaise table de caractères avec une bonne table de suffixes.

Boyer-Moore-Horspool utilise une mauvaise table de caractères.

Knuth-Morris-Pratt utilise une table de correspondance partielle.

Rabin-Karp utilise des hachages en cours d'exécution.

Ils échangent tous des frais généraux pour des comparaisons réduites à un degré différent, de sorte que la performance réelle dépendra des longueurs moyennes de l'aiguille et de la botte de foin. Plus la surcharge initiale est élevée, mieux c'est avec des entrées plus longues. Avec des aiguilles très courtes, la force brute peut gagner.

Éditer:

Un algorithme différent peut être le meilleur pour trouver des paires de bases, des phrases anglaises ou des mots simples. S'il y avait un meilleur algorithme pour toutes les entrées, il aurait été rendu public.

Pensez au petit tableau suivant. Chaque point d'interrogation peut avoir un meilleur algorithme de recherche différent.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

Cela devrait vraiment être un graphique, avec une plage d'entrées plus courtes à plus longues sur chaque axe. Si vous traciez chaque algorithme sur un tel graphique, chacun aurait une signature différente. Certains algorithmes souffrent de nombreuses répétitions dans le modèle, ce qui pourrait affecter des utilisations telles que la recherche de gènes. Certains autres facteurs qui affectent les performances globales recherchent plusieurs fois le même modèle et recherchent différents modèles en même temps.

Si j'avais besoin d'un ensemble d'échantillons, je pense que je gratterais un site comme google ou wikipedia, puis supprimerais le code HTML de toutes les pages de résultats. Pour un site de recherche, saisissez un mot, puis utilisez l'une des expressions de recherche suggérées. Choisissez quelques langues différentes, le cas échéant. En utilisant des pages Web, tous les textes seraient courts à moyens, alors fusionnez suffisamment de pages pour obtenir des textes plus longs. Vous pouvez également trouver des livres du domaine public, des documents juridiques et d'autres grands corps de texte. Ou générez simplement du contenu aléatoire en choisissant des mots dans un dictionnaire. Mais le but du profilage est de tester par rapport au type de contenu que vous rechercherez, utilisez donc des échantillons du monde réel si possible.

J'ai laissé court et long vague. Pour l'aiguille, je pense que court comme moins de 8 caractères, moyen comme moins de 64 caractères et long comme moins de 1k. Pour la botte de foin, je pense à court comme sous 2 ^ 10, moyen comme sous 2 ^ 20 et long jusqu'à 2 ^ 30 caractères.

Publié en 2011, je pense qu'il s'agit peut-être de l' algorithme "Simple Real-Time Constant-Space String Matching" de Dany Breslauer, Roberto Grossi et Filippo Mignosi.

Mettre à jour:

En 2014, les auteurs ont publié cette amélioration: Vers une correspondance optimale des chaînes compactées .

Le lien http://www-igm.univ-mlv.fr/~lecroq/string/index.html vers lequel vous pointez est une excellente source et un résumé de certains des algorithmes de correspondance de chaînes les plus connus et les plus étudiés.

Les solutions à la plupart des problèmes de recherche impliquent des compromis en ce qui concerne les frais généraux, le temps et l'espace de pré-traitement. Aucun algorithme unique ne sera optimal ou pratique dans tous les cas.

Si votre objectif est de concevoir un algorithme spécifique pour la recherche de chaînes, ignorez le reste de ce que j'ai à dire.Si vous souhaitez développer une routine de service de recherche de chaînes généralisée, essayez ce qui suit:

Passez du temps à examiner les forces et les faiblesses spécifiques des algorithmes que vous avez déjà référencés. Effectuez la révision dans le but de trouver un ensemble d'algorithmes qui couvrent la plage et la portée des recherches de chaînes qui vous intéressent. Ensuite, créez un sélecteur de recherche frontale basé sur une fonction de classificateur pour cibler le meilleur algorithme pour les entrées données. De cette façon, vous pouvez utiliser l'algorithme le plus efficace pour faire le travail. Ceci est particulièrement efficace lorsqu'un algorithme est très bon pour certaines recherches mais se dégrade mal. Par exemple, la force brute est probablement la meilleure pour les aiguilles de longueur 1 mais se dégrade rapidement lorsque la longueur de l'aiguille augmente, après quoi l' algoritim sustik-moorepeut devenir plus efficace (sur de petits alphabets), alors pour des aiguilles plus longues et des alphabets plus grands, les algorithmes KMP ou Boyer-Moore peuvent être meilleurs. Ce ne sont que des exemples pour illustrer une stratégie possible.

L'approche multi-algorithmes n'est pas une idée nouvelle. Je crois qu'il a été utilisé par quelques packages commerciaux de tri / recherche (par exemple, SYNCSORT couramment utilisé sur les mainframes implémente plusieurs algorithmes de tri et utilise l'heuristique pour choisir le "meilleur" pour les entrées données)

Chaque algorithme de recherche se décline en plusieurs variantes qui peuvent faire des différences significatives dans ses performances, comme l'illustre, par exemple, cet article .

Analysez votre service pour classer les domaines dans lesquels des stratégies de recherche supplémentaires sont nécessaires ou pour affiner plus efficacement votre fonction de sélection. Cette approche n'est ni rapide ni facile, mais si elle est bien faite, elle peut produire de très bons résultats.

J'ai été surpris de voir notre rapport technique cité dans cette discussion; Je suis l'un des auteurs de l'algorithme qui a été nommé Sustik-Moore ci-dessus. (Nous n'avons pas utilisé ce terme dans notre article.)

Je voulais ici souligner que pour moi la caractéristique la plus intéressante de l'algorithme est qu'il est assez simple de prouver que chaque lettre est examinée au plus une fois. Pour les versions antérieures de Boyer-Moore, ils ont prouvé que chaque lettre est examinée au plus 3 fois et plus tard 2 fois au plus, et ces preuves étaient plus impliquées (voir les citations dans le papier). Par conséquent, je vois également une valeur didactique à présenter / étudier cette variante.

Dans l'article, nous décrivons également d'autres variantes qui visent l'efficacité tout en assouplissant les garanties théoriques. C'est un article court et le matériel devrait être compréhensible pour un diplômé moyen du secondaire à mon avis.

Notre objectif principal était de porter cette version à l'attention d'autres personnes susceptibles de l'améliorer. La recherche de chaînes a tellement de variations et nous ne pouvons pas à eux seuls penser à tous les domaines où cette idée pourrait apporter des avantages. (Texte fixe et motif changeant, modèle différent de texte fixe, prétraitement possible / impossible, exécution parallèle, recherche de sous-ensembles correspondants dans de grands textes, autoriser les erreurs, les correspondances proches, etc., etc.)

L'algorithme de recherche de sous-chaîne le plus rapide dépendra du contexte:

1. la taille de l'alphabet (par exemple ADN vs anglais)
2. la longueur de l'aiguille

L'article de 2010 "Le problème exact de la correspondance de chaînes: une évaluation expérimentale complète" donne des tableaux avec des temps d'exécution pour 51 algorithmes (avec différentes tailles d'alphabet et différentes longueurs d'aiguille), afin que vous puissiez choisir le meilleur algorithme pour votre contexte.

Tous ces algorithmes ont des implémentations C, ainsi qu'une suite de tests, ici:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Une très bonne question. Ajoutez juste quelques petits morceaux ...

1. Quelqu'un parlait de correspondance des séquences d'ADN. Mais pour la séquence d'ADN, ce que nous faisons généralement est de construire une structure de données (par exemple, un tableau de suffixes, un arbre de suffixes ou un index FM) pour la botte de foin et de faire correspondre de nombreuses aiguilles. C'est une autre question.

2. Ce serait vraiment génial si quelqu'un souhaitait comparer divers algorithmes. Il existe de très bons benchmarks sur la compression et la construction de tableaux de suffixes, mais je n'ai pas vu de benchmark sur la correspondance de chaînes. Les candidats potentiels pour les meules de foin pourraient provenir de la référence SACA .

3. Il y a quelques jours, je testais l' implémentation Boyer-Moore à partir de la page que vous recommandiez (EDIT: j'ai besoin d'un appel de fonction comme memmem (), mais ce n'est pas une fonction standard, j'ai donc décidé de l'implémenter). Mon programme d'analyse comparative utilise des meules de foin aléatoires. Il semble que l'implémentation de Boyer-Moore dans cette page soit fois plus rapide que memmem () de la glibc et strnstr () de Mac. Au cas où vous seriez intéressé, l'implémentation est ici et le code de benchmarking est ici . Ce n'est certainement pas une référence réaliste, mais c'est un début.

Je sais que c'est une vieille question, mais la plupart des mauvaises tables de décalage sont à caractère unique. Si cela a du sens pour votre jeu de données (par exemple, surtout s'il s'agit de mots écrits), et si vous avez l'espace disponible, vous pouvez obtenir une accélération spectaculaire en utilisant une mauvaise table de décalage faite de n-grammes plutôt que de caractères uniques.

Utilisez stdlib strstr:

char *foundit = strstr(haystack, needle);

C'était très rapide, il ne m'a fallu qu'environ 5 secondes pour taper.

Voici l' implémentation de recherche de Python , utilisée dans tout le noyau. Les commentaires indiquent qu'il utilise une table delta 1 boyer-moore compressée .

J'ai moi-même fait une expérimentation assez approfondie de la recherche de chaînes, mais c'était pour plusieurs chaînes de recherche. Les implémentations d'assemblage de Horspool et Bitap peuvent souvent se défendre contre des algorithmes comme Aho-Corasick pour un faible nombre de motifs.

Un strchralgorithme plus rapide de «recherche d'un seul caractère correspondant» (ala ).

Notes IMPORTANTES:

• Ces fonctions utilisent un gcccompilateur "nombre / nombre de zéros (de début | de fin)" intrinsèque __builtin_ctz. Ces fonctions ne seront probablement rapides que sur les machines qui ont une ou plusieurs instructions qui effectuent cette opération (c'est-à-dire x86, ppc, arm).

• Ces fonctions supposent que l'architecture cible peut effectuer des charges non alignées 32 et 64 bits. Si votre architecture cible ne prend pas en charge cela, vous devrez ajouter une logique de démarrage pour aligner correctement les lectures.

• Ces fonctions sont indépendantes du processeur. Si le processeur cible a des instructions vectorielles, vous pourrez peut-être faire (beaucoup) mieux. Par exemple, la strlenfonction ci-dessous utilise SSE3 et peut être modifiée de manière triviale en XOR les octets analysés pour rechercher un octet autre que 0. Benchmarks effectués sur un ordinateur portable 2,66 GHz Core 2 exécutant Mac OS X 10.6 (x86_64):

  • 843.433 Mo / s pour strchr
  • 2656,742 Mo / s pour findFirstByte64
  • 13094.479 Mo / s pour strlen

... une version 32 bits:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... et une version 64 bits:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Edit 2011/06/04 L'OP souligne dans les commentaires que cette solution a un "bug insurmontable":

il peut lire au-delà de l'octet recherché ou du terminateur nul, ce qui pourrait accéder à une page ou une page non mappée sans autorisation de lecture. Vous ne pouvez tout simplement pas utiliser de grandes lectures dans les fonctions de chaîne à moins qu'elles ne soient alignées.

Ceci est techniquement vrai, mais s'applique à pratiquement tous les algorithmes qui fonctionnent sur des morceaux de plus d'un octet, y compris la méthode suggérée par l'OP dans les commentaires:

Une strchrimplémentation typique n'est pas naïve, mais un peu plus efficace que ce que vous avez donné. Voir la fin de ceci pour l'algorithme le plus largement utilisé: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Cela n'a vraiment rien à voir avec l' alignement en soi. Certes, cela pourrait potentiellement causer le comportement discuté sur la majorité des architectures courantes utilisées, mais cela a plus à voir avec les détails d'implémentation de la microarchitecture - si la lecture non alignée chevauche une limite 4K (encore une fois, typique), alors cette lecture provoquera un programme erreur de fin si la limite de page 4K suivante n'est pas mappée.

Mais ce n'est pas un «bug» dans l'algorithme donné dans la réponse - ce comportement est dû au fait que les fonctions aiment strchret strlenn'acceptent pas un lengthargument pour limiter la taille de la recherche. La recherche char bytes[1] = {0x55};, qui, aux fins de notre discussion, se trouve juste à la fin d'une limite de page de machine virtuelle 4K et la page suivante n'est pas mappée, avec strchr(bytes, 0xAA)(où strchrest une implémentation octet à la fois) plantera exactement le de la même façon. Idem pour strchrcousin apparenté strlen.

Sans lengthargument, il n'y a aucun moyen de dire quand vous devez quitter l'algorithme haute vitesse et revenir à un algorithme octet par octet. Un "bogue" beaucoup plus probable serait de lire "au-delà de la taille de l'allocation", ce qui résulte techniquement undefined behaviorselon les divers standards du langage C, et serait signalé comme une erreur par quelque chose comme valgrind.

En résumé, tout ce qui fonctionne sur des morceaux plus grands que des octets pour aller plus vite, comme le fait ce code de réponse et le code indiqué par l'OP, mais qui doit avoir une sémantique de lecture précise en octet est susceptible d'être "bogué" s'il n'y a pas d' lengthargument pour contrôler le ou les cas d'angle de "la dernière lecture".

Le code de cette réponse est un noyau permettant de trouver rapidement le premier octet dans un bloc de taille de mot de processeur naturel si le processeur cible a une ctzinstruction rapide . Il est trivial d'ajouter des choses comme s'assurer qu'il ne fonctionne que sur des limites naturelles correctement alignées, ou une forme de lengthborne, ce qui vous permettrait de sortir du noyau haute vitesse et de passer à une vérification octet par octet plus lente.

Le PO indique également dans les commentaires:

Quant à votre optimisation ctz, cela ne fait une différence que pour l'opération de queue O (1). Cela pourrait améliorer les performances avec de minuscules chaînes (par exemple, strchr("abc", 'a');mais certainement pas avec des chaînes de taille majeure.

Que cette affirmation soit vraie ou non dépend en grande partie de la microarchitecture en question. En utilisant le modèle canonique de pipeline RISC en 4 étapes, c'est presque certainement vrai. Mais il est extrêmement difficile de dire si cela est vrai pour un processeur super scalaire contemporain dans le désordre où la vitesse du cœur peut totalement éclipser la vitesse de streaming de la mémoire. Dans ce cas, il est non seulement plausible, mais assez courant, qu'il y ait un grand écart dans "le nombre d'instructions qui peuvent être retirées" par rapport au "nombre d'octets qui peuvent être diffusés" afin que vous ayez "le nombre d'instructions pouvant être retirées pour chaque octet pouvant être diffusé ". Si cela est assez grand, l' ctzinstruction + shift peut être effectuée "gratuitement".

Recherchez simplement "strstr le plus rapide", et si vous voyez quelque chose d'intéressant, demandez-moi.

À mon avis, vous vous imposez trop de restrictions (oui, nous voulons tous un sous-linéaire linéaire au max searcher), mais il faut un vrai programmeur pour intervenir, jusque-là je pense que l'approche de hachage est simplement une solution astucieuse-limbo ( bien renforcé par BNDM pour des motifs plus courts 2..16).

Juste un exemple rapide:

Faire recherchepattern (32bytes) dans une chaîne (206908949bytes) en-un en ligne ... Skip-Performance (plus-the-better): 3041%, 6801754 skips / itérations Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade performance: 3483KB / l'horloge

Faire recherchepattern (32bytes) dans une chaîne (206908949bytes) en-un en ligne ... Skip-Performance (plus-the-better): 1554%, 13307181 skips / itérations Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg performance: 2434KB / l'horloge

Recherche d'un motif (32 octets) dans une chaîne (206908949 octets) en une seule ligne ... Sauter-Performance (le plus grand est le meilleur): 129%, 160239051 sauts / itérations Two-Way_hits / Two-Way_clocks: 0/816 Two - Performance de la voie: 247 Ko / horloge

Sanmayce,
Cordialement

L'algorithme bidirectionnel que vous mentionnez dans votre question (qui d'ailleurs est incroyable!) A récemment été amélioré pour fonctionner efficacement sur des mots multi-octets à la fois: Optimal Packed String Matching .

Je n'ai pas lu tout l'article, mais il semble qu'ils s'appuient sur quelques nouvelles instructions CPU spéciales (incluses par exemple dans SSE 4.2) étant O (1) pour leur réclamation de complexité en temps, bien que si elles ne sont pas disponibles, elles peuvent simulez-les en temps O (log log w) pour des mots w-bit qui ne sonne pas trop mal.

Vous pouvez implémenter, par exemple, 4 algorithmes différents. Toutes les M minutes (à déterminer empiriquement), exécutez les 4 sur les données réelles actuelles. Accumuler des statistiques sur N exécutions (également à déterminer). Utilisez ensuite uniquement le gagnant pour les M minutes suivantes.

Enregistrez les statistiques sur les victoires afin de pouvoir remplacer les algorithmes qui ne gagnent jamais par de nouveaux. Concentrer les efforts d'optimisation sur la routine la plus gagnante. Portez une attention particulière aux statistiques après toute modification du matériel, de la base de données ou de la source de données. Incluez cette information dans le journal des statistiques si possible, de sorte que vous n'aurez pas à les comprendre à partir de la date / horodatage du journal.

J'ai récemment découvert un bel outil pour mesurer les performances des différents algos disponibles: http://www.dmi.unict.it/~faro/smart/index.php

Vous pourriez trouver cela utile. De plus, si je dois prendre un appel rapide sur l'algorithme de recherche de sous-chaînes, j'irais avec Knuth-Morris-Pratt.

Vous voudrez peut-être également avoir divers benchmarks avec plusieurs types de chaînes, car cela peut avoir un impact important sur les performances. Les algos effectueront différenlty en fonction de la recherche du langage naturel (et même ici, il pourrait encore y avoir des distinctions fines en raison des différentes morphologies), des chaînes d'ADN ou des chaînes aléatoires, etc.

La taille de l'alphabet jouera un rôle dans de nombreux algos, tout comme la taille de l'aiguille. Par exemple, Horspool fait bien sur le texte anglais mais mauvais sur l'ADN en raison de la taille différente de l'alphabet, ce qui rend la vie difficile pour la règle des mauvais caractères. L'introduction du bon suffixe allie cela grandement.

Je ne sais pas si c'est le meilleur, mais j'ai une bonne expérience avec Boyer-Moore .

Cela ne répond pas directement à la question mais si le texte est très volumineux, que diriez-vous de le diviser en sections superposées (chevauchement d'une longueur de motif), puis recherchez simultanément les sections à l'aide de fils. En ce qui concerne l'algorithme le plus rapide, Boyer-Moore-Horspool est, je pense, l'un des plus rapides sinon le plus rapide parmi les variantes de Boyer-Moore. J'ai posté quelques variantes de Boyer-Moore (je ne connais pas leur nom) dans cette rubrique Algorithme plus rapide que la recherche BMH (Boyer – Moore – Horspool) .

Le plus rapide est actuellement EPSM, de S. Faro et OM Kulekci. Voir http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

"Exact Packed String Matching" optimisé pour SIMD SSE4.2 (x86_64 et aarch64). Il fonctionne de manière stable et optimale sur toutes les tailles.

Le site auquel j'ai lié compare 199 algorithmes de recherche de chaînes rapides, les algorithmes habituels (BM, KMP, BMH) étant assez lents. EPSM surpasse tous les autres mentionnés ici sur ces plates-formes. C'est aussi le dernier.