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

Je suis coincé depuis un certain temps sur lequel est l'algorithme de recherche de chaînes le plus rapide, j'ai entendu de nombreuses opinions, mais à la fin je ne suis pas sûr.

J'ai entendu des gens dire que l'algorithme le plus rapide est Boyer-Moore et d'autres dire que Knuth-Morris-Pratt est en fait plus rapide.

J'ai recherché la complexité des deux mais ils se ressemblent pour la plupart O(n+m). J'ai trouvé que dans le pire des cas, Boyer-Moore a une O(nm)complexité par rapport à Knuth-Morris-Pratt qui a O (m + 2 * n). Où n = longueur du texte et m = longueur du motif.

Pour autant que je sache, Boyer-Moore a un pire temps linéaire si j'utilisais la règle de Galil.

Ma question, Sur tout ce qui est en fait l'algorithme de recherche de chaîne le plus rapide (Cette question comprend tous les algorithmes de piqûre possibles, pas seulement Boyer-Moore et Knuth-Morris-Pratt).

Modifier: en raison de cette réponse

Ce que je recherche exactement, c'est:

Étant donné un texte Tet un motif, Pje dois trouver toutes les apparences de Pin T.

De plus, la longueur de P et T est de [1,2 000 000]et le programme doit s'exécuter sous 0,15 sec.

Je sais que KMP et Rabin-Karp suffisent pour obtenir un score de 100% sur le problème, mais moi, je voulais essayer d'implémenter Boyer-Moore. Laquelle serait la meilleure pour ce type de recherche de modèle?

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 n'avez 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. En cas de non-concordance, l'analyse initiale est utilisée pour déterminer dans quelle mesure le motif peut être décalé par rapport au texte recherché. Cela fonctionne particulièrement bien pour les longs modèles de recherche. En particulier, il peut être sous-linéaire, car vous n'avez pas besoin de lire chaque caractère de votre texte.

• Knuth-Morris-Pratt: pré-analyse également le modèle, mais essaie de réutiliser tout ce qui était déjà mis en correspondance dans la partie initiale du modèle pour éviter d'avoir à le faire correspondre. Cela peut très bien fonctionner si votre alphabet est petit (par exemple, les bases d'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 les mêmes modèles de recherche encore et encore, c'est bien mieux que l'autre, car vous devez analyser les modèles une seule fois, pas une fois par recherche.

Par conséquent, comme d'habitude dans CS, il n'y a pas de réponse définitive au meilleur global . Il s'agit plutôt de choisir le bon outil pour le travail à accomplir.

Une autre note sur votre raisonnement dans le pire des cas: considérez les types de recherches nécessaires pour créer ce pire cas et réfléchissez bien à la pertinence de celles-ci dans votre cas. Par exemple, la O(mn)complexité la plus défavorable de l'algorithme de Boyer-Moore provient d'un modèle de recherche et d'un texte qui n'utilisent chacun qu'un seul caractère (comme trouver aaadans aaaaaaaaaaaaaaaaaaaaa) - avez-vous vraiment besoin d'être rapide pour des recherches comme celle-ci?

Bien que je sois un peu en retard pour répondre à cette question, mais je pense que Z-Algorithmc'est beaucoup plus rapide que ses homologues. Sa complexité la plus défavorable est O (m + n) et elle 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 existe une chaîne S ='abaaba'. Nous devons trouver des z(i)valeurs pour i=0 to len(S)-1. Avant d'entrer dans l'explication, permettez-moi de commencer par établir quelques définitions.

z(i)= non. des caractères du préfixe de Squi correspond au préfixe de s(i).

s(i)= ithsuffixe de S.

Voici les s(i)valeurs de 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 l'algorithme, 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 zvaleurs sans aucune surcharge de prétraitement. On se demanderait maintenant comment pouvez-vous utiliser cette logique pour faire correspondre le modèle 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 n'apparaît ni dans le motif ni dans le texte. J'en viendrai à l'importance $dans un petit moment.)

P$T = aba$aacbabcabaad

Nous savons len(P)= 3.

Toutes les valeurs z de P$Tsont

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 qui z(i)= len(P). Ans = 11.Donc, notre modèle est présent à Ans-len(P)-1= 7. -1est pour le $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 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.

Utilisez la mémoire adressable du contenu , implémentée dans le logiciel sous forme d'adressage virtuel (pointant les lettres vers les lettres).

C'est un peu superflu pour un algorithme de correspondance de chaîne moyen.

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

Voici comment fonctionne l'adressage virtuel.

Si je commence avec 256 adresses de début, 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 de lier des lettres à des lettres, c'est comme avoir 128 tranches d'adressage virtuel pointant vers l'adressage virtuel.

Cela fonctionnera - mais pour arriver à 900.000.000 de motifs correspondant simultanément, il y a une dernière astuce à ajouter - et il profite du fait que vous commencez par beaucoup de réutilisation de ces tampons de lettres, mais plus tard, il se disperse. Si vous listez le contenu, au lieu d'allouer les 256 caractères, cela ralentit très peu et vous obtiendrez une augmentation de 100 fois la capacité, car vous n'obtiendrez finalement qu'une seule lettre dans chaque tampon de pointeur de lettre (que j'ai surnommé ' échapper').

Si vous souhaitez obtenir une correspondance de chaîne de voisin le plus proche, vous en avez plusieurs en parallèle et vous les collectez dans une hiérarchie, de sorte que vous diffusez votre erreur sans biais. si vous essayez de trouver le plus proche voisin avec un seul, vous êtes biaisé vers le début de l'arbre.