Comparaison entre l'algorithme Aho-Corasick et l'algorithme Rabin-Karp

Je travaille sur des algorithmes de recherche de chaînes qui prennent en charge la recherche de modèles multiples. J'ai trouvé deux algorithmes qui semblent être les candidats les plus forts en termes de temps d'exécution, à savoir Aho-Corasick et Rabin-Karp . Cependant, je n'ai pu trouver aucune comparaison complète entre les deux algorithmes. Quel algorithme est le plus efficace? En outre, lequel est le plus approprié pour le calcul parallèle et la recherche de modèles multiples? Enfin, lequel nécessite moins de ressources matérielles?

Pour l'algorithme AC, la phase de recherche prend temps, alors qu'elle est pour RK. Cependant, le temps de fonctionnement de RK est ce qui le rend similaire à AC. Ma conclusion provisoire est que RK semble pratiquement meilleur car il n'a pas besoin d'autant de mémoire que AC. Est-ce exact? $O(n+m)$ $O(nm)$ $O(n+m)$

algorithms algorithm-analysis runtime-analysis strings faucon
la source

Tous vos motifs sont-ils de la même longueur?

Hendrik Jan

@HendrikJan Non, modèles de longueurs différentes

Hawk

Si les motifs sont de longueur différente, il semble difficile de les traiter en parallèle en utilisant RK? La page wikipedia semble suggérer que ces modèles sont de longueur égale, bien que la mise à jour des hachages puisse être effectuée pour différentes longueurs.

Hendrik Jan

Êtes-vous intéressé par une sorte d'étude théorique ou d'expérience pratique?

Raphael

@Raphael D'un point de vue académique, nous appliquions d'abord l'étude théorique avant de le prouver empiriquement. J'ai posté la question ici parce que je ne m'attends pas à des réponses de programmation. J'ai besoin d'une réponse algorithmique logique

Hawk

Réponses:

L'analyse asymptotique du temps d'exécution n'est probablement pas le meilleur outil à choisir entre ces deux algorithmes: l'analyse asymptotique ignore les facteurs constants, et les facteurs constants seront critiques ici. Les deux algorithmes ont essentiellement le même temps d'exécution asymptotique, donc l'analyse asymptotique n'est probablement pas très utile pour choisir entre eux.

Au lieu de cela, le bon choix entre les deux algorithmes passe par une analyse expérimentale. Identifiez une charge de travail représentative, puis comparez les performances des deux algorithmes sur votre charge de travail, sur les types de machines que vous prévoyez d'utiliser dans la pratique.

$O(nm)$ $O(n+m)$

$O(n+m)$ $c\cdot(n+m)$ $c$ $O(n+m)$

$O(n+m)$ $O(nm)$

DW
la source

Cependant, je n'ai pu trouver aucune comparaison complète entre les deux algorithmes.

$O(n + m)$ $O(n m)$

mais par rapport à votre requête implicite de "comparaison complète", certains articles ont été écrits expérimentalement / empiriquement en comparant ces deux algorithmes et d'autres sur des données réelles et incluent une analyse / comparaison des avantages / inconvénients / compromis des différents algorithmes, par exemple:

Méthodologies d'appariement de chaînes à motifs multiples: une analyse comparative / Khan, Pateriya
UNE ÉTUDE COMPARATIVE SUR LES ALGORITHMES DE CORRESPONDANCE DES SÉQUENCES BIOLOGIQUES / Pandiselvam, Marimuthu, Lawrance

vzn
la source