Quelles sont les principales différences entre les Knuth-Morris-Pratt et de Boyer-Moore algorithmes de recherche?

Quelles sont les principales différences entre les Knuth-Morris-Pratt algorithme de recherche et de la Boyer-Moore algorithme de recherche?

Je sais KMP recherches de Y dans X, en essayant de définir un motif en Y, et enregistre le motif dans un vecteur. Je sais aussi que BM fonctionne mieux pour les petits mots, comme l'ADN (ACTG).

Quelles sont les principales différences dans la façon dont ils travaillent? Lequel est le plus rapide? Qui est moins de l'ordinateur-gourmand? Dans quels cas?

  • BM fonctionne mieux sur les "naturels texte" au lieu de petits ensembles
InformationsquelleAutor ghaschel | 2012-09-29
  1. 29

    Moore UTexas page web promenades à travers les deux algorithmes en une étape-par-étape de la mode (il fournit également des techniques diverses sources):

    Selon l'homme lui-même,

    Le classique de Boyer-Moore algorithme souffre du phénomène qu'il
    qui n'a pas tendance à travailler de manière efficace sur les petits alphabets comme de l'ADN. Le skip
    distance a tendance à cesser de croître avec la longueur du motif, car
    les sous-chaînes re-produisent fréquemment. En se souvenant plus de ce qui a
    déjà été appariés, on peut obtenir de plus grandes saute à travers le texte. Un
    pouvez même organiser une `mémoire parfaite" et ainsi regarder chaque personnage à
    plus d'une fois, alors que le Boyer-Moore algorithme, bien que linéaire, peut
    l'inspection d'un personnage dans le texte plusieurs fois. Cette idée de
    se souvenant de plus a été explorée dans la littérature par d'autres. Il
    souffre de la nécessité pour les très grandes tables ou des machines d'état.

    Cependant, il y a eu quelques les modifications de la BM qui ont fait de petit alphabet de la recherche viable.

    InformationsquelleAutor David Titarenco
  2. 34

    Dans un rough explication

    Boyer-Moore approche est d'essayer de faire correspondre le dernier caractère du modèle à la place du premier, avec l'hypothèse que si il n'y a pas de match à la fin, pas besoin d'essayer de correspondre à au début. Cela permet de "grands sauts" donc BM fonctionne mieux lorsque le motif et le texte que vous êtes à la recherche ressembler à "texte naturel" (c'est à dire l'anglais)

    Knuth-Morris-Pratt recherche des occurrences d'un "mot" W à l'intérieur d'un principal "chaîne de texte" S en employant l'observation que lorsque un décalage se produit, le mot lui-même incarne suffisamment d'informations pour déterminer l'endroit où le prochain match pouvait commencer, contournant ainsi le ré-examen de déjà caractères correspondent. (Source: Wiki)

    Cela signifie KMP est mieux adapté pour les petits ensembles comme l'ADN (ACTG)

    • Je ne comprends pas pourquoi ce serait une amélioration pour correspondre à la dernière personnages en premier. Si elle échoue, vous avez toujours à aller de l'avant par un caractère unique, non?
    • Voici un exemple: Word: guitare Texte: j'aime les guitares. Alors vous allez essayer de faire correspondre le "r" de la guitare (6 caractères) vs le 6ème caractère de texte... le "e" de "l'amour" ... car elles ne correspondent pas... pas besoin de vérifier à l'encontre de "j'aime", car ils ne seront jamais un match.. si vous sauter cette partie...
    • Droit, et ensuite vous sautez vers cochez la case 'r' vs ', mais qu'encore que vous avez déplacé vers l'avant 1 étape. Si vous aviez coché la case " g " vs " l " vous auriez eu le même résultat. Non?
    • probablement, ce sera aider: utdallas.edu/~besp/demo/John2010/boyer-moore.htm Et essaye de faire de mon cas par exemple: Texte: "j'aime les guitares" Modèle: "la guitare"
    • Bel exemple pour montrer l'idée derrière la BM. Malheureusement, la mise en œuvre est buggé. Essayez "VOICI UN SIMPIEXAMPLE" et "EXEMPLE" à l'entrée. Il en résultera aucun match, même si la chaîne de recherche se produit dans le texte recherché.
    • Une autre simulation est: people.ok.ubc.ca/ylucet/DS/BoyerMoore.html

    InformationsquelleAutor gtgaxiola
  3. 1

    Boyer-Moore technique correspondent aux caractères de droite à gauche, fonctionne bien sur des schémas.
    knuth moris pratt correspondent aux caractères de gauche à droite, travaille vite à court de motifs.

    InformationsquelleAutor Sadaf Khursheed