Understanding Boyer-Moore Algorithm

4

Modifica: ho trovato la pubblicazione originale . Mi sembra che l'originale non abbia un l′(i) . Ma potrei sbagliarmi perché la definizione di rpr(i) è così oscura per me. Non sono sicuro di come ci si avvale quando rpr(i) è negativo e cosa accade quando non viene trovata una tale ripetizione.

Sto cercando di implementare l'algoritmo di Boyer-Moore in base a questo .  Non sono sicuro se faccia parte di un libro o se siano solo alcune note universitarie. Secondo questo (poco prima Theorem 0.2.4 ):

Definition: Let l′(i) denote the length of the largest suffix of P[i..n] that is also a prefix of P, if one exists. If none exists, then let l′(i) be zero.

E poi continua da qualche altra parte con:

If, during the search stage, a mismatch occurs at position i − 1 of P and L′(i) > 0, then the good suffix rule shifts P by n − L′(i) places to the right, so that the L′(i) - length prefix of the shifted P aligns with the L′(i) - length suffix of the unshifted P. In the case that L′(i) = 0, the good suffix rule shifts P by n − l′(i) places.

Note that the rules work correctly even when l′(i) = 0.

Fai attenzione che gli indici sono basati su 1.

La parte con cui ho problemi è grassetto . Ad esempio se abbiamo il pattern abcde per cui l′(5) = 0 e se testiamo questo contro abcze ; la prima mancata corrispondenza si verifica in d rispetto a z . Ora che l′(5) è 0 , dobbiamo spostarlo n - l′(5) caratteri a destra e quindi abbiamo perso la possibilità di trovare la corrispondenza. Modifica: SBAGLIATO. Dovrebbe davvero spostare n - l′(5) caratteri perché non c'è z o e nel modello prima del carattere che stiamo controllando.

Quindi mi chiedo se mi manca qualcosa o no. Devo ignorare l′(i) quando è zero?

    
posta mostruash 02.10.2014 - 21:19
fonte

1 risposta

2

Quindi, dopo aver lavorato un po 'di più sull'algoritmo, ho funzionato. La risposta alla mia domanda è:

Dovrebbe essere spostato n - l′(i) caratteri a destra anche quando l′(i) = 0 .

Quando l′(i) è zero, ciò significa quanto segue:

  1. L′(i) è zero. Quindi non è stata trovata alcuna sottostringa ricorrente a sinistra che abbia un carattere precedente diverso. Per esempio:

    mismatch:               v -----
     pattern: a b c Z a b c Z a b c
       index: 1 2 3 4 5 6 7 8 9 0 1
              0                 1
    

Si verifica una mancata corrispondenza su Z . C'è una sottostringa di ripetizione abc a sinistra, ma inizia anche con Z . Quindi non va bene. L′(9) è 0 .

In questo caso, abc corrisponde al prefisso dell'intero modello, abc . l′(9) = 3 che è la lunghezza della corrispondenza del prefisso del substrato più lunga.

n - l′(9) = 11 - 3 = 8 turni, continuiamo a controllare pattern[1..3] rispetto a abc già presente nel testo originale.

  1. Il pattern non ha un prefisso che corrisponde alla sottostringa già abbinata finora.

Quindi è impossibile trovare una corrispondenza a meno che non spostiamo n - l′(i) = n caratteri a destra. Non sono ancora sicuro di come la pubblicazione originale gestisca il caso quando L′(i) è zero però.

    
risposta data 03.10.2014 - 17:01
fonte

Leggi altre domande sui tag