Quel algorithme de recherche de chaînes est en fait le plus rapide?

Cela dépend du type de recherche que vous souhaitez effectuer. Chacun des algorithmes fonctionne particulièrement bien pour certains types de recherche, mais vous navez pas précisé le contexte de vos recherches.

Voici quelques réflexions typiques sur les types de recherche:

• Boyer-Moore: fonctionne en pré-analysant le motif et en comparant de droite à gauche. Si une discordance se produit, lanalyse initiale est utilisée pour déterminer dans quelle mesure le modèle peut être déplacé par rapport à t. le texte recherché. Cela fonctionne particulièrement bien pour les modèles de recherche longs. En particulier, il peut être sous-linéaire, car vous navez pas besoin de lire chaque caractère de votre texte.

• Knuth-Morris-Pratt: pré-analyse également le modèle , mais essaie de réutiliser ce qui était déjà apparié dans la partie initiale du motif pour éviter davoir à le refaire. Cela peut très bien fonctionner si votre alphabet est petit (par exemple, les bases ADN), car vous avez plus de chances que vos modèles de recherche contiennent des sous-modèles réutilisables.

• Aho- Corasick: nécessite beaucoup de prétraitement, mais le fait pour un certain nombre de modèles. Si vous savez que vous rechercherez sans cesse les mêmes modèles de recherche, alors cest bien mieux que lautre, car vous ne devez analyser les modèles quune seule fois, pas une fois par recherche.

Par conséquent, comme dhabitude dans CS, il ny a pas de réponse définitive au meilleur global . Il sagit plutôt de choisir le bon outil pour le travail à accomplir.

Autre remarque sur votre pire raisonnement: considérez les types de recherches nécessaires pour créer ce pire cas et réfléchissez bien à la question de savoir si ceux-ci sont vraiment pertinents dans votre cas. Par exemple, la complexité dans le pire des cas O(mn) de lalgorithme de Boyer-Moore provient dun modèle de recherche et dun texte qui nutilisent chacun quun seul caractère (comme trouver aaa dans aaaaaaaaaaaaaaaaaaaaa) – avez-vous vraiment besoin dêtre rapide pour des recherches comme ça?

Commentaires

• Jai à peu près tout lalphabet anglais à utiliser et jai mis à jour la question, désolé de ne pas avoir commencé avec ça à la mendicité.
• Et oui, je dois être rapide même pour des recherches comme que
• pouvez-vous sil vous plaît éloborer sur lalgorithme de Z ‘ et manachar également?

Bien que je sois un peu en retard pour répondre à cette question, je pense que Z-Algorithm est beaucoup plus rapide que ses homologues.Sa complexité dans le pire des cas est O (m + n) et il ne nécessite aucun prétraitement du motif / texte. Il est également très facile à coder par rapport aux autres algorithmes.

Cela fonctionne de la manière suivante.

Par exemple, il y a une chaîne S ="abaaba". Nous devons trouver les valeurs z(i) pour i=0 to len(S)-1. Avant dentrer dans lexplication, permettez-moi de vous donner quelques définitions.

z(i) = no. de caractères du préfixe de S qui correspond au préfixe de s(i).

s(i) = ith suffixe de S.

Voici les s(i) valeurs pour s = "abaaba".

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

Les valeurs z sont respectivement

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

Pour une compréhension détaillée de lalgorithme, reportez-vous aux liens suivants.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Il faut maintenant O (N) pour trouver toutes les valeurs de z sans aucune surcharge de prétraitement. On se demanderait maintenant comment utiliser cette logique pour faire correspondre un motif dans une chaîne donnée?

Voyons voir avec un exemple. Motif (P): aba, Texte (T): aacbabcabaad.

Mettez ceci sous la forme P $ T. ($ – tout caractère qui napparaît ni dans le motif ni dans le texte. Jen viendrai à limportance de $ dans un instant.)

P$T = aba$aacbabcabaad

Nous savons len(P) = 3.

Toutes les valeurs z de P$T sont

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

Maintenant lesquelles z(i) = len(P). Ans = 11. Donc notre motif est présent à Ans-len(P)-1 = 7. -1 correspond au caractère $.

Maintenant, pourquoi $ ou un tel caractère spécial est important. Considérez P = "aaa" et T = "aaaaaaa". Sans le caractère spécial, tous les z(i) auront des valeurs incrémentielles. On peut toujours trouver la position du motif dans le texte avec les formules ci-dessous:

Condition: z(i)> = len(P) et Position: Ans-len(P). Mais la condition dans ce cas devient un peu délicate et déroutante. Personnellement, je préfère utiliser la technique des caractères spéciaux.

Commentaires

• Pourriez-vous lexpliquer vous-même ici? Avoir des liens vers des sites externes peut être utilisé pour élaborer, mais le cœur dune réponse devrait être dans la réponse elle-même plutôt que davoir à suivre un lien vers un autre site.
• Lalgorithme z est fondamentalement le même que kmp. Je doute que ce soit beaucoup plus rapide.
• Je suis daccord avec @ThomasAhle. Calculer z est un prétraitement. Cependant, cest ‘ une bonne explication. Jai mis en place un moyen O(n) de passer du prétraitement KMP au prétraitement Z, en raison de cette réponse. Ici

Utilisez mémoire adressable de contenu , implémentée dans un logiciel sous forme dadressage virtuel (pointant des lettres vers des lettres).

Cest un peu superflu par rapport à un algorithme de correspondance de chaînes moyen.

CAM peut correspondre à un grand nombre de modèles simultanément, jusquà environ 128 modèles de lettres (sils sont ASCII; sils sont Unicode seulement 64). Et cest un appel par longueur de lettre dans la chaîne à laquelle vous voulez faire correspondre et une lecture aléatoire de la mémoire par longueur de la longueur maximale du motif. Donc, si vous analysiez une chaîne de 100 000 lettres, avec jusquà 90 000 000 de motifs simultanément (ce qui prendrait environ 128 Gio pour stocker un nombre de motifs aussi grand), cela prendrait 12 800 000 lectures aléatoires à partir de la RAM, donc cela se produirait en 1 ms.

Voici comment fonctionne ladressage virtuel.

Si je commence avec 256 adresses de départ, qui représentent la première lettre, ces lettres pointent vers 256 des lettres suivantes. Si un modèle est inexistant, vous ne le stockez pas.

Donc, si je continue à lier des lettres à des lettres, cest comme avoir 128 tranches dadressage virtuel pointant vers ladressage virtuel.

Ce sera travailler — mais pour arriver à 900 000 000 de motifs correspondant simultanément, il ya une dernière astuce pour y ajouter — et il en profite du fait que vous commencez avec beaucoup de réutilisation de ces tampons de lettres, mais plus tard, cela se disperse.Si vous répertoriez le contenu, au lieu dallouer les 256 caractères, cela ralentit très peu et vous obtiendrez une augmentation de capacité de 100 fois, car vous nobtiendrez finalement quune lettre utilisée dans chaque tampon de pointeur de lettre (que jai doublé  » escape « ).

Si vous voulez obtenir une correspondance de chaîne avec le voisin le plus proche, vous en avez beaucoup en parallèle et vous les collectez dans une hiérarchie, donc vous répartissez votre erreur de manière impartiale. le plus proche voisin avec un seul, alors vous « êtes biaisé vers le début de larbre.

Commentaires

• @MagnusRobertCarlWoot étant donné que vous avez le même gavatar comme roucer81, cest soit une coïncidence astronomique de collision de code de hachage, soit vous avez la même adresse e-mail. Si vous êtes le même individu derrière les deux comptes, vous devez utiliser le formulaire  » contactez-nous  » pour les fusionner afin dobtenir le crédit approprié pour la réputation acquise grâce aux votes positifs sur cette réponse.