Quali sono le principali differenze tra gli algoritmi di ricerca Knuth-Morris-Pratt e Boyer-Moore?

Question

Quali sono le principali differenze tra l'algoritmo di ricerca Knuth-Morris-Pratt e l'algoritmo di ricerca Boyer-Moore?

Conosco KMP cerca Y in X, cercando di definire un motivo in Y e salva il disegno in un vettore. So anche che BM funziona meglio per parole piccole, come il DNA (ACTG).

Quali sono le principali differenze nel modo in cui funzionano? Qual è più veloce? Qual è meno avido di computer? In quali casi?

Answer 1

Moore's UTexas webpage passeggiate attraverso entrambi gli algoritmi in modo passo-passo (egli fornisce anche varie fonti tecniche) :

• Knuth-Morris-Pratt
• Boyer-Moore

Secondo l'uomo stesso,

L'algoritmo classico Boyer-Moore soffre il fenomeno che tende a non funzionare in modo efficiente su piccoli alfabeti come il DNA. La distanza di salto tende a smettere di crescere con la lunghezza del motivo perché le sottostringhe si verificano di frequente. Ricordando più di ciò che è già stato corrisposto a , si possono ottenere salti più grandi attraverso il testo. Uno può persino disporre la "memoria perfetta" e quindi osservare ogni singolo carattere su una volta, mentre l'algoritmo Boyer-Moore, se lineare, può controllare più volte un carattere del testo da parte del testo. Questa idea di ricordare è stata esplorata in letteratura da altri. soffre della necessità di tabelle molto grandi o macchine di stato.

Tuttavia, ci sono stati alcuni modifications of BM che hanno reso praticabile la ricerca di piccoli alfabeti.

Answer 2

In una spiegazione approssimativa approccio

di Boyer-Moore è quello di cercare di far corrispondere l'ultimo carattere del modello al posto del primo con il presupposto che se non ci sta partita alla fine non c'è bisogno di cercare di abbinare all'inizio Questo permette di "grandi salti" quindi BM funziona meglio quando il modello e il testo che si sta cercando assomigliare "text naturale" (vale a dire inglese)

Knuth-Morris-Pratt ricerche per occorrenze di una "parola" W all'interno di una "stringa di testo" principale S impiegando l'osservazione che quando si verifica una mancata corrispondenza, la parola stessa incorpora informazioni sufficienti per determinare dove potrebbe iniziare la prossima corrispondenza, evitando così il riesame dei caratteri precedentemente abbinati. (Fonte: Wiki)

Ciò significa KMP è più adatto per piccoli insiemi come il DNA (ACTG)

Answer 3

La tecnica di Boyer-Moore corrisponde ai caratteri da destra a sinistra, funziona bene su modelli lunghi. knuth moris pratt abbina i caratteri da sinistra a destra, funziona velocemente su modelli corti.